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?