İçeriğe atla

Tanrının algoritması

Tanrının algoritması, Rubik Küpü ile benzeri bulmaca ve matematiksel oyunların çözüm yöntemlerini konu alan bir kavram. Sözü edilen bulmacaları olabilecek en az adımda çözmeyi başaran algoritmayı tanımlamak için kullanılan bu terim, herhangi bir anda çözüme giden en kısa yolu bulabilen bir bilgenin var olduğu düşüncesine dayanmaktadır.

Kapsam ve tanım

Kavram, sonlu sayıda "durum" barındıran ve sınırlı sayıda "hamle"den oluşan bulmacalar için kullanılmaktadır. Çözüm, gelişigüzel bir durumdan başlayarak "son duruma" (ya da son durumlardan birine) ulaşmak olarak tanımlanır.

Bu tanıma uyan bazı bulmacalar Rubik Küpü, Hanoi kuleleri ve 15-bulmaca gibi parçalı bulmacalardır. Tek kişiyle oynanan peg solitaire ile misyonerler ve yamyamlar problemi gibi mantık bulmacaları da bu tanıma dahildir. Bu oyunların ortak özelliği, durumların köşeler, hamlelerin yollar olarak tanımlandığı bir yönlü çizge olarak modellenebilmeleridir.

Bu tür bir bulmacayı çözen algoritma, gelişigüzel bir durumdan başlayarak son duruma ulaşıncaya değin yapılacak hamleleri geri dönebilmelidir (bulmacanın o ilk durum için bir çözümü varsa). Bir çözümün en iyi olarak değerlendirilmesi için olabilecek en kısa hamle dizisine sahip olması gerekmektedir. Böylece, Tanrı'nın algoritması bu tür bir bulmacayı olabilecek en iyi çözümle sonuçlandıran algoritma olarak tanımlanabilir.

Bir algoritmanın "Tanrı'nın algoritması" olarak değerlendirilebilmesi için uygulanabilir olması gerekmektedir. Bu, algoritmanın aşırı kaynak (bellek alanı ya da zaman) tüketmemesi anlamını taşımaktadır. Örneğin, çok büyük bir başvuru çizelgesi kullanılarak çözüme çok kısa sürede ulaşılabilir; ancak, bu yöntem olağanüstü miktarda bellek alanına gerek duymaktadır.

Tam çözüme ulaşmaya çalışmaktansa bir durumdan (son durum olmamak koşuluyla) başlayıp yalnızca tek hamle (herhangi bir ideal çözümün ilk hamlesi olmak koşuluyla) yapmak üzerine de odaklanılabilir. Tek bir hamle için doğru sonucu üreten bu algoritma özyineleme yoluyla ilk problemin çözümünü bulan algoritmaya evrilebilmektedir. Buna benzer biçimde, tam çözüm için üretilen algoritma da ürettiği sonucun geri kalanı atılarak yalnızca bir hamle bulacak biçime dönüştürülebilir.

Örnekler

karıştırılmış bir Rubik küpü

15-bulmacanın genellenmiş sürümü olan n-bulmacanın ideal çözümünü bulmanın NP-zor olduğu bilinmektedir.[1] Bu problem için uygulanabilir bir Tanrı'nın algoritması bulunup bulunmadığı ise belli değildir.

Hanoi kuleleri bulmacası için ise her disk sayısı için bir Tanrı'nın algoritması bulunmaktadır.[2]

Rubik Küpü için ideal çözüm yöntemi ilk kez 1997 yılında Richard Korf tarafından ortaya atılmıştır.[3] En kötü durum için 20 hamlede çözüme ulaşılabileceği 1995'ten bu yana bilinmesine karşın, 2010 yılında gerçekleştirilen deneyler sonucunda 20 hamlenin her durum için üst sınır oluşturduğu kanıtlanmıştır.[4] Bu sayı, Tanrının sayısı olarak adlandırılmaktadır.[5]

Ayrıca bakınız

  • Kahinli Turing makinesi

