Algoritmalar

ALGORİTMALAR

Algoritmalara Giriş

Algoritma, belli bir problemi çözmek veya belirli bir amaca ulaşmak için tasarlanan yol. Matematikte ve bilgisayar biliminde bir işi yapmak için tanımlanan bir başlangıç durumundan başladığında, açıkça belirlenmiş bir son durumunda sonlanan, sonlu işlemler kümesidir. Genellikle bilgisayar programlamada kullanılır ve tüm programlama dillerinin temeli algoritmaya dayanır. Aynı zamanda algoritma tek bir problemi çözecek davranışın, temel işleri yapan komutların veya deyimlerin adım adım ortaya konulmasıdır ve bu adımların sıralamasına dikkat edilmelidir. Bir problem çözülürken algoritmik ve sezgisel olmak üzere iki yaklaşım vardır. Algoritmik yaklaşımda da çözüm için olası yöntemlerden en uygun olan seçilir ve yapılması gerekenler adım adım ortaya konulur. Algoritmayı belirtmek için; metinsel olarak düz ifade ve akış diyagramı olmak üzere 2 yöntem kullanılır. Algoritmalar bir programlama dili vasıtasıyla bilgisayarlar tarafından işletilebilir.

Sıralama Algoritmaları-1

Bu makalemizde en temel ve en basit sıralama algoritmalarından Insertion Sort, Selection Sort ve Shell Sort algoritmalarını öğreneceğiz. Bildiğiniz gibi bilgisayar sistemlerinin ve programlama tarihinin en başından beri sıralama algoritmaları her zaman önemli olmuştur. Birçok önemli algoritmada sıralama algoritmaları kullanılır. Peki bilgisayar sıralama işlemini nasıl yapar. Mesela bir insana verilen üzerinde harfler bulunan karışık kartların sıralamasını istediğimizde önce rastgele bir kart alır. Sonra bir kart daha alır, sonra aldığı kartı ile kartı karşılaştırır ve kartı uygun bir yere koyar. Bütün kartları bu şekilde yaptıktan sonra sıralama işlemi tamamlanır. Bilgisayar sistemleri de genelde sıralama yaparken insanların yaptığı gibi karşılaştırma yapar. Bu makalede göreceğimiz algoritmalar genelde yavaş çalışan algoritmalardır. Bunların yanında Merge Sort, Quick Sort, Heap Sort gibi diğer hızlı algoritmalar da vardır. Ancak bazı algoritmaların da başka dezavantajları vardır.

Insertion Sort (Sıralama)

Bu algoritma insanların sıralama mantığına en yakın olan algoritmadır. Sıralanacak dizi sıralanmış ve              sıralanmamış parçalara ayrılarak her bir eleman sıralanmış parça içinden kontrol edilerek uygun yere yerleştirilir.

Selection Sort (Sıralama)

Bu algoritma birinci elemandan başlayarak son elemana kadar sıralanmış parçayı artırarak işler. Önce dizideki en küçük eleman bulunur ve dizinin ilk elemanı ile yer değiştirilir. Sonraki aşamada sıralanmamış parça içindeki en küçük eleman bulunur ve ikinci elemanla yer değiştirilir. Bu işlemi N defa N eleman için yaptığımızda dizi sıralanmış olacaktır.

Shell Sort (sıralama)

Shell sort algoritması ınsertion algoritmasına benzer ancak bu algoritma daha hızlıdır. Çünkü sıralama işlemini bütün dizi üzerinde değil de diziyi gruplara bölerek yapar. Insertion sort metodunu dizinin belli bölümlerine uyguladığımızda Shell sort algoritmasını elde ederiz.

BFS Algoritması, DFS Algoritması

Graflar

Graf, matematiksel anlamda, tepelerden ve bu düğümler arasındaki ilişkiyi gösteren ayrıtlardan oluşan bir kümedir. Bir G grafı V ile gösterilen tepelerden ve E ile gösterilen ayrıtlardan oluşur. Her ayrıt iki tepeyi birleştirir. Her ayrıt, iki bilgi arasındaki ilişkiyi gösterir ve u-v şeklinde ifade edilir. U-v iki tepeyle gösterilen bir ayrıttır.

