Her Yazılımcının Mutlaka Bilmesi Gereken Yazılım Algoritmaları

Her Yazılımcının Mutlaka Bilmesi Gereken Yazılım Algoritmaları

Bilgiye ulaşmayı sağlayan arama motorlarından her an her yerde bağlantıda tutan sosyal medya platformlarına kadar birçok sisteme yazılım algoritmaları güç veriyor. Peki bu algoritmalar tam olarak ne ve neden bu kadar önemli? İster junior ister senior ol her yazılımcının mutlaka bilmesi gereken algoritmalara ve örnek uygulamalarına bir göz atmak isteyebilirsin.

Yazılımda Algoritma Nedir?

En genel anlamıyla bir yazılım algoritması sorunları çözmek, görevleri tamamlamak üzere kullanılan prosedürlerin kademeli halini uygun şekilde uygulayan ve sonuç alınmasını sağlayan sistemlerdir. Algoritmalar iki sayıyı toplamak için kullanılabileceği gibi daha karmaşık olarak machine learning modellerini eğitirken de görev alabilir. Algoritmalardan yoksun bilgisayar sistemleri birçok komutu yerine getiremeyebilir, işlemleri etkili ve verimli şekilde sonuçlandırmaktan oldukça uzak birer nesne haline gelebilirdi. O halde junior veya senior ayırt etmeksizin her yazılımcının mutlaka bilmesi gereken yazılım algoritma mantığı örneklerine ve çözüm uygulamalarına bir göz atalım.

En Popüler Yazılım Algoritmaları

Time Complexity (Büyük O Gösterimi)

Zaman karmaşıklığı olarak da bilinen Time Complexity, belirli bir algoritmanın verimliliğini ölçmeyi ve karşılaştırma yapmayı sağlar. Time Complexity aşağıdaki gibi çalışır:

Geleneksel birimler yerine hesaplama adımları kullanır. Bir algoritmanın hız ve girdi boyutu olmak üzere verimliliğini etkileyen iki faktör bulunur. Algoritmanın verimliliği dış faktörlerden büyük ölçüde etkilenmemiş olsaydı hız, dakika ve saniye cinsinden ölçülebilirdi. Bununla birlikte günümüzde donanım ve teknoloji eskisinden çok daha hızlı hale geldiğinden geleneksel zaman birimleriyle ölçüm pek tercih edilmez. Bunun yerine aritmetik toplama-çıkarma yada karşılaştırma gibi temel hesaplama birimini temsil eden hesaplama adımları kullanılır.

Algoritma girdi olarak veri kullanır ve girdi boyutu değiştikçe algoritmanın verimliliği ölçülebilir. Küçük girdi boyutları için algoritmanın kullanım kolaylığı hızından daha önemli hale gelir. Çünkü bu girdi aralığındaki faydalar ihmal edilebilir düzeydedir.

Algoritmaları girdi boyutlarına ve hızlarına göre sınıflandırmak için kullanılan Büyük O Gösterimi ile yüksek değerlerdeki hızlar karşılaştırılır. Bunun nasıl çalıştığını görmek için gerçekleştirilecek işlem sayısının hesaplandığı bir formül örneğini şu şeklide açıklamak mümkündür:

T(N)=\dfrac{1}{2}N^2 + 3N + 7

N sonsuza yaklaştıkça denklemdeki baskım terim N^2 olur, bu nedenle algoritmanın zaman karmaşıklığının O(N^2) olduğu söylenebilir. Bununla birlikte çeşitli karmaşıklık sınıfları mevcuttur. Üç tanesi ele alınacak olursa:

1 - P, polinom zamanda veya O(n^c)’de çözülebilen karar problemleri sınıfını temsil eder. Bu problem sınıfı klasik bilgisayarlarda çözülmesi kolay olan problem sınıfıdır.
2 - EXP, üstel zamanda veya O(2^{n^c}) çözülebilen karar problemleri kümesini içerir. Bu sınıf problemlerini klasik bilgisayarlarda çözmek zordur ancak kuantum bilgisayarlarda polinom zamanda çözülebilecek algoritmalar mevcut olabilir.
3 - R, sonlu zamanda çözülebilen tüm problemleri temsile eder. P, EXP ve R sınıfları mevcut tüm problemlerin küçük bir kısmını içerir.

Search Algorithms (Arama Algoritmaları)

Arama algoritmalarının amacı bir değerler dizisini incelemek ve liste içinde istenen değerin konumunu veya indeksini en uygun hızda bulmaya çalışmaktır.

Doğrusal Arama
N elemanlı rastgele ve sırlanmamış bir dizi verildiğinde algoritma dizideki bir x değerinin indeksini döndürür. Tüm arama algoritmalarının en az kullanılanı, programın aradığını bulana kadar tüm dizi değerleri üzerinde tek tek kapsamlı bir arama gerçekleştirdiği doğrusal aramadır.