Notlar

  1. ^ Daniel Ratner, Manfred K. Warmuth (1986). "Finding a shortest solution for the N × N extension of the 15-puzzle is intractable" 9 Mart 2012 tarihinde Wayback Machine sitesinde arşivlendi.. Proceedings AAAI-86. Ulusal Yapay Zeka Konferansı, 1986. s. 168–172
  2. ^ Carlos Rueda, "An optimal solution to the Towers of Hanoi Puzzle".
  3. ^ Richard E. Korf, "Finding optimal solutions to Rubik's Cube using pattern databases", Proc. Nat. Conf. on Artificial Intelligence (AAAI-97), Providence, Rhode Island, Temmuz 1997, s. 700–705
  4. ^ "God's Number is 20" 21 Temmuz 2013 tarihinde Wayback Machine sitesinde arşivlendi.. Cube20.org
  5. ^ Jonathan Fildes (11 Ağustos 2010). "Rubik's Cube quest for speedy solution comes to an end". BBC News. 25 Ağustos 2010 tarihinde kaynağından arşivlendi. Erişim tarihi: 25 Ağustos 2010. 

Kaynakça

İlgili Araştırma Makaleleri

<span class="mw-page-title-main">Bellek yönetimi</span>

Ana belleğin işlemler arasında paylaştırılmasına ana bellek yönetimi ya da bellek yönetimi adı verilir. İşletim sisteminin bu amaçla oluşturulan kesimine de bellek yöneticisi adı verilir.

<span class="mw-page-title-main">Rubik Küpü</span> mekanik bulmaca

Rubik Küpü, Zekâ Küpü ya da Sabır Küpü; 1974 yılında Macar heykeltıraş ve mimar Ernő Rubik tarafından icat edilen mekanik bulmacadır. Hareketli yüzeylerden oluşan ve çoğunlukla plastikten yapılmış bir küp olan Rubik Küpü, başlıca dört şekilde piyasaya sürülmüştür: 2×2×2'lik Mini Rubik Küpü, 3×3×3'lük standart küp, 4×4×4'lük Rubik'in İntikamı ve 5×5×5'lik Profesörün Küpü. 6×6×6 ve 7×7×7'lik küpler de hâlihazırda üretilmektedir. Standart olan ve 6 yüzeye sahip bir rubik küp, toplam 27 parçadan oluşur.

<span class="mw-page-title-main">Genetik algoritma</span>

Genetik algoritmalar, doğada gözlemlenen evrimsel mekanizmalara benzer mekanizmalar kullanarak çalışan eniyileştirme yöntemidir. Çok boyutlu uzayda belirli bir maliyet fonksiyonuna göre en iyileştirme amacıyla iterasyonlar yapan ve her iterasyonda en iyi sonucu üreten kromozomun hayatta kalması prensibine dayanan en iyi çözümü arama yöntemidir.

<span class="mw-page-title-main">Sudoku</span>