BFS Algoritması

BFS Algoritması graflar üzerinde arama algoritmasıdır. Bir noktadan başlayarak diğer tüm düğümleri ziyaret etmeyi hedefler. Mantık olarak en yakındaki düğümleri ziyaret eder, giderek uzaklaşır. DFS’ den temel farkı budur. DFS algoritması gidebileceği yere kadar gider, ondan sonra geri döner. BFS algoritmasında kuyruk veri yapısı kullanılmaktadır.

Prim ve Kruskal Algoritmaları

Prim Algoritmaları

Prim algoritması, minimum spanning tree algoritmalarından biridir. Kenarların bir alt kümesini, tüm düğümleri kapsayacak ve kenarların toplam ağırlığını minimum yapacak şekilde bulur. Bu algoritma 1930 yılında matematikçi Vojtech Jarnik tarafından bulunmuştur. Daha sonra bağımsız olarak 19572 de bilgisayar bilimcisi Robert C. Prim ve 1959’ da Dijkstra tarafından tekrar bulunmuştur. Bu nedenle bu algoritmaya DJP veya Jarnik algoritması da denir.

Kruskal Algoritması

Bir asgari tarama ağacı algoritması olan Dijkstra algoritması, işaretlemiş olduğu komşuluklara en yakın düğümü bünyesine katarak ilerler. Kruskal algoritması her seferinde en iyi kenarın seçilmesi esasına dayalıdır. N kenarlı bir graf için herhangi bir düğümle başlanır ve en kısa yol buna eklenir. Aynı değerli kenarlarda seçim keyfi yapılabilir. Düğümlerin birleştirilme işlemine en az maliyetli kenardan başlanır, kalan kenarlar arasından en az maliyetlisi seçilerek devam edilir.

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

Ünlü algoritmalardan bir tanesidir. En Kısa Yol Algoritması basit bir mantıkla oluşturulmuş ve günümüzde oldukça kullanılan algoritmadır. En Kısa Yol Algoritması’ nın Çıkış noktası farklı düğümlerden en kısa yoldan hedefe ulaşmayı amaçlamaktadır. Bu amaçla günümüzde de internet trafiğinin yönlendirilmesinde, oyun programlamada sıkça kullanılmaktadır. Dijkstra’  nın En kısa Yol

Algoritması sırasıyla şöyledir:

1. Düğümler arasında uzaklık değerleri belirlenmiş olmalı.

2. Bir başlangıç noktası belirliyoruz. Bu başlangıç noktası 0 noktamız.

3. Başlangıç noktasından diğer diğer düğümlerin uzaklıkları hesaplıyoruz. En küçük uzaklığı buluyoruz.

4. En küçük uzaklığı bulduktan sonra daha küçük bir değer bulunduysa yeni bulunan değer kabul edilir.

5. Son düğüme gelene kadar bu işleme devam edilir.

6. Sonunda programımız bize en kısa yolun olduğu düğümleri gösterir.

Bellman Ford Algoritması

Bu algoritmanın amacı, bir şekil üzerindeki, bir kaynaktan bir hedefe giden en kısa yolu bulmaktır. Bu anlamda, literatürde en kısa yol bulma algoritması olarak sınıflandırılabilir. Algoritma ağırlıklı şekiller üzerinde çalışır. Kabaca, bütün düğümler için bütün kenarları dolaşır. Dolayısıyla performansı düğüm sayı ile kenar sayısının çarpımı olarak düşünebiliriz.

Sıkıştırma Algoritmaları

