Hala Çözülmüş 10 Algoritmik Problemler - AYDINLATMA

Aslında algoritmalar yüzyıllar boyunca var olmuştu, bu nedenle bilim adamlarının şimdiye kadar her algoritmayı keşfedip çözeceğini düşünürdünüz. Ne yazık ki, bunun tersi doğrudur. Belirli bir algoritmayı çözmek çoğu zaman, algoritmanın çözemediği birkaç soru sunar ve birisi çözüm bulana kadar görünmüyordu.

Algoritma, bir sorunu çözmek için kullanılan bir dizi adımı içerir ve bunları denklemler gibi başka öğelerle karıştırmayın. Bir algoritma asla bir problem aramak için bir çözüm değildir. Hiç kimse henüz var olmayan bir sorunu çözmek için bir dizi adım oluşturmaz (asla var olmayabilir).

Bu liste, birilerinin kendileri için bir çözüm bulması durumunda bir amaca hizmet edecek algoritmik problemler hakkında.

Metin aramalarıyla uğraşmak

Birçok metin araması, bilgisayara ne bulması gerektiğini anlatan bir tür kısaltma - normal ifadeler kullanmayı içerir. Normal ifade için kullanılan dil bilgisi, dil veya uygulamaya bağlıdır, ancak sözcük işlemcileri, e-posta uygulamaları, arama diyalogları ve kesin arama yapmanız gereken her yerde diğer yerlerde kullanılan düzenli ifadeler buluyorsunuzdur. Bir dizi metin öğesi için şartlar.

Normal ifadelerle ilgili mevcut sorunlardan biri, her uygulama ortamında benzer bir kurallar kümesi varmış gibi görünmesi, ancak bir arama teriminin zor oluşturulması için yeterli farklılıklara sahip olmasıdır. Genelleştirilmiş yıldız-yükseklik sorunu, genelleştirilmiş düzenli ifade sözdiziminin var olup olmadığını keşfetmeyi amaçlamaktadır. Eğer öyleyse, ortaya çıkan algoritma, birisinin arama yapmak için yalnızca normal ifadeler üretme yöntemini öğrenmesini mümkün kılacaktı.

Farklılaşan sözcükler

Bir karakter, karakterlerle çalışırken harfleri değil sayıları görür. Sayılar aslında bilgisayara 0s ve 1s bir dizi ve aslında herhangi bir anlamı yoktur. Karakter dizelerine birleştirmek sadece 0 ve 1'li serileri daha uzun sürer. Sonuç olarak, iki dizgeyi karşılaştırmak, bir insanın bir bakışta görebileceği bir şey, bir bilgisayar içinde zaman alabilir ve konjugasyonlar arasında muhtemelen karışıklık olabilir. Örneğin, algoritmayı oluştururken dikkatli olmadıkça, bir bilgisayar enlist ve 'ı şaşırtabilir. Daha da önemlisi, bilgisayar ikisinin arasındaki farkı ayırt etmek için zamana ihtiyaç duyacaktır. Ayırıcı kelimeler problemi, kelime ayrımı yapmak için mümkün olan en küçük (ve en hızlı) olası algoritmayı (bu durumda deterministik bir sonlu otomat, DFN) bulmayı amaçlamaktadır.Hedef, belirli bir uzunluğa sahip iki sözcük verilen bir sözcüğü kabul etmek ve bir başkasını reddetmektir.

Bir uygulamanın bitmesi gerekip gerekmediğinin belirlenmesi> Alan Turing'in 1936'da öne sürdüğü sorunlardan biri, bir programın ve girdinin bir açıklaması verilen bir algoritmanın programın sonuçta durup bozulmayacağını belirleyebileceği

durma sorunu). Basit bir uygulama ile çalışırken, çoğu durumda programın durup durmayacağını veya bitmeden bir döngüde çalışmaya devam edip etmeyeceğini kolayca tespit etmek mümkündür. Bununla birlikte, program karmaşıklığı arttıkça, programın herhangi bir girdi ile yürütülmesinin sonuçlarının belirlenmesi daha zor hale gelir. Bir Turing makinesi bu tespiti yapamaz; Sonuç, sonsuz döngülere sahip buggy kodudur. Mevcut teknolojiyi kullanan herhangi bir test yapılmaz bu sorunu çözebilir. Bir hiper bilgisayar, durma sorunu gibi sorunları çözmek için Turing makinesinin ötesine geçen bir hesaplama modelidir. Bununla birlikte, bu tür makineler mevcut teknoloji kullanılarak mümkün değildir. Mümkün olsaydı, bilgisayarların şu anda cevaplayamadığı her türlü öngörülemeyen şeyi onlara sorma imkanınız olurdu. Bu makale, birisi bu sorunu çözdüyse ne olacağına dair iyi bir fikrinizi sunar.

