Video: The Secret step-by-step Guide to learn Hacking 2024
John Paul Mueller, Luca Massaron, Algoritmaların sıkıcı ya da zor kullanılması gerekmiyor. Aslında, algoritmalar sizi düşünmemiş olabileceğiniz birçok yönden kuşatır ve bunları önemli görevleri yerine getirmek için her gün kullanırsınız. Bununla birlikte, bir matematikçi olmaksızın algoritmaları kullanabilmeniz gerekir.
Programlama dilleri, bir algoritma oluşturmak için kullanılan adımları tanımlamanıza izin verir. Bazıları, bilgisayar görevlisi olmadan insanların anlayabileceği şekilde bu görevi yerine getirirken diğerlerinden daha iyidir. Python, algoritmaları daha kolay kullanır; çünkü (paketlerin, veri kümelerinin ve diğer kaynakların kullanımı yoluyla) yerleşik ve genişletilmiş bir çok destek ile birlikte gelir. Bu Cheat Sheet, algoritmaları hızlı ve kolay bir şekilde kullanmak için en sık ihtiyaç duyulan ipuçlarına erişmenize yardımcı olur.
İhtiyacınız olan Algoritmanın Bulunması
Aşağıdaki tabloda, çeşitli veri analizi türleri için yararlı olabilecek algoritmalar ve algoritma türleri açıklanmaktadır. (Tüm bu algoritmaların tartışmalarını Algoritmalar için Aptallar bölümünde bulabilirsiniz.)
Algoritma | Açıklama | Yardımcı Bağlantı |
A * Arama | Algoritma, düğümlerin maliyetini, denklem: f (n) = g (n) + h (n), burada:
n düğüm tanımlayıcısıdır
g (n) şu ana dek düğüme ulaşmanın maliyetidir h (n) düğümündeki hedef f (n), n'den hedefe kadar olan yolun tahmini maliyetidir. Fikir, en umut vadeden yolları aramak ve pahalı yollardan kaçınmaktır. |
Stanford. edu |
Dengeli Ağaç | Yeniden örgütlenerek dengeli bir yapıya sahip olan, daha düşük erişim süreleri sağlayabilen bir ağaç türü. Sol taraftaki öğe sayısı, sağdaki sayı ile birer birer değişir. | Webdocs |
İki Yönlü Arama | Bu teknik, iki arama yolu ortada buluşuncaya kadar, aynı anda kök düğümden ve hedef düğümden arar. Bu yaklaşımın bir avantajı, çözümün diğer pek çok kaba kuvvet çözümüne göre daha hızlı bulunması nedeniyle zamandan tasarruf sağlamasıdır. Buna ek olarak, bellek diğer yaklaşımlardan daha verimli kullanır ve daima bir çözüm bulur. Başlıca dezavantaj, uygulanmanın karmaşıklığıdır. | Planlama. cs |
İkili Ağaç | Bu, sıfıra (yaprak düğüm), bir veya iki (dallanma düğümleri) diğer düğümlere bağlanan düğümleri içeren bir ağaç türüdür. Her düğüm, veri depolama, sol bağlantı ve sağ bağlantı olmak üzere bağlantı sağlamak ve veri depolamak için içermesi gereken üç öğeyi tanımlar. | cs. cmu. edu |
Genişlik İlk Arama | Bu teknik kök düğümden başlar, önce alt düğümlerin her birini araştırır ve ancak daha sonra bir sonraki seviyeye iner. Bir çözüm bulana kadar seviyeye kadar ilerleme kaydedilir. Bu algoritmanın dezavantajı her düğümün bellekte saklanmasıdır, bu da çok sayıda düğüm için hatırı sayılır miktarda bellek kullandığı anlamına gelir. Bu teknik, zaman kazandıran yinelenen düğümleri kontrol edebilir ve her zaman bir çözüm getirir. | Han Academcy |
Brute Force | Bu, birisinin, mümkün olan her çözümü en iyi problem çözümünü aramaya çalıştığı bir problem çözme tekniğidir. Kaba kuvvet teknikleri varolduğunda en uygun çözümü garanti eder, ancak insanların çoğundan kaçınmak için zaman alıcıdır. | IgM. univ |
Derinlik İlk Arama | Bu teknik kök düğümden başlar ve bir yaprak düğümüne ulaşana kadar bağlı alt düğüm kümesini inceler. Bir çözüm bulana kadar şube ile şubeyi ilerletir. Bu algoritmanın dezavantajı, yinelenen düğümleri kontrol edememesi, bu da aynı düğüm yollarını bir kereden fazla geçirebileceği anlamına gelir. Aslında, bu algoritma hiç bir çözüm bulamayabilir, yani algoritmanın sonsuza kadar arama yapmasını önlemek için bir kesme noktası tanımlamanız gerekir. Bu yaklaşımın bir avantajı, hafızanın verimli olmasıdır. | Hacker Earth |
Böl ve Bölün | Bu, problemin mümkün olan en küçük parçalara ayrıldığı ve mümkün olan en basit yaklaşımla çözüldüğü bir problem çözme tekniğidir. Bu teknik kaba kuvvet gibi diğer yaklaşımlarla karşılaştırıldığında önemli zaman ve kaynak tasarrufu sağlar. Bununla birlikte, her zaman en uygun sonucu garanti etmez. | Khan Academy |
Dijikstra | Bu, yönlendirilmiş, ağırlıklı (pozitif ağırlıklı) grafikte en kısa yolu bulmak için kullanılan bir algoritmadır. | Geeks İçin Geeks |
Grafik | Bir grafik, bir çeşit ağaç uzantısıdır. Ağaçlarda olduğu gibi ilişkiler oluşturmak için birbirine bağlanan düğümleriniz var. Bununla birlikte, ikili ağaçların aksine, bir grafik birden fazla veya iki bağlantıya sahip olabilir. Aslında, grafik düğümleri genellikle çok sayıda bağlantıya sahiptir. GPS haritaları gibi yerlerde kullanılan grafikleri ve bir ağacın yukarıdan aşağıya yaklaşımı çalışmayacağı diğer her türlü yeri görürsünüz. | Öğreticiler |
Açgözlü Algoritma | Çözümün problem çözme sürecinin her adımında en iyi cevaba dayandığı bir problem çözme tekniğini. Açgözlü algoritmalar genellikle iki varsayım yapar:
Belirli bir aşamada tek bir optimal seçim yapmak mümkündür. Her adımda en uygun seçimi seçerek genel sorun için en uygun çözümü bulmak mümkündür. |
Öğreticiler |
Açgözlü En İyi İlk Arama (BFS) | Algoritma her zaman denklemi kullanarak hedefe en yakın yolu seçer: f (n) = h n). Bu özel algoritma çözümleri oldukça çabuk bulabilir ancak aynı zamanda döngüler içinde sıkışabilir, bu yüzden birçok kişi bunu bir çözüm bulmak için en uygun yaklaşım olarak düşünmüyor. | Centurion2 |
Hashing | Bu, veri yapısında belirli bir veri maddesinin konumunu (gerçekte ne olursa olsun bu yapı olabilir) tahmin etmeden önce tahmin etmenin bir yöntemidir. Bu yaklaşım, bir dizine yerleştirilen tuşların kullanılmasına dayanır. Bir karma işlevi anahtarı, algoritmanın bir karma tabloya yerleştirdiği sayısal bir değere dönüştürür. Karma tablo, bir veri yapısında bulunan öğelere işaret eden bir dizin oluşturmanın yollarını sağlar; böylece bir algoritma, verilerin konumunu kolayca tahmin edebilir. | Öğreticiler |
Öbek | Bu, ağaç yapısına veri eklemeye izin veren sofistike bir ağaçtır. Veri ekleme kullanımı, sıralama işlemini daha hızlı yapar. Bu ağaçları, ağacın mevcut maksimum veya minimum değerini anında temin edebilme yeteneğine bağlı olarak, maksimum yığınlar ve en az yığınlar olarak daha da sınıflandırabilirsiniz. | Öğreticiler |
Sezgisel | Bu, kendi keşfine dayanan ve problemi çözmek için yeterince yararlı sonuçlar (mutlaka optimal değil ancak yeterince iyi) üreten bir problem çözme tekniğidir ve daha iyi bir çözüm " Gerekli değil. Kendini keşfi, algoritmanın bir çözüm için potansiyel olarak yararlı bir yol gösterebilmesini sağlayan bir süreçtir (ancak çözümün doğru olup olmadığını bilmek için insan sezgisini ve anlayışını hesaba katmanız gerekir). | Kuzeybatı. edu |
MapReduce | Bu algoritmalar paralel hesaplamaları kullanarak (bir ağda birbirine bağlı birden çok bilgisayar kullanarak) algoritmaların çalışmasını sağlamak için algoritmaların daha hızlı çözümlerini tamamlamalarına izin veren bir çerçeve. | Hadoop Apache |
Mergesort | Mergesort, genel amaçlı, karşılaştırmalı veri sıralama yöntemidir. Görevi yerine getirmek için bölünmüş ve fethedilen bir yaklaşıma bağlı. | Geeks için Geeks |
Nash Equilibrium | Bu, diğer oyuncuların diğer oyuncular için denge stratejisini bildiği bir oyun teorisidir; bu nedenle hiç kimsenin kendi kişisel stratejisini değiştirerek kazanacak bir şeyleri yoktur. Bu teori, oyuncuyu kazanmak için oyuncunun diğer oyuncuların kararlarını hesaba katması gereken herhangi bir düşmanca durumda kullanımını görür. | Han Academy |
PageRank | PageRank, bir grafikteki bir düğümün önemini ölçmek için kullanılan bir algoritma. Bu algoritma, alakalı aramaları kullanıcılara güç kazandıran Google'ın temel algoritmalarının kökenindedir. | Princeton. edu |
Saf Buluşsal Arama | Bu algoritma düğümlerini maliyetlerine göre genişletir. İki liste tutar. Kapalı liste, daha önce keşfedilmiş olduğu düğümleri içerir ve açık liste, keşfedilmesi gereken düğümleri içerir. Her yinelemede, algoritma, mümkün olan en düşük maliyetle düğümü genişletir. Tüm alt düğümleri kapalı listeye yerleştirilir ve tek tek alt düğüm maliyetleri hesaplanır. Algoritma, düşük maliyetli alt düğümleri açık listeye geri gönderir ve yüksek maliyetli alt düğümleri siler. Sonuç olarak, algoritma çözüm için akıllı, maliyet temelli bir arama gerçekleştirir. | World of Computing |
Quicksort | Bu, veri dizilerini daha küçük dizilere ayırmaya dayanan genel amaçlı bir sıralama stratejisidir.Görevi yerine getirmek için bölünmüş ve fethedilen bir yaklaşıma bağlı. | Öğreticiler |
Dengesiz Ağaç | Ağacın dengesine bakmadan gerekli olduğunda yeni veri öğeleri yerleştiren bir ağaç. Öğeler ekleme yöntemi, ağacın daha hızlı oluşturulmasını sağlar, ancak arama veya sıralama yaparken erişim hızını azaltır. | Quora |
Diğer Matematik Yapılardan Algoritmaları Farklılaştırmak
Çoğu insana benziyorsanız, matematik yapılarıyla ilgili olarak başınızı kaşıyordur, çünkü kimse doğru terimleri nasıl kullanacaklarını bilmiyor gibi görünür. Sanki insanlar şeytani şeyler yapmaya çalışıyor! Sonuçta, bir denklem nedir ve neden bir algoritmadan farklıdır? Artık korkmayın: Aşağıdaki tablo, karşılaşabileceğiniz ama hakkında sormaktan korktuğunuz matematik yapılarına ilişkin kesin kılavuzu sunmaktadır.
Yapı | Açıklama |
Denklem | Bir bütün olarak alındığında belirli bir değere eşit sayıda sayı ve semboller. Bir denklem her zaman eşittir işareti içerir, böylece sayıların ve simgelerin eşitlik işaretinin diğer tarafındaki belirli değeri temsil ettiğini bilirsiniz. Denklemler genellikle bir sembol olarak sunulan değişken bilgi içerir, ancak değişken kullanmaları gerekmez. |
Formül | Bilgi veya fikirleri ifade etmek için kullanılan sayıların ve sembollerin bileşimi. Bir formül normal olarak iki tamsayının en büyük Ortak Böleni (GCD) tanımlamak için matematiksel veya mantıksal kavramlar sunar (Khan Academy'deki video bunun nasıl çalıştığını anlatır). Genel olarak, bir formül iki veya daha fazla değişken arasındaki ilişkiyi gösterir. Çoğu kişi bir formülü özel bir denklem olarak görür. |
Algoritma | Bir sorunu çözmek için kullanılan bir dizi adım. Bu sekans, belirli bir çözüm sağlayarak, bir konuyu ele alan benzersiz bir yöntem sunar. Bir algoritmanın, matematiksel veya mantıksal kavramları temsil etmesi gerekmemektedir; insanlar bu algoritmaları bu şekilde en çok kullandıklarından, bu kitaptaki sunumlar genellikle bu kategoriye girmektedir. Bazı özel formüller de, ikinci dereceden formül gibi algoritmalardır. Bir algoritmayı temsil eden bir işlem için şunlar olmalıdır:
Sonlu: Algoritma sonunda sorunu çözmelidir. İyi tanımlanmış: Adımlar dizisi, özellikle bilgisayarlar tarafından anlaşılabilir, kullanışlı bir algoritma oluşturabilen kesin ve mevcut adımları sağlamalıdır. Etkili: Bir algoritma, birisinin tanımladığı sorunun tüm durumlarını çözmelidir. Bir algoritma, çözmesi gereken sorunu her zaman çözmeli. Bazı arızaları önceden tahmin etmeniz gerekirse de, arızanın görülme sıklığı nadirdir ve yalnızca, amaçlanan algoritma kullanımı için kabul edilebilir durumlarda oluşur. |
İnanılmaz Yol Algoritmalarını Kullanma
İnsanlar aslında algoritmaları her zaman kullanıyor. Örneğin, tost yapmak bu blog yazısında açıklandığı üzere bir algoritmaya örnektir. Toast yapmak şaşırtıcı bir algoritma değil, ancak aşağıdaki tabloda, görevleri yerine getirmek için bir bilgisayar kullananlar var.
Görev | Neden İnanılmaz |
Kriptografi | Verileri güvende tutmak, bilgisayar korsanlarının sürekli veri kaynaklarına saldırmasıyla devam eden bir savaştır. Algoritmalar, verileri analiz etmenizi, başka bir forma koymanızı ve daha sonra orijinal formuna geri döndürmenizi sağlar. |
Grafik analizi | İki nokta arasındaki en kısa çizgiye karar verme yeteneği her türlü kullanım şekli bulur. Örneğin, bir yönlendirme probleminde, GPS bu özel algoritma olmadan çalışamaz çünkü A noktasından B noktasına giden en kısa rotayı kullanarak hiçbir zaman şehir sokaklarına yönlendirilemez. |
Sahte rasgele numara üretimi | Oyun oynarken düşünün Bu hiç değişmedi. Aynı yerde başlayın ve oynarken her zaman aynı adımları aynı şekilde yapın. Sıkıcı! Görünüşte rasgele sayılar üretme yeteneği olmaksızın, birçok bilgisayar görevleri anlamsız veya imkansız hale gelir. |
Zamanlama | İlgili kişilerin hepsine adil bir şekilde kaynakların kullanılması, algoritmaların varlığını büyük bir şekilde bildirebilmelerinin bir başka yoludur. Örneğin, kavşaklardaki zamanlama ışıkları artık ışık değişiklikleri arasındaki saniye sayısını azaltan basit cihazlar değildir. Modern cihazlar, günün saati, hava koşulları ve trafik akışı gibi her türlü konuyu göz önünde bulundurur. Bununla birlikte, çizelgeleme birçok biçimde gelir. Bilgisayarınızın aynı anda birden fazla görevi nasıl çalıştığını düşünün. Bir zamanlama algoritması olmadan, işletim sistemi tüm mevcut kaynakları kapar ve uygulamanızın faydalı bir iş yapmasını önleyebilir. |
Aranıyor | Bilgilerin bulunması ya da gördüğünüz bilgilerin istediğiniz bilgiye sahip olduğunu doğrulamak çok önemli bir görevdir. Bu yeteneği olmadan, çevrimiçi gerçekleştirdiğiniz birçok görev, ofisiniz için mükemmel bir cezve satan internet sitesini bulmak gibi mümkün olmayacaktır. |
Sıralama | Bilgi sunmanın sırasının belirlenmesi önemlidir, çünkü günümüzde insanların çoğu bilgi yüklemesinden muzdarip ve veri başlatmayı azaltmak zorundadır. Amazon'a gideceğini, satış için binden fazla cezve bulduğunu, ancak bunları fiyata veya en olumlu gözden geçirmeye göre sıralamak mümkün olmadığını düşünün. Dahası, birçok karmaşık algoritma güvenilir bir şekilde çalışmak için doğru sırayla veri ister, bu nedenle sıralama daha fazla problemi çözmek için önemli bir gerekliliktir. |
Dönüştürme | Bir veriyi farklı türde bir veriye dönüştürmek, verilerin etkili bir şekilde anlaşılması ve kullanılması için kritik önem taşır. Örneğin, imparatorluk ağırlıklarını iyi anlayabilirsiniz, ancak tüm kaynaklar metrik sistemi kullanmaktadır. İki sistem arasındaki dönüştürme, veriyi anlamanıza yardımcı olur. Aynı şekilde, Hızlı Fourier Dönüşümü (FFT), Wi-Fi yönlendiriciniz gibi şeylerin çalışmasına olanak tanıyan sinyalleri zaman etki alanı ve frekans etki alanı arasında dönüştürür. |
Algoritma Karmaşıklığının Ele Alınması
Algoritmaların karmaşık olduğunu zaten biliyorsunuz. Bununla birlikte, bir algoritmanın ne kadar karmaşık olduğunu bilmeniz gerekir; çünkü daha karmaşık olan algoritma o kadar uzun sürer. Aşağıdaki tablo, çalışma süresine göre sunulan karmaşıklığın çeşitli düzeylerini (en hızlıdan en yavaşa) anlamanıza yardımcı olur.
Karmaşıklık | Açıklama |
Sabit karmaşıklık O (1) | Ne kadar çok girdi girdiğinize bakılmaksızın değişmez bir yürütme süresi sağlar. Her girdi, tek bir yürütme süresi birimi gerektirir. |
Logaritmik karmaşıklık O (log n) | İşlemlerin sayısı girdiden daha yavaş büyür ve algoritmayı küçük girdilerle daha az verimli, daha büyük olanlarla daha verimli hale getirir. Bu sınıfın tipik bir algoritması ikili aramadır. |
Doğrusal karmaşıklık O (n) | İşlemler girişle 1: 1 oranında büyür. Tipik bir algoritma, girişi bir kez taradığınızda ve onun her bir öğesine bir işlem uyguladığınızda tekrarlama işlemidir. |
Linearitmik karmaşıklık O (n log n) | Karmaşıklık, logaritmik ve doğrusal karmaşıklık arasındaki bir karışımı ifade eder. Mergesortsort, Heapsort ve Quicksort gibi verileri sipariş etmek için kullanılan akıllı algoritmaların tipik bir örneğidir. |
İkinci dereceden karmaşıklık O (n 2 ) | İşlemler, girdi sayısının karesi kadar büyür. Başka yinelemelerde (bilgisayar bilimlerinde iç içe geçmiş yinelemeler olarak adlandırılır) tek bir iterasyona sahip olduğunuzda, karmaşıklığınız karmaşıktır. Örneğin, bir isim listesi var ve en benzer olanları bulmak için her ismi diğer tüm isimlerle karşılaştırıyorsunuz. Bazı daha az etkili sipariş algoritmaları böyle karmaşıklığı sunar: kabarcık sıralama, seçim sıralama ve ekleme sıralama. Bu karmaşıklık düzeyi, algoritmalarınızın bir çözüm bulmadan önce saatlerce hatta günler sürebilir anlamına gelir. |
Kübik karmaşıklık O (n 3 ) | İşlemler karesel karmaşıklığa göre daha hızlı büyür, çünkü şimdi birden çok iç içe geçmiş yinelemeye sahipsiniz. Bir algoritma bu karmaşıklık derecesine sahipse ve az miktarda veri (100, 000 öğe) işlemek zorunda kalırsanız, algoritma yıllarca çalışabilir. Girişin gücü olan bir dizi işleminiz olduğunda, algoritmanın polinom zamanında çalıştığı anlamına gelir. |
Üstel karmaşıklık O (2 n ) | Algoritma, eklenen her yeni eleman için önceki işlemlerin iki katı sayı alır. Bir algoritma bu karmaşıklığa sahip olduğunda, küçük sorunlar bile sonsuza kadar sürebilir. Kapsamlı aramalar yapan birçok algoritmanın üstel karmaşıklığı vardır. Bununla birlikte, bu karmaşıklık seviyesi için klasik örnek Fibonacci sayılarının hesaplanmasıdır. |
Faktöriyel karmaşıklık O (n!) | Bu algoritma, elemanlar arasındaki muhtemel kombinasyonların çokluğundan dolayı karmaşıklığın gerçek bir kabusu ortaya koymaktadır. Düşünüyorsanız: Girişiniz 100 nesneyse ve bilgisayarınızdaki bir işlem 10 999 - 6 saniyedir (günümüzde her bilgisayar için makul bir hız alır), yaklaşık 10 140 yılına ihtiyaç duyarsınız (evrenin yaşının 10 14 yıl olduğu tahmin edildiğinden, imkansız bir zaman süresi). Ünlü bir faktöryal karmaşıklık problemi, bir satış elemanının pek çok şehri ziyaret etmek ve başlangıç şehrine geri dönmek için en kısa güzergahı bulması gereken seyyar satıcı meselesidir.
|