10 Noch zu lösende algorithmische Probleme - Dummies

Algorithmen gibt es zwar schon seit Jahrhunderten, man könnte also meinen, dass Wissenschaftler bis jetzt jeden Algorithmus entdeckt und gelöst hätten. Leider ist das Gegenteil der Fall. Das Lösen eines bestimmten Algorithmus stellt oft einige weitere Fragen, die der Algorithmus nicht löst und die nicht offensichtlich erschienen, bis jemand die Lösung gefunden hat.

Algorithmen sind eine Reihe von Schritten, die verwendet werden, um ein Problem zu lösen, und Sie sollten sie nicht mit anderen Entitäten wie Gleichungen verwechseln. Ein Algorithmus ist niemals eine Lösung bei der Suche nach einem Problem. Niemand würde eine Reihe von Schritten erstellen, um ein Problem zu lösen, das noch nicht existiert (oder niemals existiert).

Diese Liste befasst sich mit algorithmischen Problemen, die einem Zweck dienen könnten, sollte jemand eine Lösung für sie finden.

Umgang mit Textsuchen

Bei vielen Textsuchen werden reguläre Ausdrücke verwendet - eine Art Kurzschrift, die dem Computer mitteilt, was er finden soll. Die Grammatik, die für den regulären Ausdruck verwendet wird, hängt von der Sprache oder Anwendung ab, aber Sie finden reguläre Ausdrücke an mehreren Stellen, einschließlich Textverarbeitungsprogrammen, E-Mail-Anwendungen, Suchdialogen und an allen anderen Stellen, an denen Sie eine präzise Suche durchführen müssen. Begriffe für eine Reihe von Textelementen.

Eines der aktuellen Probleme bei regulären Ausdrücken besteht darin, dass es so aussieht, als ob jede Anwendungsumgebung ein ähnliches Regelwerk hat, aber gerade so viele Unterschiede aufweist, dass das Erstellen eines Suchbegriffs schwierig wird. Das verallgemeinerte Sternhöhenproblem versucht herauszufinden, ob eine verallgemeinerte Syntax für reguläre Ausdrücke existiert. Wenn dies der Fall ist, würde der resultierende Algorithmus es jemandem ermöglichen, nur eine Methode zum Erstellen regulärer Ausdrücke zu erlernen, um Suchen durchzuführen.

Unterscheidende Wörter

Bei der Arbeit mit Zeichen sieht ein Computer Zahlen statt Buchstaben. Die Zahlen sind eigentlich nur eine Folge von Nullen und Einsen zum Computer und haben eigentlich keine Bedeutung. Das Kombinieren von Zeichen zu Strings macht die Reihe von Nullen und Einsen länger. Folglich kann der Vergleich zweier Strings, etwas, das ein Mensch auf einen Blick erledigen kann, innerhalb eines Computers Zeit in Anspruch nehmen, und Verwirrung ist wahrscheinlich zwischen Konjugaten. Zum Beispiel könnte ein Computer enlist und zuhören, wenn Sie nicht vorsichtig beim Erstellen des Algorithmus sind. Noch wichtiger ist, dass der Computer Zeit braucht, um den Unterschied zwischen den beiden zu erkennen. Das Problem der Trennwörter versucht, den kleinsten (und schnellsten) möglichen Algorithmus (einen deterministischen endlichen Automaten, in diesem Fall DFN) zu finden, um eine Worttrennung durchzuführen.Das Ziel besteht darin, ein Wort zu akzeptieren und ein anderes Wort zurückzuweisen, wenn zwei Wörter einer bestimmten Länge gegeben sind.

Feststellen, ob eine Anwendung endet

Eines der Probleme, das Alan Turing 1936 vorgeschlagen hat, ist die Frage, ob ein Algorithmus bei einer Beschreibung eines Programms und einer Eingabe bestimmen könnte, ob das Programm schließlich Halteproblem). Wenn Sie mit einer einfachen Anwendung arbeiten, ist es in vielen Fällen einfach festzustellen, ob das Programm angehalten wird oder in einer Endlosschleife weiterläuft. Wenn jedoch die Programmkomplexität zunimmt, wird es schwieriger, das Ergebnis der Ausführung des Programms mit irgendeiner gegebenen Eingabe zu bestimmen. Eine Turingmaschine kann diese Bestimmung nicht machen; Das Ergebnis ist ein fehlerhafter Code mit Endlosschleifen. Keine Testmenge, die aktuelle Technologie verwendet, kann dieses Problem lösen.