Doğrusal arama karmaşıklığında algoritma, ortalama olarak bir dizideki değerlerin yarısını ve en kötü ihtimalle tüm değeleri inceler. Hesaplama karmaşıklığı O(N)’dir.

İkili Arama
N elemanlı rastgele sıralanmış bir dizi verildiğinde algoritma dizideki bir x değerinin indeksini döndürür. İkili arama, arama alanını böl ve fethet yöntemiyle daraltmak için dizinin sıralanmış düzeninden yararlanır. İkili arama şu şekilde çalışır:

• Adım 1: Dizinin ortadaki elemanını inceler ve aranılan elemanla karşılaştırır.
• Adım 2: Eşleştiğinde algoritma bu değeri döndürür ve durur.
• Adım 3: Aksi halde değer daha küçükse Adım 1 tekrarlanır.

İkili arama karmaşıklığı en kötü senaryoda diziyi k kez ikiye bölmek zorunda kalır.

N=2^k olduğunda;

log(N)=log(2^k)=k

Bu nedenle zaman hesaplama karmaşıklığı O(log(N)) olarak hesaplanır.

Grover Algoritması
Grover algoritması arama problemini sıralanmamış N elemanlı bir dizide çözmeye çalışır ancak yaklaşımı kökten farklıdır. Bu senaryoda bir kuantum işlemcisi ile aramanın yürütülmesi için kuantum algoritması kullanılır.

Sıralanmamış bir dizi için tek seçenek kaba kuvvet arama yöntemidir ve klasik bir sistemde ortaya çıkan zaman karmaşıklığı O(N)’dir. Kuantum süperpozisyon, dolaşıklık ve girişimden yararlanarak hesaplama karmaşıklığını O(√N) değerine düşürebilir. Bir genlik yükseltici kuantum operatörü kullanılarak daha da düşük bir değere; O(√1) düşürülebilir.

Bu sonuca ulaşmak için öncelikle problem, içinde ‘oracle’ bulunan bir kutu olarak yeniden formüle edilir. Kuantum bir sistemi temsil eden bu kutuda bulunan oracle her sorgulandığında ikili yanıt alınır. Soru şu şekildedir: ‘Kutudaki sayı 15 mi?’. Eğer kutu sorgulanan sayıyı içeriyorsa cevap doğrudur.

Özetlenecek olursa Grover kuantum algoritmasının çalışma şekli aşağıdaki gibidir:

• Adım 1: Kutunun içerebileceği olası sayı aralığını kapsayacak kadar kübit yaratılır. Örneğin gizli sayı [0-8] ise, 8 = 2^3, bu durumda üç kübit gerekir.
   
• Adım 2: Tüm kübitlerin kuantum süperpozisyonunu oluşturmak için Hadamard gates yani klasik sitemin boolean veya kuantum analogları kullanılır. Bu süperpozisyon olası tüm girdi değerlerinin tek seferde hesaplanmasını sağlar. Böylelikle üç kübit yerine bu kübitlerin alabileceği tüm olası değerlerin süperpozisyonundan oluşan tek bir kuantum girdi sistemi elde edilir (000, 001, 010, 011).
   
• Adım 3: Girdi Kontrollü-Z geçidinden geçirilir ve bu geçit ile oracle simüle edilir. Bir Kontrollü-Z kapısı giriş (1, 1) ise işaretini çevirir, aksi durumda girişi değiştirmeden bırakır. Bu nedenle bu adımda gizli sayı (1, 1)’dir.
   
• Adım 4: Bu bir kuantum sistemi olduğundan sonunda ölçümü yapılan herhangi bir cevap alınabilir. Ancak kübitleri ölçülen doğru cevabın (1, 1) ortaya çıkma olasılığı daha yüksektir.
   
• Adım 5: Bu adım iki seçenekten oluşur. Hesaplamayı birden çok kez yapılır ve genellikle olasılıkları yükselten bir genlik yükseltici (yansıma operatörü) kullanılır. Böylecek en olası sonucun ilk çalıştırmada ortaya çıkma şansı yüksek olur.

Sorting Algorithms (Sıralama Algoritmaları)

Sıralama algoritmaları N adet rastgele sayıdan oluşan bir dizinin elemanlarını artan sırada yeniden düzenler. Algoritmalar, en düşük çalışma zamanı ve bellek kullanımı karmaşıklığı için çalışır.

Ekleme Sıralaması
Ekleme sıralaması sezgisel ancak maliyetli bir sıralama algoritmasıdır, tüm dizi üzerinde N adede kadar geçiş yaparak çalışır. Algoritma, her geçişte 1'den N'ye kadar olan öğeleri inceler ve bunları sollarındaki ile karşılaştırır. Eğer sayı sol komşusundan daha küçükse değiştirilirler. Bu karşılaştırma ve değiştirme bir dalga gibi sola doğru hareket eder, yalnızca sağdaki sayı soldakinden büyük olduğunda durur.

