Dünyaya Yön Veren 5 Algoritma

Karnınızın çok aç olduğunu hayal edin, güzel bir havuçlu kek yapmaya karar verdiniz. Bütün malzemeleri hazırladınız ve sırasıyla olması gerektiği gibi karıştırıp sonrasında pişirdiniz. Tebrikler, aslında kek yaparken sırasıyla uygulanan bütün o adımlar “kek yapma algoritması” adını verdiğimiz bir algoritmanın parçası. Teknoloji dünyasında da işler bundan farklı ilerlemiyor, belirli bir amacımız var ve amacımızı gerçekleştirmeye yönelik çeşitli yöntemlerle oluşturulmuş adımlara sahibiz. Peki, bu çoğu yerde işittiğimiz ya da kullandığımız algoritmalar tam olarak nedir? En çok nerelerde karşımıza çıkar ve nasıl kullanılır? Detaylar yazımızda.

A- A+

26.02.2022 tarihli yazı 5909 kez okunmuştur.

Algoritma Yazılım Bilgisayar

Algoritmalar belirli bir problemi çözmek, bir sonuca varmak için atılan adımlardır. Bu adımların sonuca götürmesinin yanı sıra sonlu, hızlı ve sade olması gerekir. Algoritmalar genellikle bilgisayar bilimleriyle beraber kullanılsalar da aslında çok eski bir tarihleri vardır.

İlk örnekleri M.Ö. 1600 yıllarında Babiller tarafından taş tabletlere yazılmış, çarpanlara ayırma ve karekök bulma ile alakalı tabletlerdir. M.Ö. 300 yıllarında Öklid’in bulduğu “en büyük ortak bölen” algoritması bile halen kullanılmaktadır. Bu yolculuğun önemli noktalarından birisi de 813-833 yılları arasında doğrusal ve 2. derece denklemlerin çözümü için algoritmalar geliştiren El-Harezmî’dir. Ayrıca Algoritma kelimesinin kökü Harezmî’nin isminden gelmektedir. Bu ilerlemeler teknolojinin de hızla gelişmesiyle artık teknoloji ve algoritmalar birbirinin ayrılmaz parçalarıdır. Zamanla farklı problemler için onlara özel farklı çözüm algoritmaları oluşturulmuştur. Bu yazımızda, çok yaygın bir şekilde kullanılan 5 algoritmaya yer verdik.

►İlginizi Çekebilir: Beş Dakikada "Algoritmayı" Tanıyın

1) Dijkstra’nın En Kısa Yol Algoritması

Dijkstra algoritması ismini algoritmanın geliştiricisi olan Hollandalı bilgisayar bilimci Edsger Dijkstra’dan almaktadır. Dijkstra algoritması eğer elimizde ağırlıklı bir graf (çizge) varsa açgözlü algortimayı (greedy algorithm) yani, sonraki adımları göz önüne almadan mevcut durumdaki en iyi seçeneği belirleyip kullanarak verilen grafta en kısa yolu (shortest path) bulmayı amaçlayan bir algoritma kullanır. Graf, yapısında düğümler (nodes) ve bu düğümleri birbirine bağlayan kenarlardan (edges) oluşan bir ağ yapısıdır. Ağırlıklı graf (weighted graph) yapısından kastedilen ise kenarlar üzerinde seçimleri etkileyen maliyetlerin ulunduğu graf yapısıdır.

►İlginizi Çekebilir: Bataryanın Hızlı Şarj Olmasını Sağlayan Algoritma

Başlangıç için seçtiğimiz (hangisi olacağı bize bağlı) düğüme sıfır, diğer düğümlere sonsuz bir değer atanır. Başlangıç düğüm, etrafındaki bütün komşuları ziyaret ederek mesafeleri günceller, güncellenen komşularda en kısa mesafede olan sanki yeni bir başlangıç noktasıymış gibi düşünülerek güncelleme işlemi bütün noktalar arasından en kısa yol bulununcaya kadar devam eder. Yani, seçtiğimiz ilk nokta ile hedef noktalar arasında en kısa mesafe tespit edilmiş olur. Dijkstra algoritması Google ve Yandex haritaların kullandığı algoritmalardan birisidir. Endüstri Mühendisliği alanında da üretim, lojistik, bir hizmetin en kısa yolu göz önünde bulundurarak kullanıcıya ulaştırmak gibi konular başta olmak üzere birçok optimizasyon probleminin çözümünde faydalanılır.

2) Arama ve Sıralama Algoritmaları