Veri sıkıştırma işlemi, belirli uzunluktaki verilerin çeşitli yöntemlerle daha az bellek kullanılması amacıyla geliştirilmiştir. Bu sayede bellek üzerinde yer tasarrufu, veri aktarımında da zaman tasarrufu yapılabilmektedir. Veri sıkıştırma yöntemleri iki grupta incelenir: Kayıplı ve Kayıpsız sıkıştırma. Kayıplı sıkıştırma daha çok multimedia verilerde kullanılır. Mpeg ve MP3 bunun yaygın örneğidir.MP3’lerde insan kulağının duyamayacağı ses dalgaları kayda alınmaz. Ayrıca JPEG resim sıkıştırma formatında da resim üzerinde belirli ara renk kayıpları olmaktadır. İkinci tip sıkıştırma ise kayıpsız sıkıştırmadır. Özellikle sayısal sonuçların önemli olduğu durumlarda kullanılır. Mesela bir exe dosyayı sıkıştırdığımızda hiçbir verinin kaybolmasını istemeyiz. Çünkü birkaç byte’ ın bile farklı olması exe’nin çalışmamasına yol açabilir. Yukarıda bahsedildiği gibi tüm Multimedia formatları kayıplı değildir. GIF ve PCX formatı kayıpsız olarak sıkıştırma yapabilmektedir.

AVL Tree Algoritması

AVL ağacı, denge şartı olan ikili arama ağacıdır. AVL ağacının ismi ise onu geliştiren Andelson-Velsky ve Landis’in isimlerinin baş harflerinden gelir. Bu veri yapısının önemi ise verimliliğinden kaynaklanmaktadır. Düğüm sayısı n olan bir ağaçta düğüm arama, yeni düğüm ekleme ve düğüm silme işlemlerinin ortalamada ve en kötü durumda O(log n)lik zaman kalır ve ideal ağaca yakındır. İkili arama ağacında her kökün sol çocuğu olan ağaçtaki bütün düğümler kökten küçük, sağdakilerse kökten büyük olmak zorundadır. Bu sayede ikili arama ağacında düğüm arama bir dizide aramaktan daha verimli olur, ortalamada O(log n) zaman alsa da ağaç dengeli bir biçimde dağılmadığı zaman O(n)e yaklaşır. Bu sorunu ortadan kaldırmak için AVL ağacını kullanabiliriz. AVL ağacının önemli işlemleri ağacı dolaşma, yeni düğüm ekleme, düğüm arama, düğüm silme ve ağacı tekrar dengelemek için kullanılan döndürmelerdir.

B Tree Algoritması

B tree binary sıralama ağaçlarının genel adıdır. Genel olarak arama işleminde daha hızlı sonuç vermesine karşın ekleme ve silme daha yavaştır. Kayıtların sayısı capacity order la orantılıdır.   B Tree, ağaç şeklinde dinamik bir veri yapısıdır. Nodlar ve nod içindeki sıralı elemanlardan oluşur. Kök noddan başlayarak; her bir elemanın küçük değerleri sola doğru, büyük değerleri ise, sağa doğru, alt kod üzerinde ter almaktadır. Her bir eleman ile birlikte alt noda ait referansı da saklamaktadır. Anahtar bilgilerde mükerrerliğe izin verilmemiştir.

B + Tree Algoritması

B+ ağacı, sıralanmış halde bulunan veriye yeni veri eklerken, bu veriden eksiltilme yaparken veya sadece veriye ulaşmak istediğimizde hızlı ve verimli bir şekilde ulaşmak için sıkça tercih edilen, indeksleme amacıyla kullanılan bir ağaç yapısıdır. İndeksleme her bir veride bulunan ve sadece o veriye özel olan bir değeri seçerek yapılır. Bu değere anahtar denir. B+ ağaçları sahip olduğu verilerin ya da anahtarların sayısına bağlı olarak büyüyüp küçülebilir. Bu yüzden dinamik yapıya sahip olan B+ ağaçlarının yüksekliği değişkendir; ancak ağaca ekleme ve çıkarma yaparken kullanılan algoritmaların dizâyn dolayısıyla tüm yapraklar aynı yüksekliktedir ve bütün kayıtlar yaprak yüzeyinde tutulur. Sadece anahtarlar yaprak olmayan noktalarda tutulur. B+ ağaçlarının her bir indeks paçasındaki anahtar sayısı bir maksimum ve bir minimum değer ile sınırlandırılmıştır. Bu minimum sayıya ağacın derecesi denir ve bir düğümde bulunabilecek maximum anahtar sayısı minimum anahtar sayısının iki katıdır.