Ekleme sıralamasının zaman karmaşıklığı O(N^2)'dir. Çünkü her geçişte en fazla N eleman kadar N geçişi bulunur.

Birleştirme Sıralaması
Birleştirme sıralaması, iki öğeli bitişik alt dizilere soldan sağa doğru özyinelemeli şekilde çalışır. Önce 1-2 elemanları sıralanır ardından 3-4'e geçilir. Sonrasında 5-6 eklenmeden önce 1-2-3-4 elemanları sıralanır. Sıralama, dizinin sonuna ulaşılana kadar bu şekilde devam eder. Birleştirme sıralamasının zaman karmaşıklığı O(N log N)’dir.

Böl ve yönet adımı, uzunluğu N/2->2 arasında değişen iki alt diziyi özyinelemeli olarak sıralar. İkili Aramada’da gösterildiği gibi bu işlemin maliyeti O(log N)’dir. Birleştirme adımı N elemanı birleştirir ve böylece O(N) maliyetine neden olur. Bu durumda toplam maliyet O(N log N) olur.

Quicksort
Quicksort, pivot kavramını kullanan bir başka böl ve yönet algoritmasıdır. Pivot, dizideki bir elemandır (genellikle sonuncu). Aşağıdaki gibi çalışır:

• Adım 1: Algoritma, solundaki tüm elemanlar daha küçük, sağındakiler daha büyük olana kadar pivotu sola doğru hareket ettirir.
   
• Adım 2: Dizi, pivottan önceki tüm elemanlardan oluşan bir sol, pivotun sağındaki tüm elemanlardan oluşan sağ olmak üzere iki bölüme ayrılır.
   
• Adım 3: Adım 1, bir segment yalnızca iki sırlanmış öğe içerene kadar her iki segmentte de tekrarlanır.

Quicksort’un zaman karmaşıklığı pivot seçimine duyarlıdır. Örneğin dizi zaten sıralanmışsa ve pivot son eleman olarak seçilirse algoritmanın {N—1, N—2,…} tüm alt dizinleri incelemesi gerekecektir. Algoritmanın pivot seçimine olan hassasiyetini en aza indirmek için çeşitli Quicksort varyantları mevcuttur. Birleştirme sıralamasının zaman karmaşıklığı mümkün olan en iyi senaryoda O(N log N), en kötü senaryoda ise O(N^2)'dir.

Graph Algorithms

Bir grafik kenarları ve köşeleri ile tanımlanır: G={V, E}. Kenarlar, mevcut kenar boyunca hareket etmenin maliyetini temsil eden negatif ve pozitif sayılarla ağırlandırılabilir. Bununla birlikte bir yöne de sahip olabilirler.

Kruskal Algoritması

V köşeli ve E ağırlıklı, negatif olmayan kenarlı bir G={V, E} grafiği verildiğnde G içinde bir minimum yayılan ağaç bulunur. Minimum yayılan ağaç G’deki tüm köşeleri ve E kenarlarının bir alt kümesini içeren bir graftır.

Minimum yayılan ağacı bulmak için uygulanan algoritma şu şekildedir:

• Adım 1: Ağırlıklarına göre artacak şekilde sıralanmış tüm kenarların bir listesi yapılır.
   
• Adım 2: En üstteki kenar ve köşeler minimum yayılan ağaca eklenir.
   
• Adım 3: liste boyunca yineleme yapılır ve ilgili kenarın köşeleri incelenir.

Seçim algoritmasında yapılan ekleme işleminde eşit ağırlıklı iki kenar arasında seçim yapılması gerektiğinden minimum maliyetli birden fazla yayılan ağaç bulunabilir.

Kruskal algoritması, kenarları artan ağırlıklara göre sıralamak için gereken süre artı minimum yayılan ağacı oluşturmak için gereken süre olan O(E log E) yani O(E log V)’de çalışır.

Dijkstra Algoritması

V köşeli ve E ağırlıklı negatif olmayan kenarlı bir G={V, E} grafiği verildiğinde S ve E olmak üzere iki belirlenmiş köşe arasındaki en kısa yol bulunur.

Uygulanan ilk algoritma S’den E’ye giden tüm farklı yolların kapsamlı bir araştırmasını yapar, S kök düğümü ve E yapraklı olan bir ağaç oluşturur. Bu arama stratejisi, dallar arasında arama yaparken biriktirilen bilgileri dikkate almadığı için optimal değildir. Örneğin başlangıç ve A köşelerini birleştiren P1 ve P2 olmak üzere iki yol varsa P1’in maliyeti 11 iken P2’ninki 15 ise, P2’yi kullanan herhangi bir yolun P1’i kullanan herhangi bir yola göre daha az optimal olduğunu sonucu çıkarılabilir. Dijkstra algoritması bu bilgiden yararlanmak için S ile G’deki diğer her tepe noktası arasındaki en iyi rotayı kaydeder.