Ein Hypercomputer ist ein Rechenmodell, das über die Turing-Maschine hinausgeht, um Probleme wie das Halteproblem zu lösen. Solche Maschinen sind jedoch mit der derzeitigen Technologie nicht möglich. Wenn es möglich wäre, könnten Sie alle möglichen Unwägbarkeiten erfragen, die Computer derzeit nicht beantworten können. Dieser Artikel gibt Ihnen eine gute Vorstellung davon, was passieren würde, wenn jemand in der Lage wäre, dieses Problem zu lösen.

Erstellen und Verwenden von Einwegfunktionen

Eine Einwegfunktion ist eine Funktion, die einfach zu verwenden ist, um eine Antwort in eine Richtung zu erhalten, aber mit der Umkehrung dieser Antwort fast unmöglich zu verwenden ist. Mit anderen Worten, Sie verwenden eine Einwegfunktion, um so etwas wie einen Hash zu erstellen, der als Teil einer Lösung für Kryptografie, persönliche Identifizierung, Authentifizierung oder andere Datensicherheitsanforderungen erscheinen würde.

Die Existenz einer Einwegfunktion ist weniger geheimnisvoll und eher eine Frage des Beweises. Viele Telekommunikations-, E-Commerce- und E-Banking-Systeme verlassen sich derzeit auf Funktionen, die angeblich ein Weg sind, aber niemand weiß wirklich, ob sie wirklich ein Weg sind. Die Existenz einer Einwegfunktion ist derzeit eine Hypothese, keine Theorie. Wenn jemand beweisen könnte, dass eine Einbahnfunktion vorhanden ist, wären Probleme mit der Datensicherheit aus Programmierungsperspektive leichter zu lösen.

Multiplizieren von wirklich großen Zahlen

An vielen Stellen gibt es wirklich große Zahlen. Betrachten Sie zum Beispiel die Berechnungen mit Entfernungen zum Mars oder Pluto. Es gibt derzeit Methoden, um eine Multiplikation mit wirklich großen Zahlen durchzuführen, aber sie neigen dazu, langsam zu sein, weil sie mehrere Operationen benötigen, um abgeschlossen zu werden. Das Problem tritt auf, wenn die Zahlen zu groß sind, um in die Register des Prozessors zu passen. Zu diesem Zeitpunkt muss die Multiplikation in mehr als einem Schritt erfolgen, was die Dinge erheblich verlangsamt. Die aktuellen Lösungen umfassen:

• Gauss komplexer Multiplikationsalgorithmus
• Karatsuba-Multiplikation
• Toom-Cook
• Fourier-Transformationsmethoden

Auch wenn viele der derzeit verfügbaren Methoden akzeptable Ergebnisse liefern, brauchen sie alle Zeit und Wenn Sie viele Berechnungen durchführen müssen, kann das Zeitproblem kritisch werden. Folglich ist die Multiplikation großer Zahlen eines jener Probleme, die eine bessere Lösung erfordern als die heute verfügbaren.

Eine Ressource gleichmäßig teilen

Gleiche Ressourcen zu teilen scheint nicht schwer zu sein, aber Menschen, die neidisch sind, könnten die Ressource ungleich geteilt sehen, es sei denn, Sie können einen Weg finden, allen zu versichern, dass die Spaltung in Ordnung ist. Das ist das neidfreie Kuchenschneidproblem. Natürlich, wenn Sie einen Kuchen schneiden, egal wie fair Sie versuchen, es zu tun, gibt es immer die Wahrnehmung, dass die Teilung unfair ist. Eine faire Aufteilung der Ressourcen ist im täglichen Leben wichtig, um Konflikte zwischen den Stakeholdern in jeder Organisation zu minimieren und alle Beteiligten effizienter zu machen.

Es gibt bereits zwei Lösungen für das neidfreie Kuchenschneidproblem mit einer bestimmten Anzahl von Personen, aber es gibt keine allgemeine Lösung. Wenn zwei Personen involviert sind, schneidet der erste den Kuchen und der zweite das erste Stück. Auf diese Weise wird beiden Parteien eine gleiche Aufteilung gewährleistet. Das Problem wird mit drei Leuten schwieriger, aber Sie können die Selfridge-Conway Lösung für das Problem versuchen. Nachdem Sie jedoch zu vier Personen gekommen sind, existiert keine Lösung.

Reduzieren der Editierdistanz-Berechnungszeit

