İçeriğe atla

Dekker algoritması

Dekker algoritması, karşılıklı dışlamayı (mutual exclusion) sağlamak için kullanılan bir eşzamanlı programlama (concurrent programming) algoritmasıdır. 1964'te T. J. Dekker tarafından geliştirilen ve adını da buradan alan algoritma, iki threadin çakışma yaratmaksızın paylaşılamayacak (yani bir seferde sadece bir threadin kullanabileceği) bir kaynağı, sadece iletişim için paylaşılan bir bellek yardımıyla, kullanmalarına olanak tanır. Basit bir vardiya (yani threadler arası sıra bölüştüren) algoritmasındaki dikkatli değiştirmeden (strict alternation) kaçınır. Dekker algoritması karşılıklı dışlama için icat edilmiş ilk algoritmalardandır.

Algoritmanın yapısı

Eğer iki işlem aynı anda kritik bölgeye girmeye çalışırsa, Dekker algoritması o anki sıraya göre hangi işlemin sırasıysa, sadece o bir tek işlemin kritik bölgeye girmesine izin verir. Eğer bir işlem zaten kritik bölgedeyse, diğer işlem yoğun beklemede ilk işlemin kritik bölgeden çıkmasını bekler. Bunu gerçekleştirmek için iki bayrak kullanılırlar: f0 ve f1. Bunlar kritik bölgeye girme amacını belirtirken, bir sıra değişkeni sayesinde iki işlem arasında hangisinin öncelikli olduğu belirtilir.

Algoritmanın sözde kodu şu şekilde yazılabilir:

 f0 := false
 f1 := false
 turn := 0   // veya 1
 
 // işlem 1                          // işlem 2
 p0:                                 p1:
     f0 := true                          f1 := true
     while f1 {                          while f0 {
         if turn ≠ 0 {                       if turn ≠ 1 {
             f0 := false                         f1 := false
             while turn ≠ 0 {                    while turn ≠ 1 {
             }                                   }
             f0 := true                          f1 := true
          }                                  }
     }                                    }

    // kritik bölge                       // kritik bölge 
    ...                            ...
    // kalan bölge                        // kalan bölge
    turn := 1                             turn := 0
    f0 := false                           f1 := false

İlgili Araştırma Makaleleri

<span class="mw-page-title-main">İkili arama algoritması</span>

İkili arama, sıralı bir dizide, belirli değerin aranmasına yönelik bir algoritmadır. Her adımda, aranan değerin dizinin orta değerine eşit olup olmadığı kontrol edilir. Eşit ise aranan bulunmuştur. Aranan değer orta değerden küçükse, dizinin sıralı olduğu kabulünden, ortanın yukarısına bakmaya gerek kalmaz, arama dizinin başı ve orta değer arasında devam eder. Aranan ortadan büyükse arama orta ile son arasında devam eder. Her adımda dizi ikiye bölünür.

RSA, güvenliği tam sayıları çarpanlarına ayırmanın algoritmik zorluğuna dayanan bir tür açık anahtarlı şifreleme yöntemidir. 1978’de Ron Rivest, Adi Shamir ve Leonard Adleman tarafından bulunmuştur. Bir RSA kullanıcısı iki büyük asal sayının çarpımını üretir ve seçtiği diğer bir değerle birlikte ortak anahtar olarak ilan eder. Seçilen asal çarpanları ise saklar. Ortak anahtarı kullanan biri herhangi bir mesajı şifreleyebilir, ancak şu anki yöntemlerle eğer ortak anahtar yeterince büyükse sadece asal çarpanları bilen kişi bu mesajı çözebilir. RSA şifrelemeyi kırmanın çarpanlara ayırma problemini kırmak kadar zor olup olmadığı hala kesinleşmemiş bir problemdir.

Soundex, İngilizcedeki keliemelerin teleffuz biçimlerine göre hazırlanmış bir fonetik algoritmadır. Bu algoritmanın hazırlanmasındaki temel amaç; teleffuzları benzeşen kelimelerin bu yolla aynı karakter katarına (string) dönüştürülmeleri ve bu yolla benzer kelimelerin -yazımlarında fark olsa bile- tespit edilmesidir. Bunun yanında Soundex algoritması, fonetik algoritmalardan en bilineni ve en sık kullanılanı olup, bazı çevreler tarafından -yanlış bir şekilde- fonetik algoritma terimiyle aynı anlamda kullanılamaktadır.