Dijkstra'nın algoritması grafik üzerinde birkaç iterasyon çalıştırır. Her yeni iterasyon S ile incelenen düğümler arasındaki en kısa mesafeyi takip ederken bir önceki turdan ulaşılabilen komşu düğümleri araştırır. Daha kısa bir yol denemek istersen izleme tablosunu güncelledikten sonra bir sonraki yinelemede aşağıdaki adımları izleyebilirsin.

• Adım 1: Tüm mesafeler (başlangıç düğümü hariç) sonsuza başlatılır; d(start)=0, d(V_i)=\infty. Karmaşıklık O(V)’dir.
   
• Adım 2: Başlangıçta boş olan bir dış liste tutulur. Karmaşıklık O(1)’dir.
   
• Adım 3: Minimum maliyetli V_{j, min} ve dış listede olmayan düğüm seçilir.

Karmaşıklık O(V): V_{j, min}'i bir dış liste eklenir. Böylece bir sonraki turda tekrar ziyaret edilmez, O(1). Mevcut V_{j, min} düğümü ile komşuları arasındaki en kısa mesafeyi bularak tüm komşu düğümleri açılır. Karmaşıklık O(E) 'dir. V_i üzerinden V_{j, min} tepe noktasına daha kısa bir mesafe varsa, d(V_{j, min}) = d(V_i) +cost(V_iV_j) olarak güncellenir, O(1). Tüm düğümler dış listede olana kadar Adım 3 tekrarlanır.

Dijkstra'nın algoritması tüm V düğümlerini E iterasyonda çözer. Bu durumda O(EV) karmaşıklığı ortaya çıkar.

Algoritmalar, çok çeşitli zorlukların üstesinden gelebilecek güçlü araçlardır. Çeşitli algoritma türlerinin kapsamlı bir şekilde kavranması, mekanizmaları ve temel ilkelerindeki teknik yeterlilikle birleştiğinde yazılım çözümleri yaratma ve sorunları gelişmiş verimlilikle ele alma gücü verir. Yazılım algoritmaları dünyasının derinliklerine inme arayışına başlarken Techcareer.net, başarılı bir yazılım geliştiricisi olma yolundaki yolculuğunu desteklemek için eğitimler ve blog yazıları da dahil olmak üzere bir dizi kaynağa sahiptir. Yazılım algoritmaları dünyasını keşfetmeye ve becerilerini geliştirmeye hazırsan yolun her adımını güvenle atmak için bizi takip etmeye devam et!

Sıkça Sorulan Sorular

Yazılım algoritmaları hakkında daha detaylı bilgiye nasıl ulaşabilirim?

Yazılım algoritmalarını öğrenmek kadar pratikte işine yarayacak seviyede uygulayabiliyor olmak da iş hayatı için sağlıklı bir yatırım olabilir. Algoritmalarla çalışmak ve bu alanda uzmanlaşmak istiyorsan Techcareer.net tarafından düzenlenen bootcamp’leri takip edebilir, sana uyanlara başvuru yapabilirsin.

Bootcamp’lere katılım şartı aranıyor mu? Aranıyorsa bunlar neler?

Her bootcamp kendine özgü gerekliliklere sahiptir. Yine de temel programlama bilgisi, öğrenme ve gelişme için yüksek motivasyon gibi bazı gerekliliklere ihtiyaç duyulabilir. Daha detaylı bilgi için güncel başvuruların bulunduğu bootcamp eğitimleri sayfasına göz atabilirsin.

Hackathon yarışmalarına katılım koşulları nelerdir?

Etkinlik türüne göre Hackathon’lar için de farklı katılım koşulları bulunur. Genel olarak öğrenci veya mezun olman, en az iki kişilik bir ekibin olması, belirli süreli proje çalışmasına yatkın olman gibi gereklilikler söz konusu olabilir. Etkinlikleri daha yakından incelemek için Hackathon etkinlikleri sayfasını ziyaret edebilirsin.

İş ilanlarına başvurmak için hangi nitelikler gerekiyor?

Uzmanlaşmak istediğin alana yönelik olarak her işin belirli gereklilikleri vardır. Örneğin SQL Yazılım Uzmanı pozisyonuna uygun bir adayın nitelikleri arasında T-SQL kodlama tecrübesi veya ön muhasebe ve üretim bilgisi aranırken, Senior PHP Developer pozisyonu için en az 4 yıl Backend geliştirme deneyimine sahip olunması beklenir. Açık pozisyonlar ve işe ait detaylı bilgi için iş ilanları incelemesi yapabilirsin.