Günlük hayatta olduğu gibi bilgisayarlar dünyasında da bazı şeylerin gerektiğinde sıralanmasında veya lazım olduğunda onu bulmak için aramamıza gerek olabilir. Bunları yapmamız gerektiğinde bilgisayar dünyasında bu algoritmaların en iyi, ortalama ve en kötü senaryolara göre zaman ve bellek karmaşıklığının analiz edilmesi gerekir. Zaman karmaşıklığı, algoritmamızın girdisini boyutu arttıkça sonuç için gerekli adım sayısının analizini yapar. Bu sayede sonuç için ne kadar zaman gerektiği hakkında bir tahminde bulunabiliriz. Bellek karmaşıklığı ise aynı şekilde elimizdeki girdi boyutu arttıkça kullanılan bellek miktarı hakkında bilgi verir.

►İlginizi Çekebilir: Ö lümü Öngören Algoritma Geliştirildi

Arama algoritmaları (searching algorithms), bazı veri yapılarında (liste, dizi, ağaç, graf) bulunan verileri aramak veya olup olmadığını kontrol etmek için kullanılır. Arama işlemini türüne göre ikiye ayrılır. Sıralı arama verinin tutulduğu veri yapısındaki tüm elemanlar gezilerek kontrol edilir. Örnek olarak doğrusal arama (linear search) verilebilir. Bu yazıda aradığınız bir kelimeyi bulmak için teker teker bütün kelimelere bakmak zorunda olduğunuzu düşündüğünüzde, baya zorlu bir iş olurdu. Diğer tür aralıklı arama ise sıralanmış verilerde çalışır ve veri yapısını sürekli ikiye bölerek arama alanını daraltmayı amaçlar. Bu yöntem birçok algoritmada da kullanılan parçala fethet yaklaşımının bir uygulamasıdır. Örnek olarak ikili arama (binary search) verilebilir.

İkili Arama Örneği

Sıralama algoritmaları (sorting algorithms), veri yapılarında tutulan verileri küçükten büyüğe veya tam tersi şekilde sıralamak için kullanılır. Bunu yapmak çok fazla yol geliştirilmiştir. Bazıları bellek karmaşıklığı göz önüne alındığında daha verimlidir. Örneğin hızlı sıralama algoritması (quick sort). Bazıları ise zaman karmaşıklığı açısından daha yararlı olabilir. Örneğin, birleştirme sıralaması (merge sort).

3) Anahtar Değişimi Şifreleme

Şifreleme antik çağlardan beri hep önemli olmuştur. Devamlı olarak yeni teknikler geliştirilmiş ve en güvenli yol bulunmaya çalışılmıştır. Şifreleme, okunabilir bir veriyi bazı yöntemlerle farklı bir veri baytına dönüştürür. Gönderici ve alıcı arasındaki iletişimin güvenliği istenmeyen kişiler tarafından her an kesilebilir veya değiştirilebilir. Anahtar değişimi şifrelemede verileri şifreleme ve deşifre etmede iki tür anahtar kullanılır. Sadece gönderici ve alıcının bildiği kendilerine ait gizli anahtar (private key) diğeride bütün herkesin ulaşabileceği açık anahtar (public key). Taraflar birbirlerine temas etmeden hatta tanışmadan bu anahtarlar aracılığıyla verileri şifreler ve şifrelenmiş bu verileri deşifre edebilirler.

►İlginizi Çekebilir: Yapay Zeka Optimizasyon Algoritmaları

Anahtar değişimi şifrelemenin önemli bir parçası olan Diffie-Hellman anahtar değişimini örnek olarak verebiliriz. Günümüzde çokça adını duyduğumuz uçtan uca şifreleme sırasında Diffie-Hellman anahtar değişimi şifrelemeden faydalanılır. Şifreleme mantığı bir temel bir matematik kuralına dayanır gab=gba ((23)5=(25)3=32768) yani bir sayıda aynı üsler hesaplanırken sıra önemli değildir, önce “a” üssünü sonra üssünü almak ile önce b’yi almak aynı şey olacaktır. Bu şifreleme yönteminin güvenilir olmasının nedeni üs alma işleminin kolay fakat logaritma işlemini zor olmasına dayanır.

Örnek olarak;

1. Gönderici ve alıcı, kendileri dışında kimsenin bilmediği birer sayı (Private key) seçiyor ve kimseyle paylaşmıyor (gönderici=a, alıcı=b).

2. Herkesin ulaşabileceği iki açık anahtar (public key) duyuruluyor (g=3, p=17)

3. Gönderici “a” gizli anahtarından yararlanarak ga mod p sonucunu hesaplar ve alıcıya iletir.

4. Alıcı “b” gizli anahtarından yararlanarak gb mod p sonucunu hesaplar ve göndericiye iletir.

