Programlama dünyasında dışarı çıkmak ve bir miktar para kazanmak istiyorsanız, programcıların yaşam algoritmaları ve veri yapıları en önemli konudur. Bugün, yaptıklarını ve en basit örneklerle nerede kullanıldıklarını göreceğiz. Bu liste, rekabetçi programlamada ve güncel gelişim uygulamalarında kullanımlarını göz önünde bulundurarak hazırlanmıştır.1. Sıralama Algoritmaları (Sort Algorithms)
Sıralama, Bilgisayar Bilimlerinde en çok çalışılan konsepttir. Fikir, bir listenin öğelerini belirli bir sırayla düzenlemektir. Her büyük programlama dili yerleşik sıralama kitaplıklarına sahip olsa da, nasıl çalıştığını biliyorsanız kullanışlı gelir. İhtiyaca bağlı olarak bunlardan herhangi birisini kullanmak isteyebilirsiniz.
Birleştir Sırala (Merge Sort)
Hızlı sıralama (Quick Sort)
Kepçe Sırala (Bucket Sort)
Yığın sıralamasını (Heap Sort)
Sıralama Sayımı (Counting Sort)
Daha da önemlisi, bunları ne zaman ve nerede kullanacağını bilmelisiniz. Sıralama tekniklerinin doğrudan uygulamasını bulabileceğiniz bazı örnekler şunları içerir:
E-ticaret web sitelerinde fiyata göre sıralama, popülerlik vb.
2. Arama Algoritmaları (Search Algorithms)
İkili Arama (Binary Search ); (doğrusal veri yapılarında)
İkili arama, sıralanmış veri kümesi üzerinde çok etkili bir arama yapmak için kullanılır. Zaman karmaşıklığı O (log2N) ‘dır. Fikir, mümkün olan bir öğeye indirgeyene kadar, öğenin içerebileceği bölümün bölümünü tekrar tekrar bölmektir. Bazı uygulamalar şunlardır:
Şarkıların sıralanmış bir listesinde bir şarkı adı aradığınızda, sonuçları hızlı bir şekilde döndürmek için ikili arama ve dize eşleme gerçekleştirir.
Git’te git bisect ile hata ayıklamak için kullanılır
Derinlik / Genişlik İlk Arama ( Derinlik / Genişlik İlk Arama); (Grafik veri yapılarında)
DFS ve BFS, veri yapılarını gezen ve araştıran ağaç / grafiktir. DFS / BFS’nin nasıl işlediğine derinlemesine inanıyoruz ancak aşağıdaki animasyonla bunların farklı olduğunu göreceğiz.
Uygulamalar alanları:
Arama motorları tarafından web taraması için kullanılır.
Yapay zekada botlar oluşturmak için kullanılır, örneğin bir satranç botu.
Haritadaki iki şehir arasındaki en kısa yolu bulma ve diğer pek çok uygulamada.
3. Takma (Hashing)
Hash lookup şu anda anahtar veya kimlik bilgilerini kullanarak uygun verileri bulmak için en yaygın kullanılan tekniktir. Verilere endeksiyle erişiyoruz. Daha önce dizin aramak için Sıralama + İkili Arama’ya güveniyorduk, şimdi karma kullanıyoruz.
Veri yapısı, tuşları değerleri verimli bir şekilde haritalayan Hash-Map veya Hash-Table veya Dictionary olarak adlandırılır. Tuşları kullanarak değer aramaları gerçekleştirebiliriz. Fikir, anahtar -> değer eşleştirmesini yapan uygun bir karma işlevi kullanmaktır. İyi bir karma fonksiyon seçmek senaryoyla ilgilidir.
Uygulamalar alanları:
Yönlendiricilerde IP adresini saklama -> Yönlendirme mekanizmaları için Yol çifti gibi.
Bir listede bir değerin olup olmadığını kontrol etmek için. Doğrusal arama pahalı olurdu. Bu işlem için Set veri yapısını da kullanabiliriz.
4. Dinamik Programlama (Dynamic Programming)
Dinamik programlama (DP), karmaşık bir sorunun daha basit alt problemlere bölünmesiyle çözülmesinin bir yöntemidir. Alt problemleri çözer, sonuçlarını hatırlar ve bunları kullanarak karmaşık problemi çabucak çözmek için yol gösterir.
5. Karekötik ile üstelleşme (Exponentiation by squaring)
232’yi hesaplamak istediğinizi söyleyin. Normalde 32 kez tekrar edip sonucu buluruz. Sana 5 tekrarlamada yapılabileceğini söylersem ne olur?
Karekötik kullanarak üstelleştirme veya İkili üstelleştirme, O (log2N) cinsinden bir sayıdaki büyük pozitif tamsayı güçlerin hızlı bir şekilde hesaplanması için genel bir yöntemdir. Sadece bu değil, yöntem de polinomların ve kare matrislerin güçlerinin hesaplanması için kullanılır.
Uygulama alanları:
Bir sayıdaki büyük güçlerin hesaplanması çoğunlukla RSA şifrelemesinde gereklidir. RSA aynı zamanda ikili üslup ile birlikte modüler aritmetik kullanır.
6. Dizgi Eşleştirme ve Ayrıştırma (String Matching and Parsing)
Desen eşleştirme / arama, Bilgisayar Bilimlerinde en önemli sorundur. Konuyla ilgili çok araştırma yaptık, ancak herhangi bir programcı için yalnızca iki temel gereksinimi isteyeceğiz.
KMP Algoritması (Dize Eşleştirme); (KMP Algorithm (String Matching)
Knuth-Morris-Pratt algoritması, kısa bir desen uzun bir dizede eşleştirmeniz gereken durumlarda kullanılır. Örneğin, bir dokümanda bir anahtar kelime Ctrl + F olduğunda, dokümanın tamamında desen eşleme yaparız.
Düzenli İfade (Dizge Ayrıştırma); (Düzenli İfade (Dizge Ayrıştırma)
Çoğu zaman, önceden tanımlanmış bir kısıtlama üzerinde ayrıştırma yaparak bir dizeyi doğrulamamız gerekir. Web geliştirme sırasında URL ayrıştırma ve eşleme için yoğun bir şekilde kullanılır.
7. Birincilite Test Algoritmaları (Primality Testing Algorithms)
Belirli bir numaranın asal olup olmadığını belirlemenin deterministik ve olasılık yolları vardır. Hem deterministik hem de olasılıksal (nondeterministik olmayan) yolları göreceğiz.
Eratosthenes’in eleği (deterministik); Sieve of Eratosthenes (deterministic)
Sayıların sınırı konusunda belirli bir sınırımız varsa, 100 – 1000 aralığındaki tüm asal sayıları belirlerseniz elek bir yol olur. Aralığın uzunluğu önemli bir faktördür, çünkü aralığa göre belirli miktarda bellek tahsis etmek zorundayız.
Herhangi bir sayı n için, sqrt (n) (deterministik) kadar aşamalı olarak sınama,
Seyrek olarak uzun bir aralıkta (örneğin 1 ila 1012 arasında) yayılmış az sayıyı kontrol etmek istiyorsanız, Elek yeterli miktarda bellek tahsis edemez. Her sayı için yalnızca sqrt (n) ‘yi aşarak ve n’de bir bölünebilirlik kontrolü yaparak kontrol edebilirsiniz.
Fermat birinci derece testi ve Miller-Rabin ilkel testi (her ikisi de nondeterministik değildir)
Bunların her ikisi de kompozitlik testleri. Bir sayı bileşik olarak kanıtlanırsa, o zaman emin bir asal sayı değildir. Miller-Rabin, Fermat’ınkinden daha sofistike bir üründür. Infact, Miller-Rabin’in deterministik bir değişkeni vardır, ancak daha sonra zaman karmaşıklığı ile algoritmanın doğruluğu arasındaki bir ticaret oyunu.
Uygulama alanları
Asal sayıların tek en önemli kullanımı Kriptografide. Daha doğrusu, Public Key Cryptosystems’in ilk uygulaması olan RSA algoritmasında şifreleme ve şifre çözmede kullanılırlar.
Diğer bir kullanım, Hash Tablolarında kullanılan Hash işlevleridir.