<span class="mw-page-title-main">Birleştirmeli sıralama</span>

Birleşmeli Sıralama, bilgisayar bilimlerinde derecesinde karmaşıklığa sahip bir sıralama algoritmasıdır. Girdi olarak aldığı diziyi en küçük hale gelene kadar ikili gruplara böler ve karşılaştırma yöntemi kullanarak diziyi sıralar.

<span class="mw-page-title-main">Seçmeli sıralama</span>

Seçmeli Sıralama, bilgisayar bilimlerinde kullanılan bir sıralama algoritmasıdır. Karmaşıklığı olduğu için büyük listeler üzerinde kullanıldığında verim sağlamaz ve genel olarak benzeri olan eklemeli sıralamadan daha başarısızdır. Seçmeli sıralama yalın olduğu ve bazı durumlarda daha karmaşık olan algoritmalardan daha iyi sonuç verdiği için tercih edilebilir.

Çarpma algoritmaları, çarpma işlemi için gereken sonlu işlemler kümesidir. Çarpma işlemi, aritmetik işlemlerinde sık kullanılan ve bilimsel uygulamalarda önemli rolü olan, temeli aslında toplama ve kaydırma işlemlerine dayanan aritmetiksel bir işlemdir. Toplama işleminden daha karmaşıktır ve daha çok zaman alır aynı zamanda daha çok alan gerektirir.

<span class="mw-page-title-main">Hızlı sıralama</span>

Hızlı sıralama, günümüzde yaygın olarak kullanılan bir sıralama algoritmasıdır. Hızlı sıralama algoritması n adet sayıyı, ortalama bir durumda, karmaşıklığıyla, en kötü durumda ise karmaşıklığıyla sıralar. Algoritmanın karmaşıklığı aynı zamanda yapılan karşılaştırma sayısına eşittir.

<span class="mw-page-title-main">Yığın sıralaması</span>

Yığın Sıralaması, bilgisayar bilimlerinde kullanılan karşılaştırmaya dayalı bir sıralama algoritmasıdır. Uygulamada pek çok bilgisayarda hızlı sıralama algoritmasından daha yavaş çalışsa da en kötü durumda O(n log n) çalışma süresi vardır. Yığın sıralaması diziyi yerinde sıralar ancak kararlı bir sıralama algoritması değildir.

Cüce sıralaması, bilgisayar bilimlerinde kullanılan araya sokmalı sıralamaya benzer bir sıralama algoritmasıdır. Ara sokmalı sıralamadan farkı kabarcık sıralaması yönteminde olduğu gibi, bir elemanın sıralanan dizideki yerine birçok yer değiştirme yoluyla gelmesidir. Cüce Sıralaması adı algoritmanın yönteminin mitolojideki Hollanda cücelerinin (gnome) bir dizi çiçek saksısını sıraya diziş biçimine benzemesinden kaynaklanmaktadır.

<span class="mw-page-title-main">Kabarcık sıralaması</span>

Kabarcık Sıralaması, bilgisayar bilimlerinde kullanılan yalın bir sıralama algoritmasıdır. Sıralanacak dizinin üzerinde sürekli ilerlerken her defasında iki öğenin birbiriyle karşılaştırılıp, karşılaştırılan öğelerin yanlış sırada olmaları durumunda yerlerinin değiştirilmesi mantığına dayanır. Algoritma, herhangi bir değişiklik yapılmayıncaya kadar dizinin başına dönerek kendisini yineler. Adına "Kabarcık" sıralaması denmesinin nedeni büyük olan sayıların aynı suyun altındaki bir kabarcık gibi dizinin üstüne doğru ilerlemesidir.

<span class="mw-page-title-main">Kabuk sıralaması</span>

Shell sıralaması, bilgisayar bilimlerinde kullanılan bir sıralama algoritmasıdır. Eklemeli sıralama algoritmasının aşağıdaki iki gözlem kullanılarak genelleştirilmiş biçimidir:

Kokteyl sıralaması, bilgisayar bilimlerinde kabarcık sıralaması algoritmasına benzer bir sıralama algoritmasıdır. Kabarcık sıralamasından farkı sıralanacak listenin üzerinden tek yöne doğru değil iki yöne de geçerek öğeleri sıralamasıdır. Algoritmanın uygulanması kabarcık sıralaması algoritmasının uygulanmasından çok az daha zordur.

Tarak Sıralaması, ilk defa 1991 yılının Nisan ayında Stephen Lacey ve Richard Box tarafından Byte dergisinde duyurulmuş yalın bir sıralama algoritmasıdır. Kendisinden önce duyurulmuş kabarcık sıralaması algoritmasından başarılıdır ve karmaşıklıkta hızlı sıralama algoritmasıyla yarışır. Algoritmanın ana fikri listenin sonundaki küçük değerli öğelerin sayısını azaltmaktır. Kabarcık sıralaması algoritmasında sıralanacak listenin sonundaki küçük değerli öğelerin varlığı algoritmayı çok yavaşlattığı için tarak sıralamasında bu değerlerin sayısının azaltılması yoluna gidilmiştir.

<span class="mw-page-title-main">İkili arama ağacı</span>

İkili arama ağacı, verileri organize etmek için kullanılan bir çeşit ikili ağaçtır. İkili ağaçtan temel farkı, verilerin sıralanmış bir şekilde tutulmasıdır, bu sayede ikili arama algoritmasının kullanılmasına imkân verir.

İplik sıralaması bilgisayar bilimlerinde kullanılan bir sıralama algoritmasıdır. Sıralanacak olan dizinin, sıralanmış alt dizilerinin oluşturularak bu alt dizilerin birleştirilmesi yoluyla sonucun oluşturulması mantığına dayanır. Algoritmanın her bir aşamasında ana dizinin üzerinden geçilir ve bu diziden zaten sıralanmış olan bir dizi eleman çıkarılır. Çıkarılan bu eleman dizileri daha sonra birleştirilir.

Saçma sıralama veya rastgele sıralama, bilgisayar bilimlerinde yalnızca eğitim amaçlı olarak kullanılan verimsiz bir sıralama algoritması. Bir deste oyun kağıdı saçma sıralama algoritmasıyla sıralanmak istendiğinde, destenin sıralı olup olmadığına bakılır, eğer deste sıralı değilse havaya atılarak yere düşen kartlar toplanarak deste yeniden oluşturulur. Bu işlem deste sıralanana kadar sürer.

<span class="mw-page-title-main">Project Euler</span> Matematik/Programlama Problemi

Project Euler veya Euler Projesi, çözülmesi için matematiksel kavrayışlardan daha fazlasını gerektiren bir dizi zorlu matematik/bilgisayar programlama problemidir. Her ne kadar matematik zarif ve etkili yöntemlere ulaşmanıza yardımcı olsa da, çoğu problemi çözmek için bir bilgisayar ve programlama becerileri gerekecektir. Toplam problem sayısı 800'den fazladır ve hala projeye etkin olarak problem eklenmektedir.

Bilgisayar programlamada dinamik iletim, altyordam çağrılarının ilişkin altyordam başlangıç adresine dinamik olarak bağlanmasıdır. Bir diğer deyişle, dinamik iletim program metnindeki bir çağrı ile işletilen altyordamın programın çalışması sırasında birbirine bağlanması durumudur. Geri çağrı ve çokbiçimliliğin realize edilmesinde kullanılan bu bağlama yöntemi, yordamsal programlama dillerinde altyordam göstericileriyle gerçekleştirilirken, nesne yönelimli dillerde kalıtlama ve gerçekleştirme ilişkilerinin kullanılmasıyla otomatikman sağlanır. Altyordamların birinci sınıf dil öğesi olarak ele alındığı fonksiyonel programlama dillerinde ise, aynı işlevsellik altyordamların argüman olarak geçirilmesi ile sağlanabilir.

<span class="mw-page-title-main">FIFO algoritması</span>

FIFO algoritmasının mantığı basittir. Bellek yöneticisinin yeni bir sayfaya yer açmak için, hangi sayfayı dışarıda bırakacağını karar veren algoritmalardan biridir. Yönlendiriciye gelen ilk paket, iletilecek ilk pakettir.