Tek yönlü işlevler oluşturma ve kullanma

Tek yönlü işlev, tek yönlü bir yanıt elde etmek için kullanımı kolay, ancak bu yanıtı tersine çevirmek neredeyse imkansız olan bir işlevdir. Başka bir deyişle, şifreleme, kişisel tanımlama, kimlik doğrulama veya diğer veri güvenliği ihtiyaçları için bir çözümün parçası olarak görünecek bir karma gibi bir şey oluşturmak için tek yönlü bir işlev kullanırsınız.

Tek yönlü bir işlevin varlığı daha az gizlidir ve daha çok bir kanıt meselesidir. Birçok telekomünikasyon, e-ticaret ve e-bankacılık sistemleri halen bir yönde olan işlevlere güveniyor, ancak kimse gerçekten tek bir yol olup olmadığını bilmiyor. Tek yönlü bir fonksiyonun varlığı şu anda bir hipotez, bir teori değil. Birisi tek yönlü bir işlev bulunduğunu kanıtlayabilseydi, veri güvenliği sorunlarının programlama perspektifinden çözülmesi daha kolay olurdu.

Gerçekten çok sayıda çarpma

Pek çok yerde çok büyük sayılar var. Örneğin, Mars'a veya belki Pluto'ya mesafeleri içeren hesaplamaları yapmayı düşünün. Yöntemler şu anda çok büyük sayılar üzerinde çarpma işlemi yapmak için var olmaktadır, ancak tamamlamak için birden çok işlem gerektirdikleri için yavaş olma eğilimindedirler. Sorun, sayılar işlemci kayıtlarına sığmayacak kadar büyük olduğunda ortaya çıkar. Bu noktada, çarpma, birden fazla adımda gerçekleşmelidir; bu, şeyleri önemli derecede yavaşlatır. Mevcut çözümler şunları içerir:

Gauss karmaşık çarpma algoritması

• Karatsuba çarpımı
• Toom-Cook
• Fourier dönüşümü yöntemleri
• Halihazırdaki birçok yöntem kabul edilebilir sonuçlar verir, ancak hepsi zaman alır ve Yapacak çok hesaplamalarınız olduğunda, zaman sorunu kritik hale gelebilir. Sonuç olarak, çok sayıdaki çarpma, bugün mevcut olanlardan daha iyi bir çözüm gerektiren sorunlardan biridir.

Bir kaynağı eşit derecede bölme

Kaynakları eşit derecede paylaşmak zor görünmeyebilir, ancak kıskanç sıralama olan insanlar, herkesi bölünmenin adil olduğunu adil bir şekilde bölüştürmenin bir yolunu bulamazsanız, kaynağı eşit olmayan bir şekilde bölünmüş olarak görebilir. Bu, gıpta sahibi olmayan kek kesme problemidir. Elbette, bir pastayı kestiklerinde ne yapmaya kalkarsanız yapın, bölünmenin haksız olduğuna dair bir algı var. Adil bir kaynak dağılımı yaratmak, her organizasyonda menfaat sahipleri arasındaki çekişmeyi en aza indirgemek, herkesi daha verimli hale getirmek için günlük yaşamda önemlidir.

Zevksiz kek kesme problemi için belli sayıda insanla iki çözüm zaten var, ancak genel bir çözüm mevcut değil. Katılan iki kişi olduğunda, ilk önce kek kesilir ve ikincisi ilk parçayı seçer. Bu şekilde, her iki taraf da eşit bir bölünmeye tabi tutulur. Sorun üç kişi ile zorlaşıyor, ancak sorun için Selfridge-Conway çözümünü deneyebilirsiniz. Bununla birlikte, dört kişiden sonra hiçbir çözüm bulunmuyor.

Düzenleme mesafesi hesaplama süresinin azaltılması

İki dizge arasındaki

