Akademisyenler öncülüğünde matematik/fizik/bilgisayar bilimleri soru cevap platformu
3 beğenilme 0 beğenilmeme
805 kez görüntülendi

Dunya uzerinde her gun yeni bir teknolojik gelisme oluyor. Robotlar, telefonlar, tabletler vs. Telefonlarimiz gittikce hizlaniyor, bilgisayarlarimiz hizlaniyor. Cep telefonumuzla selfie cekip arkadasimiza gondermemiz 10 saniyemizi almiyor. Biz farkinda olmadan elimizdeki aletler saniyede yuzlerce matris, onlarca polinom carpiyor. Sonucta fotograf dedigimiz sey, goruntu dedigimiz sey kucuk kucuk karelerden baska bir sey degil. Bu karelerin her birinde bir renk var, bu renklerin her birinin bir sayisal degeri var. Bu sayisal degerler degistikce, fotograf da degisiyor. Ornegin, instagramda fotografiniza filtre eklerken aslinda sadece bir matris uzerindeki sayilari degistiriyorsunuz.

Farkinda olmadan biz, bilgisayar bilimleriyle ulasan matematikciler her gecen gun bu makinelerimizi daha da hizlandiracak algoritmalar uretmeye calisiyorlar. Benim soracagim soru da iki polinomu birbiriyle carpmayi kolaylastiracak bir algoritma bulabilmek ile ilgili.

Tamam, hepimiz iki polinomu nasil carpmamiz gerektigini biliyoruz. Ornegin $p(x) = a + bx$ ve $q(x) = c + dx$ olsun. $p(x)q(x) = A + Bx + Cx^2$ diyelim. O zaman, teker teker terim terim carparak $A = ac, B=ad + bc$ ve $C=bd$ oldugunu buluyoruz. Ama bu arada 4 adet carpma islemi, 1 adet toplama islemi yapiyoruz. Algoritmamizin amaci kullandigimiz carpma islemi sayisini azaltmak. Bu arada toplama islemi sayisi artabilir.

Bunun mantigi ne? Carpma genel olarak toplamadan cok daha pahali bir islemdir. Ben size 123456 ile 789123 sayilarini carpin desem, kac dakikanizi alir? Bu sayilari toplayin desem ne kadar vaktinizi alir? Biz de algoritmamizdaki carpma islemi sayisini azaltarak bilgisayarimizi, telefonumuzu ya da kredi karti pos makinemizi hizlandirmak istiyoruz.

Elimizde iki tane $n$inci dereceden polinom olsa, bunlari standard yontemle carptigimizda $n^2$ adet carpma islemi yapmis oluruz.

Soru 1: Bu $n^2$ tane carpma isleminin sayisini azaltacak bir algoritma bulabilir misin?

Soru 2: Bu islem sayisini ne kadar azaltabilirsin? Ornegin $n$ adet carpma islemiyle calisacak bir algoritma bulabilir misin? Alt sinir nedir?

Akademik Matematik kategorisinde (2.5k puan) tarafından  | 805 kez görüntülendi

Cauchy çarpımı uygulandığında $n^2$ yerine $n$ toplamla iş hallolmuyor mu?

@Anil anlamadim yorumunu
Hocam cevabi soruda vermissiniz olmaz ki boyle ?
Anlamadım, nerede vermişim?
DFT ler tesadufen mi koyu ?
Aaa ne çakalmışım beş yıl önce :)

1 cevap

2 beğenilme 0 beğenilmeme
En İyi Cevap

Soru 1 in cevabi sitede dolayli yoldan var.

Polinomlarin katsayilarinin olusturdugu dizilerin katlamasi/evrisimi/convolutioni, polinomlarinin carpimlarinin katsayilarinin olusturdugu dizi olacak. Katlamalar Diskret Fourier Transformasyonu altinda carpmaya donuyor.

Yani iki polinomun da DFT sini alip, noktasal carpip, ters DFT yi hesaplarsak iki polinomu carpmis oluruz.

Su soruda verilen algoritma DFT yi $O(n\log n)$ islemde hesapliyor. 

 

Soru 2 nin cevabini bulunca unlu oluyoruz zaten :)

 

(1.6k puan) tarafından 
tarafından seçilmiş
20,200 soru
21,726 cevap
73,275 yorum
1,887,832 kullanıcı