Sudoku (Japonca: 数独, romanize: sūdoku, mantık tabanlı, kombinasyonel sayı yerleştirme bulmacasıdır. Klasik Sudoku, 9×9 boyutlarında bir diyagramda çözülen ve her satır, her sütun ve her 3×3'lük karede 1'den 9'a kadar rakamların birer kez yer almasını gerektiren sayı tabanlı bir zekâ oyunudur. Bulmaca hazırlayıcısı tek çözümü olması için iyi tasarlanmış belirli sayıları önceden kutucuklara yerleştirir.

Matematikte matematiksel programlama, eniyileme ya da optimizasyon terimi; bir gerçel fonksiyonu minimize ya da maksimize etmek amacı ile gerçek ya da tam sayı değerlerini tanımlı bir aralıkta seçip fonksiyona yerleştirerek sistematik olarak bir problemi incelemek ya da çözmek işlemlerini ifade eder. Örneğin bu problem şöyle olabilir:

<span class="mw-page-title-main">Tangram</span> deneme

Tangram, taş, kemik, plastik veya tahtadan yapılmış olan geometrik biçimlerdeki yedi adet parçayı bir araya getirerek çeşitli formlar oluşturma esasına dayalı yaratıcı bir zeka oyunudur. Hedeflenen form, geometrik bir şekil, hareket halindeki bir insan figürü, hayvan figürü, alfabedeki bir harf ya da benzeri bir şey olabilir. Hedef olarak belirlenen formu oluşturabilmek için, yedi parçanın tamamını kullanmak gerekir. Bu parçalar, farklı büyüklüklerdeki beş adet üçgen, bir adet kare ve bir adet paralelkenardır. Bu yedi parçanın Güneş, Ay, Mars, Jüpiter, Satürn, Merkür ve Venüs'ü temsil ettiği söylenmektedir. Çin'de geliştirilen bu oyunun ortaya çıkışı çok eski tarihlerde olmuştur.

8 Vezir Bulmacası, 8x8'lik bir satranç tahtasına 8 adet vezirin hiçbiri olağan vezir hamleleriyle birbirini alamayacak biçimde yerleştirmesi sorunudur. Her bir vezirin konumunun diğer bir vezire saldırmasına engel olması için hiçbir vezir başka bir vezirle aynı satıra, aynı kolona ya da aynı köşegene yerleştirilemez. 8 Vezir Bulmacası daha genel olan n Vezir Bulmacası'nın özel bir durumudur.

<i>Portal</i> (video oyunu) 2007 yapımı bulmaca-platform oyunu

Portal, Valve Corporation tarafından geliştirilmiştir. Orange Box'ın bir parçası olarak 9 Ekim 2007'de Microsoft Windows ve Xbox 360, 11 Aralık 2007'de PlayStation 3 için dağıtılan bir FPS bilimkurgu, macera, bulmaca oyunudur. Windows sürümü Valve'ın içerik dağıtım yazılımı Steam üzerinde indirebilir olarak bulunması dışında 9 Nisan 2008'de tek ürün olarak Electronic Arts tarafından dağıtılmıştır.

<span class="mw-page-title-main">Gelmiş geçmiş en zor mantık bulmacası</span>

L'indovinello più difficile del mondo, Raymond Smullyan'dan esinlenilmiş ve İtalya'nın başlıca gazetelerinden La Repubblica'da yer almış şu mantık bulmacasına Amerikalı filozof ve mantıkçı George Boolos tarafından verilen ad:

Zebra Bulmacası, çok kişi tarafından bilinen ünlü bir mantıksal bulmacadır.

<span class="mw-page-title-main">Pergel ve çizgilik çizimleri</span>

Pergel ve çizgilik çizimi, belli uzunlukta doğrular, belli büyüklükte açılar ve diğer geometrik şekilleri çizmek için sadece ideal bir çizgilik ve pergel kullanılmasıdır.

Matematikte, özellikle soyut cebir ve uygulamalarında, ayrık logaritma, genel logaritmanın grup kuramındaki karşılığıdır. Genel olarak bakıldığında, loga(b) ifadesi, ax = b ifadesinin gerçel sayılar kümesi içindeki çözümlerine karşılık gelir. Benzer olarak, g ve h sonlu devirli grup G'nin elemanları olduğunda, gx = h ifadesinin çözümü olan x sonuçlarına h'nin g tabanındaki ayrık logaritması denir.

Hesaplamalı elektromanyetik, hesaplamalı elektrodinamik veya elektromanyetik modelleme elektromanyetik alan ile fiziksel nesnelerin ve çevrenin etkileşimini modelleme işlemidir.

Hesaplamalı kimya, kimya problemlerini çözmeye yardımcı olmak için bilgisayar simülasyonunu kullanan bir kimya dalıdır. Moleküllerin, katıların yapı ve özelliklerini hesaplamak için verimli bilgisayar programlarına dahil edilmiş teorik kimya yöntemlerini kullanır. Bu yöntemlerin kullanılmasının nedeni, hidrojen moleküler iyonu ile ilgili nispeten yeni sonuçlar dışında, kuantum çok-gövdeli(many-body) problemlerin analitik olarak çözülemez oluşudur. Hesaplama sonuçları normal olarak kimyasal deneylerle elde edilen bilgileri tamamlarken, bazı durumlarda gözlemlenmeyen kimyasal olayları da tahmin edebilmektedir. Yeni ilaç ve materyallerin tasarımında yaygın olarak kullanılmaktadır.

Hisse ispatı, (PoS) bir kripto para blok zinciri ağının dağıtık fikir birliğine ulaşmayı amaçladığı bir algoritma türüdür. PoS tabanlı kripto para birimlerinde, bir sonraki bloğu oluşturan, rassal seçim ve zenginliğin ya da yaşın çeşitli kombinasyonları yoluyla seçilir. Aksine, bitcoin gibi emek ispatınadayanan kripto paraların algoritması, madencilik kullanır. Yani, kayıtları (transaction) doğrulamak ve yeni bloklar oluşturmak için yoğun hesaplamalı bulmacaların çözümünü gerektirir.

Emek ispatı , denial-of-service saldırıları ve bir ağ üzerinde bulunan spam mesajlar ile servislerin kötüye kullanımını, istemciden bir miktar iş yapmasını isteyerek önleme amaçlı ekonomik bir ölçüdür. Bu kavram, Cynthia Dwork ve Moni Naor tarafından 1993 tarihli bir dergi makalesiyle ilk kez ortaya konmuştur. "Emek İspatı" terimi ya da POW ilk kez Markus Jakobsson ve Ari Juels tarafından 1999 tarihli bir yayında literatüre kazandırılarak resmîleştirilmiştir. Emek ispatı sisteminin bir para birimine değer kazandırmak amacıyla kullanıldığı ilk örneklerden biri Solomon Adalarında kullanılan shell moneydir.

Problem çözme, problem çözücü için açık bir çözüm yöntemi bulunmadığında, belirli bir durumu, bir sonuç durumuna dönüştürmeye yönelik bilişsel süreçtir.

<span class="mw-page-title-main">Zamanda sonlu farklar yöntemi</span> elektromanyetizmada kullanılan bir yöntem

Zamanda sonlu farklar yöntemi, kısaca FDTD ya da Yee yöntemi, hesaplamalı elektromanyetizmada kullanılan bir sonlu farklar tekniğidir. Zaman düzleminde çalışan bir yöntem olduğundan ötürü, elektromanyetik spektrumun mikrodalga veya görünür ışık gibi farklı bölgelerinde anten veya fotonik aygıt tasarımı gibi çeşitli problemlerin çözümünde kullanılır. Aynı zamanda bu özellik, simülasyonu yapılan sistemin geniş bir frekans yelpazesine tepkisinin gözlenebilmesini sağlamaktadır. Matris tersinmesi gerektirmeyen bu FDTD, en yaygın elektromanyetik simülasyon yöntemlerinden biri olarak kabul edilir.

Espresso mantık sadeleştiricisi, dijital mantık kapısı devrelerinin karmaşıklığını etkili bir şekilde azaltmak için sezgisel ve özel algoritmalar kullanan bir bilgisayar programıdır. Espresso, IBM'den Robert K. Brayton tarafından geliştirilmiştir. Richard L. Rudell daha sonra 1986'da "PLA Sentezi için Çok Değerlikli Mantık Minimizasyonu" başlığı altında Espresso-MV varyantını yayınladı. Espresso birçok türevine ilham vermiştir.

Matematiksel bulmacalar, eğlence matematiğinin ayrılmaz bir parçasını oluşturur. Belirli kuralları vardır, ancak genellikle iki veya daha fazla oyuncu arasında rekabet içermezler. Bunun yerine, böyle bir bulmacayı çözmek için, çözen kişi verilen koşulları karşılayan bir çözüm bulmalıdır. Matematiksel bulmacaları çözmek için matematik bilgisi gerekir. Mantık bulmacaları yaygın bir matematiksel bulmaca türüdür.


Bu sayfa, bu Vikipedi makalesine dayanmaktadır.
Metin, CC BY-SA 4.0 lisansı altında mevcuttur; ek koşullar uygulanabilir.
Görseller, videolar ve sesler kendi lisansları altında mevcuttur.