Die Editierdistanz zwischen zwei Zeichenketten ist die Anzahl der Operationen, die erforderlich sind, um eine Zeichenkette in die andere Zeichenkette zu transformieren. Die Entfernungsberechnung dreht sich um die Levenshtein-Entfernungsoperationen, die das Entfernen, Einfügen oder Ersetzen eines Zeichens in der Kette sind. Diese spezielle Technik wird in natürlichsprachlichen Interfaces, bei der Quantifizierung von DNA-Sequenzen und an allen möglichen anderen Stellen verwendet, an denen Sie zwei ähnliche Strings haben können, die eine Art Vergleich oder Modifikation erfordern.

Derzeit gibt es eine Reihe von Lösungen für dieses Problem, die alle sehr langsam sind. Tatsächlich nehmen die meisten von ihnen exponentielle Zeit in Anspruch, so dass die Zeit, die zum Ausführen einer Transformation benötigt wird, schnell zu dem Punkt summiert, an dem Menschen Pausen in der Verarbeitung von Eingaben sehen können. Die Pause ist nicht ganz so schlimm, wenn ein Textverarbeitungsprogramm verwendet wird, das automatische Wortprüfungen durchführt und ein falsch geschriebenes Wort in das richtige Wort umwandelt. Wenn jedoch Sprachschnittstellen verwendet werden, kann die Pause sehr auffällig werden und den menschlichen Bediener veranlassen, Fehler zu machen.

Probleme schnell lösen

Wenn maschinelles Lernen beginnt und wir mehr und mehr auf Computer zählen, um Probleme zu lösen, wird die Frage, wie schnell ein Computer ein Problem lösen kann, kritisch. Das P versus NP-Problem fragt einfach, ob ein Computer ein Problem schnell lösen kann, wenn er die Lösung des Problems schnell verifizieren kann. Mit anderen Worten, wenn der Computer vernünftigerweise feststellen kann, dass eine menschliche Antwort auf ein Problem in polynomieller Zeit oder weniger korrekt ist, kann er das Problem dann selbst in polynomieller Zeit oder weniger lösen?

Diese Frage wurde ursprünglich in den 1950er Jahren von John Nash in Briefen an die National Security Agency (NSA) und erneut in Briefen zwischen Kurt Gödel und John von Neumann diskutiert. Neben dem maschinellen Lernen (und AI im Allgemeinen) ist dieses spezielle Problem in vielen anderen Bereichen von Belang, einschließlich Mathematik, Kryptographie, Algorithmenforschung, Spieltheorie, Multimedia-Verarbeitung, Philosophie und Wirtschaft.

Das Parity-Spiel

spielen Zunächst scheint das Lösen eines Spiels im wirklichen Leben nicht besonders nützlich zu sein. Ja, Spiele sind lustig und interessant, aber sie bieten nicht wirklich einen Hintergrund, um etwas Nützliches zu tun - zumindest ist das die allgemeine Theorie. Die Spieltheorie spielt jedoch in einer großen Anzahl realer Szenarien eine Rolle, von denen viele komplexe Prozesse beinhalten, die jemand leichter als Spiele verstehen kann als als tatsächliche Prozesse. In diesem Fall hilft das Spiel den Leuten unter anderem dabei, automatisierte Verifikation und Controller-Synthese zu verstehen. Sie können mehr über das Paritätsspiel lesen. In der Tat können Sie es spielen.

Räumliche Probleme verstehen

Um dieses spezielle Problem in einen Zusammenhang zu bringen, denken Sie darüber nach, Kisten in einem Lagerhaus zu bewegen oder in anderen Situationen, in denen Sie den Raum betrachten müssen, in dem sich Dinge bewegen. Wenn Sie viele Kisten in einem großen Lagerhaus haben und alle einen Gabelstapler benötigen, wollen Sie natürlich nicht versuchen, sie optimal zu lagern, indem Sie sie physisch neu anordnen. Hier müssen Sie das Problem beheben, indem Sie eine Lösung visualisieren.

Die Frage ist jedoch, ob alle räumlichen Probleme eine Lösung haben. Denken Sie in diesem Fall an eines der Rätsel dieser Kinder, bei dem Sie ein Bild zusammensetzen, indem Sie die kleinen Kacheln herumschieben. Es scheint, als ob eine Lösung in allen Fällen existieren sollte, aber in manchen Situationen kann ein schlechter Startpunkt zu einer Situation führen, die keine Lösung hat.

Mathematiker wie Sam Loyd verwenden oft Rätsel, um komplexe mathematische Probleme aufzuzeigen, von denen einige heute keine Lösung haben. Der Besuch dieser Seiten macht Spaß, weil Sie nicht nur kostenlose Unterhaltung, sondern auch Denkanstöße bekommen. Die Probleme, die diese Rätsel aufwerfen, haben praktische Anwendungen, aber sie werden auf unterhaltsame Weise präsentiert.