Gönderici (gb mod p) a mod p denklemini alıcı ise (ga mod p) b mod p denklemini hesaplar çıkan sonuç aynı olacaktır bunun yanında sonucu sadece gönderici ve alıcı biliyor olacaktır. Bu durumda sadece iki kişinin bildiği bu anahtarla veriler şifrelenirken ve çözülürken bu anahtar kullanılacak dolayısıyla anahtar değişmiş olacak.

4) Geri Yayılım Algoritması

Geri yayılımdan bahsetmeden önce bu algoritmanın üzerinde çalıştığı yapay sinir ağlarından (artifical neural network) bahsetmek faydalı olacaktır. Bilgisayarlar, matematiksel olarak modellenmiş problemleri insanlardan daha hızlı ve verimli bir şekilde çözebilmektedirler. Fakat günlük hayatta karşılaştığımız her problem bilgisayarların anlayacağı matematiksel biçimde modellenemeyeceği için bazı verimsiz durumlar ortaya çıkmaktadır. Örneğin, sokakta gördüğümüz bir hayvanın kedi veya köpek mi olduğunu kapsayan bir sınıflandırma probleminde neredeyse bütün insanlardan verimsiz ve yavaş olduğu söylenebilir. Yapay sinir ağları bu verimsizliği ortadan kaldırmak için geliştirilmiştir. İnsan beyninin çalışmasını taklit eden bir yapısı vardır. İnsanlarda bulunan nöronların ve sinapsislerin bilgiyi alıp beyne iletmesine benzer bir ağ yapsısı oluşturulmuştur.

Sokakta görülen hayvanın kedi mi veya köpek mi olduğuna karar verilen bir problem düşünelim.

Giriş katmanından (input layer) alınan veriler kulak uzunluğu, bacak uzunluğu nasıl yürüdüğü boyu gibi veriler olabilir. Çıkış katmanını (output layer) da kedi veya köpek karalarından birisi olarak düşünebiliriz. Aradaki gizli katmanlar (hidden layers) ise toplanan bu verilen diğer nöronlara iletip iletmeme kararının verildiği ve içinde bu kararın verilmesi için bir fonksiyonun bulunduğu katmandır. Eğer gelen veriler belli bir eşik değerini geçerse diğer nörona aktarılacak. Burada önemli olan kısım her nöronun aynı ağırlıkta (weight) olmaması durumudur. Örneğin parmak ucumuz iğne batırdığımızda duyulan acı ile daha sert bir yere batırıldığında duyulan acı aynı değildir. Bu ağırlıkları da hesaba katarak bir değer oluşturulur. Karar olarak olasılığı en yüksek olan seçilecektir. Bu durumda yanlış karar verme durumları oluşabilir. Geri yayılım (backpropagation) burada devreye girmektedir. Ağda bulunan hata miktarı gizli katmanlarda bulunan nöronlara geri döndürülerek modelin başarısının artması sağlanır. Geri yayılım, modeldeki ağırlıkları güncelleyerek hata miktarını azaltmaya çalışır.

Geri yayılımın arkasındaki matematik ise gradyan azalma (gradient descent) ile yapılır. Sinapsisler üzerindeki değişimi veren formül hatanın mevcut ağırlık değerinin türevi ile adım boyunun (step size) çarpılması ile elde edilir. Buradaki amaç doğru ağırlıkları bulmak için global minimum değerinin türev yardımıyla bulunmasıdır.

5) PageRank Algortiması

Şimdi bahsedeceğimiz algoritma biz fark etmesek bile Google Arama Motorunu her kullandığımızda karşımıza çıkıyor. Larry Page ve Sergey Brin, Google’da bulunan siteleri indekslemek ve sıralamak için bu algoritmayı oluşturmuştur. Google sitelerin değerine göre 0-10 arası bir pagerank değeri verir. Bu değer sitenin sahip olduğu özgün içeriğe, siteye verilmiş bağlantılara ve bu bağlantıların kalitesine bağlıdır. Eğer sitenizde bulunan içerik ve linklerin kalitesi yüksekse daha fazla bir pageranke sahip olursunuz. Bu da sitenin görünürlüğünü artıracaktır.

Algoritma basit bir mantığa dayansa bile bugünün önemli kavramlarından olan arama motoru optimizasyonun (SEO) bu algoritma etrafında gelişmiştir. PageRank artık Google tarafından indeksleme ve sıralama için kullanılan 200 algoritmadan birisi olsa da bu algoritmaların arkasındaki temel yapı konumundadır.

Kaynak:

► Aytekin, A., ÇAKIR, F. S., Yücel, Y. B., & Kulaözü, İ. (2018). ALGORİTMALARIN HAYATIMIZDAKİ YERİ VE ÖNEMİ. Avrasya Sosyal ve Ekonomi Araştırmaları Dergisi, 5(7), 143-150.

► İnterestinengineering.com

► bilgisayarkavramlari.com

► geeksforgeeks.org