Yazan : Şadi Evren ŞEKER
Bu yazının amacı, matrislerin determinantını (masfuf muheddedad, matrix determinant) nasıl hesaplandığını anlatmaktır.
Konuya basit matrisler ile başlayalım. Örneğin 2×2 boyutundaki bir matris için:
basitçe det(A) = ad – bc şeklinde hesaplanabilir buradaki hesap aşağıda gösterilen iki ok yönünden sağı göstereni + ve solu göstereni – alarak hatırlanabilir:
Şekilde görüldüğü üzere mavi okun üzerinden geçtiği elemanlar ad ve kırmızı okun üzerinden geçtiği elemanlar cb olmaktadır ve determinant ad-cb şeklinde hesaplanmaktadır.
Determinant hesaplanırken matrisin köşeli parantezleri yani [] sembolleri yerine düz parantezler yani || sembolleri kullanılır.
olarak yazılabilir.
3×3 boyutundaki bir matrisin determinantı yine benzer şekilde oklar kullanılarak hesaplanabilir.
Genel olarak herhangi boyuttaki bir matrisin determinantı ise aşağıdaki formül ile hesaplanabilir:
Yukarıdaki gösterimde, kısaca bir matrisin nxn boyutunda olduğu kabul edilmiş ve öncelikle y sembolü kullanılmıştır. Buradaki y sembolü yer değiştirmeyi (permutation) ifade etmektedir. Yani y_i demek, i.nci değiştirme (permütasyon) demektir. Örnek olarak elemanlarımız 1,2,3 ise ve yerdeğiştirme dizilimi aşağıdaki şekildeyse:
1,2,3
2,3,1
3,1,2
2,1,3
1,3,2
3,2,1
Bu dizilimdeki her elemana bir numara verildiğinde yi gösterimindeki i değerine göre bir gösterim ifade ediliyor demektir. Örneğin i=5 için yukarıdaki gösterimlerden 5. sıradakini anlayabiliriz ki bu da 1,3,2 gösterimidir.
Denklemde yer alan diğer bir gösterim ise yön() fonksiyonudur. Basitçe +1 veya -1 döndüren bir fonksiyondur ve aşağıdaki şekilde ifade edilebilir:
Kısacası aldığı parametrenin teklik/çiftliğine göre + veya – döndüren fonksiyondur.
Çarpım sembolü ile ifade edilen terim ise yukarıdaki 2×2 veya 3×3 boyutlu matrislerde gösterilen ve çarpılarak daha sonra toplanan veya çıkarılan her bir terim için kullanılmıştır.
Örnek olarak yukarıdaki dizilimleri ele alacak olursak aşağıdaki şekilde 3×3 boyutundaki bir matirisin determinantını hesaplayabiliriz:
Yukarıdaki yaklaşımda, ilk satırda bulunan sayılar kapatılıp kalan alandaki matrislerin determinantı ile çarpılmıştır. Ayrıca çarpma işlemi sırasında bir artı bir de eksi yönde ilerlenmiştir.
Örneğin 5 çarpanı için:
5 sayısının bulunduğu satır ve sütun kapatılıp kalan satır ve sütunlardaki matris alınmıştır. Benzer şekilde 3 sayısı için:
3 sayısının bulunduğu satır ve sütundaki sayılar kapatılır ve geri kalan sayılardan oluşan matris okunur.
Bu şekilde alt matrisler elde edilir ve bu alt matrisler ise kapanan sayı sabit çarpıma (scalar multiplication) tabi tutulur.
Neticede çıkan sonuç toplanır. Yani yukarıdaki örnekten devam edilecek olursa
5( 4 . 4 – 9 . 6 ) – 3( 2 . 4 – 9 . 3 ) + 7 ( 2 . 6 – 4 . 3)
olur Bu işlemin sonucu da
-133
olarak bulunur.
Yukarıdaki bu genel hesaplama formülüne göre kodlaması aşağıdaki şekilde yapılabilir:
Yukarıdaki kodun ekran çıktısı aşğaıdaki şekildedir:
Kabaca kodu açıklayacak olursak. Determinant fonksiyonu bir integer matris parametre olarak almaktadır. Koddaki ilk 2 if (4. ve 8. satırlardaki) özel matris determinantı için kullanılır. Yani matrisin boyutunun 1×1 veya 2×2 olması durumları içindir. Bu hesaplar doğrudan yukarıdaki yazıda anlatıldığı şekliyle yapılır. Yani 1×1 için matrisin yegane elemanı döndürülürken 2×2 için köşegen ve ters köşegendeki sayılar çarpılıp çıkarılarak döndürülür.
Şayet matrisin boyutu 2×2’den daha fazla ise (örneğin 3×3 veya 4×4 gibi) bu durumda matris, yukarıdaki örnek çözümünde olduğu gibi küçük matrislere bölünür ve her eleman için artı ve eksi şekilde sayısal değerler denkleme dahil edilerek hesaplanır.
Kodun 15. satırından başlayan döngü ilk satırı ve ilgili sütunu kapatmakta ve kalan küçük matrisi 25. satırdaki işlem ile özyineli (recursive) olarak tekrar denkleme sokmaktadır. Ayrıca -1 sayısının üstü alınarak yön fonksiyonu kodlanmıştır (-1 sayısının çift üstlerinin + ve tek üstlerinin – olduğunu hatırlayınız).
sa hocam biz aşağıdaki programı yazmaya çalıştık ama hata veriyo ve craşş oluyo nerede hata yaptığımızı bulamadık projenin konusunu versek yardımcı olabilirmisiniz şimdiden teşekkür ederimPROJE KONUSU:
Bir şehirde, programa girdi olarak verilecek arzu edilen maksimum yürüyüş mesafesi bilgisi gözönünde
bulundurularak en fazla sayıda alışveriş merkezine yakınlığı bulunan bölgenin tespit edilmesi
gerekmektedir. Şehirde bulunan alışveriş merkezlerinin konumları da girdi olarak verilecektir.
Şehirdeki sokaklar ızgara (grid) şeklinde organize edilmiştir. x-y koordinat sisteminde (a,b) ve (c,d)
noktalarıyla temsil edilen iki kavşak noktası arasındaki yürüyüş mesafesi |a – c| + |b – d| formülüyle
hesaplanır.
Aşağıdaki şekil 4×4 boyutlarındaki bir şehre ait sokakları ve sokakların kesişim noktalarındaki
kavşakları göstermektedir.
PROGRAM GİRDİSİ:
Program girdisi bir metin dosyasından okunacaktır. Dosya içerisinde birden fazla test durumu
bulunabilir. Her bir test durumu, ayrı bir şehri, bu şehirdeki alışveriş merkezlerinin konumunu ve arzu
edilen maksimum yürüyüş mesafesini temsil etmektedir. Her bir test durumunun ilk satırı dx, dy, n, ve
q olmak üzere 4 adet tamsayı içermektedir. dx ve dy (1 ≤ dx, dy ≤ 1000) şehrin boyutlarını, n
(0 ≤ n ≤ 5· 105) şehirdeki alışveriş merkezlerinin toplam sayısını belirtmektedir. q (1 ≤ q ≤ 20) ise
toplam sorgu sayısını (arzu edilen maksimum yürüyüş mesafeleri sayısı) temsil etmektedir. Takip eden
n adet satırın her biri xi ve yi (1 ≤ xi ≤ dx+1, 1 ≤ yi ≤ dy+1) olmak üzere i. alışveriş merkezinin
konumunu belirtmektedir. Alışveriş merkezlerinin yalnızca kavşak noktalarında konumlandığı ve her
bir kavşakta en fazla 1 adet alışveriş merkezinin bulunabileceği varsayılmaktadır. Takip eden q adet
satırın her biri ise bir alışveriş merkezine ulaşmak için arzu edilen maksimum yürüyüş mesafesini (m, 0
≤ m ≤ 106) göstermektedir. Girdi dosyasının son satırı 4 adet 0 rakamı içermektedir.
PROGRAM ÇIKTISI:
Programın çıktısı bir metin dosyasına kaydedilmelidir. Giriş dosyasında, verilen her bir test durumu
için çıkış dosyasında test numarası belirtilmeli ve test durumundaki her bir sorguya karşılık gelen bir
satır üretilmelidir. Üretilecek bu satırlar, sorguda belirtilen maksimum yürüyüş mesafesi (m) dikkate
alındığında erişilebilecek maksimum alışveriş merkezi sayısını ve bunun için en uygun kavşak
noktasının koordinatlarını içermelidir. Örneğin, aşağıdaki tabloda gösterilen örnek, maksimum yürüyüş
mesafesi 1 olarak alındığında maksimum 3 adet alışveriş merkezine (3,4) koordinatlı kavşaktan
erişilebileceğini göstermektedir. Maksimum yürüyüş mesafesi 2 olarak seçildiğinde (2,2) konumundan
maksimum 4 alışveriş merkezine erişilebilir. Birden fazla optimal kavşak bulunduğu durumlarda bu
kavşaklardan en güneydeki (minimum pozitif y koordinatına sahip olan) tercih edilir. En güney
pozisyonunda birden fazla kavşak var ise bu durumda en batıdaki (minimum pozitif x koordinatına
sahip olan) kavşak optimal çözüm olarak seçilir.
Örnek Girdi Örnek Girdiye ait Çıktı
4 4 5 3
1 1
1 2
3 3
4 4
2 4
124
0 0 0 0
Case 1:
3 (3,4)
4 (2,2)
5 (3,1)
Hocam, peki mesela 6×7 lik bir matrisin determinantını hesaplamak istesek nasıl bir yol izlemeliyiz?
6×7 boyutlarındaki bir matrisin (masfuf) tersi yoktur. Kısaca matrisin determinantının hesaplanabilmesi için tersi alınabilir matris olması gerekir ve tersi alınabilir matrislerin tamamı kare matrisler (square matrix) için tanımlıdır. Sizin sorunuzdaki kare olmayan (non-square) matrisler için bir birim matris (Identity matrix) bulunmaz (birim matris diyagonu 1 diğer elemanları sıfır olan kare matristir) dolayısıyla tersi alınmaz ve dolayısıyla determinantı yoktur.
Merhaba hocam
Yukarıdaki kod da 1 2 3 serisinin yer değiştirme dizilimini nasıl yazabilirim ?
hocam sitenizdeki “permütasyon algoritması” konu baslığı altında permütasyonu sadece zar için almışsınız ben n*n matriste nasıl kullanabilirim ? ( matrisin boyutunu ve değerlerini kullanıcı belirleyecek )
Bütün diziler tek boyutlu diziye indirgenebilir (zaten indirgenir de, nitekim RAM(hafıza) tek boyutludur). O anlatımda sanırım 1’den 6’ya kadar olan semboller tek bir dizi gibi kabul ediliyordu. Yapmanız gereken dizinizi (kaç boyutlu olursa olsun nxn ise iki boyutludur) tek boyutlu olarak düşünmek. ve aynı algoritmayı uygulamak.
hocam ben bunu c# olarak visual studio da yapmayı denedim ama determinant (gecici) den sonra
determinant diye public açtığımda orası hata veriyo hocam bide ben public Form1()
{
InitializeComponent();
}
buranın üstünde sizin gibi en üste public i public determinant(int[,] matris); bu şekilde hocam hata vermeye başladı ve bana şunu dedi
Error CS0501 ‘Form1.determinant(int[*,*])’ must declare a body because it is not marked abstract, extern, or partial determinantmatris hocam bunu nasıl düzeltirim