düzenleme mesafesi, bir dizeyi diğer dize haline dönüştürmek için gereken işlem sayısıdır. Mesafe hesaplaması, dizgedeki bir karakterin kaldırılması, eklenmesi veya yerine konması olan Levenshtein mesafe işlemleri etrafında döner. Bu özel teknik, doğal dil arayüzlerinde, DNA dizisi kantifikasyonunda ve bir tür karşılaştırma veya tadilat gerektiren iki benzer dizeye sahip olabileceğiniz her yerde kullanımını görür. Şu anda bu sorun için bir takım çözümler var, hepsi oldukça yavaş. Aslında, çoğu üstel zaman alır, bu nedenle dönüşüm gerçekleştirmek için gereken süre hızlı bir şekilde, insanların girdi işlemlerinde duraklamaları görebileceği noktaya kadar varır. Otomatik sözcük denetimleri gerçekleştiren ve yanlış yazılan bir sözcüğü doğru olana çeviren bir sözcük işlemci kullanıldığında duraklama o kadar da kötü değildir. Bununla birlikte, ses arabirimlerini kullanırken duraklama oldukça gözle görülür hale gelebilir ve insan operatörünün hatalar yapmasına neden olabilir.

Sorunların çabucak çözülmesi

Makine öğrenimi başladığında ve sorunları çözmek için bilgisayarlara giderek daha fazla katlandıkça, bir bilgisayarın sorunu ne kadar çabuk çözebileceği konusu kritik önem taşıyor. P'ye karşı NP problemi, bir sorunun çözülmesini hızlı bir şekilde doğrulayabildiğinde, bir bilgisayarın sorunu hızlıca çözüp çözemeyeceğini sorar. Diğer bir deyişle, bilgisayar bir sorunun insan tarafından bir tepkisinin polinom zamanında veya daha az olduğu konusunda makul bir şekilde tespit edebiliyorsa, sorunun kendisini polinom zamanında veya daha az çözünebilir mi?

Bu soru 1950'lerde John Nash tarafından Ulusal Güvenlik Ajansı'na (NSA) gönderildi ve yine Kurt Gödel ve John von Neumann arasındaki mektuplarda tartışıldı. Makine öğrenimine (ve AI genel olarak) ek olarak, bu özel problem, matematik, kriptografi, algoritma araştırması, oyun teorisi, multimedya işleme, felsefe ve ekonomi de dahil olmak üzere diğer birçok alanda bir endişe kaynağıdır.

Eşlik oyunu oynamak

İlk önce, bir oyunu çözmek, gerçek hayatta bu kadar yararlı görünmeyebilir. Evet, oyunlar eğlenceli ve ilginç, ancak faydalı bir şey yapmak için gerçekten bir arka plan sağlamıyorlar - en azından genel teori bu. Bununla birlikte, oyun teorisi, birçoğu gerçek süreçlerden çok oyunlardan daha kolay anlaşabilen karmaşık süreçleri içeren çok sayıda gerçek hayat senaryosunda oynanır. Bu durumda oyun insanlara otomatik doğrulama ve kontrolör sentezini anlamalarına yardımcı olur. Eşlik oyunu hakkında daha fazla bilgi okuyabilirsiniz. Aslında oynayabilirsiniz.

Mekansal sorunları anlama

Bu problemi bağlam içine koymak için, depoların etrafında kutuları hareket ettirmeyi veya hareket ettikleri alanı dikkate almanız gereken bazı durumlarda düşünün. Açıkçası, büyük bir depoda birçok kutu varsa ve hepsi pick up yapmak için bir forklift gerektiriyorsa, onları fiziksel olarak yeniden düzenleyerek en uygun şekilde nasıl saklayacaklarını anlamaya çalışmak istemiyorsunuzdur. Burada, bir çözümü görselleştirerek sorunu çözmeniz gerekiyor.

Bununla birlikte, soru bütün uzamsal sorunların bir çözümünün olup olmadığıdır. Bu durumda, küçük taşları kaydırarak bir araya getiren çocuk bulmacalarından birini düşünün. Sanki her durumda bir çözüm mevcut gibi görünüyor, ancak bazı durumlarda kötü bir başlangıç ​​noktası hiçbir çözüm bulamayan bir duruma neden olabilir.

Sam Loyd gibi matematikçiler karmaşık matematik problemlerini göstermek için sıklıkla bazıları bugün hiçbir çözüm bulamayan bulmacalar kullanırlar. Bu siteleri ziyaret etmek çok eğlenceli çünkü sadece bazı ücretsiz eğlenceler değil, aynı zamanda düşünce için yiyecekler alıyorsunuz. Bu bulmacaların yükselttiği sorunların pratik uygulamaları var, ancak eğlenceli bir şekilde sunuluyor.