{"id":20792,"date":"2012-08-21T13:28:15","date_gmt":"2012-08-21T11:28:15","guid":{"rendered":"https:\/\/astrodicticum-simplex.ulrich.digital\/index.php\/2012\/08\/21\/am-anfang-war-das-problem\/"},"modified":"2025-05-14T16:10:48","modified_gmt":"2025-05-14T14:10:48","slug":"am-anfang-war-das-problem","status":"publish","type":"post","link":"https:\/\/astrodicticum-simplex.ulrich.digital\/index.php\/2012\/08\/21\/am-anfang-war-das-problem\/","title":{"rendered":"Am Anfang war das Problem"},"content":{"rendered":"

W\u00e4hrend meiner Auszeit<\/a> erscheinen hier einige Gastbeitr\u00e4ge von anderen Bloggern. Wenn ihr auch Lust habt, euer Blog (euren Podcast, euer Videoblog, etc) hier vorzustellen oder einfach nur mal einen Artikel schreiben wollt, dann macht mit<\/a>!<\/p>\n

Heute gibt es einen Artikel von Moritz Moxter, Autor des Blogs 7tupel.net<\/a>.<\/p>\n

\n


\nAls Informatiker m\u00f6chte ich mir heute die Zeit nehmen darauf einzugehen was aus Sicht des Informatikers ein Problem ist. Dabei geht es nicht um ein bestimmtes Problem, sondern um die generelle Frage nach allen Problemen.<\/p>\n

Die Informatik ist eine Wissenschaft die sich in erste Linie damit besch\u00e4ftigt Probleme zu analysieren und – wenn m\u00f6glich – zu l\u00f6sen. Es geht anders als die meisten Menschen zun\u00e4chst vermuten nicht<\/strong> um Computer. Der Computer ist vielmehr ein Hilfsmittel, vergleichbar mit dem Teleskop in der Astronomie: Hier geht es schlie\u00dflich auch nicht um Teleskope, diese sind blo\u00df ein Hilfsmittel. Probleme k\u00f6nnen sehr unterschiedlich sein. Einige davon begenen uns jeden Tag, zu den bekannteren geh\u00f6ren z.B. das Finden der k\u00fcrzesten Verbindung zwischen zwei Orten (Navigationsystem). Aber dar\u00fcber hinaus gibt es noch viele andere Probleme die uns zwar st\u00e4ndig begegnen, die wir aber nicht weiter wahrnehmen. Und wieder andere Probleme haben in unserem Alltag keine Relevanz, oder nur in einigen wenigen F\u00e4llen.<\/p>\n

Aber was ist jetzt eigentlich ein Problem? Ein Problem kann man ganz einfach als die Suche nach der Antwort zu einer Frage beschreiben. Die Frage kann dabei unterschiedlicher Natur sein, zB. wie oben genannt die Frage nach der k\u00fcrzesten Strecke, um von einem Punkt auf einer Karte zu einem anderen zu kommen. Oder abstrakter formuliert: der Pfad in einem gerichteten und gewichteten Graphen mit den geringesten Kosten c von einem Blatt n zu einem zweiten Blatt n‘ \u00fcber k Kanten.<\/p>\n

Jetzt m\u00f6chten wir Probleme aber zun\u00e4chst auf m\u00f6glichst allgemeiner Ebene betrachten. Das ist zun\u00e4chst schwierig, da es sehr viele unterschiedliche Probleme gibt, deren L\u00f6sungen man auf unterschiedliche Art und Weise beschreiben kann oder auch muss. Wir m\u00fcssen Formalisieren. Anstatt von einem Problem zu reden und nach dessen L\u00f6sung zu suchen formulieren wir stattdessen: Ist die gegebene L\u00f6sung eine valide L\u00f6sung f\u00fcr unser Problem?<\/em><\/p>\n

Diese Umformulierung ver\u00e4ndert nicht die Problemstellung, aber die Antwort auf die Frage wird deutlich vereinfacht. Statt bei jedem Problem Antworten unterschiedlicher Art und Weise zu bekommen, k\u00f6nnen wir uns jetzt auf die Antworten Ja und Nein einschr\u00e4nken, ohne uns selbst zu beschneiden. Weiter formalisieren wir unser Problem als die Berechnung einer Funktion f(x)<\/strong> mit der L\u00f6sung y<\/strong>. Unsere Fragestellung ist jetzt also „ist y = f(x) ?<\/em>„. Noch formaler sieht das dann so aus:<\/p>\n

\"\"<\/a><\/p>\n

Ein paar Worte zur Erkl\u00e4rung:<\/p>\n

Die Definition ist eine ganz normale Funktionsdefinition, wie man sie auch aus dem Schulunterricht kennen sollte. Auf der linken Seite steht die Basismenge, von der aus wir auf unsere L\u00f6sungsmenge (rechts) abbilden. Unsere L\u00f6sungsmenge ist in diesem Fall sehr einfach. Da wir vorher festgestellt haben, das wir uns auf die Antworten Ja<\/em> und Nein<\/em> beschr\u00e4nken k\u00f6nnen enth\u00e4lt unsere L\u00f6sungsmenge genau zwei Elemente: die 0 als die Antwort Nein und die 1 als Antwort Ja.<\/p>\n

Die Menge auf der linken Seite ist schon etwas komplexer. Das *<\/strong> an dieser Stelle ist nicht der \u00fcbliche Operator f\u00fcr Multiplikation, sondern der Kleene-Star. Die Menge {0,1}*<\/em> entspricht hier der Menge der m\u00f6glichen L\u00f6sungen des Problems das wir betrachten (diese kann wie hier formal definiert bin\u00e4r codiert sein ohne Einschr\u00e4nkungen in Kauf zu nehmen).<\/p>\n

Wichtig ist, dass die Menge {0,1}* eine abz\u00e4hlbar unendliche Menge ist. Das bedeutet, wenn wir uns unendlich viel Zeit nehmen, dann k\u00f6nnten wir alle (unendlich vielen) Elemente der Menge nacheinander aufz\u00e4hlen.<\/p>\n

Jetzt haben wir aber nur genau ein Problem und seine m\u00f6glichen L\u00f6sungen betrachtet. Die Menge aller Probleme entspricht der Potenzmenge der Menge {0,1}*. Und gleich hier fangen unsere Probleme an. Denn nach Cantors zweitem Diagonalargument<\/a> ist die Potenzmenge einer beliebigen Grundmenge stets m\u00e4chtiger als die Grundmenge (=sie hat mehr Elemente). Da wir aber festgestellt haben, das {0,1}* bereits abz\u00e4hlbar unendlich viele Elemente enth\u00e4lt, muss deren Potenzmenge \u00fcberabz\u00e4hlbar unendlich viele Elemente enthalten. Eine \u00fcberabz\u00e4hlbar unendliche Menge bringt jedoch das Problem mit sich, dass wir die Elemente nicht mehr alle aufz\u00e4hlen k\u00f6nnen (Florian hat hierzu vor ein paar Wochen ein sch\u00f6nes Video<\/a> verblogt).<\/p>\n

Diese Erkenntnis f\u00fchrt uns zu einem Dilemma: Jedes m\u00f6gliche Computerprogramm besteht aus einer endlichen Folge von Zeichen. Die Menge aller Programme die m\u00f6glich sind muss also abz\u00e4hlbar unendlich sein. Aber oben haben wir festgestellt, das es \u00fcberabz\u00e4hlbar unendlich viele Probleme gibt. Die Konsequenz daraus ist die Tatsache, das es mehr Probleme gibt als L\u00f6sungen. Es wird also immer Probleme geben, die wir niemals<\/strong> mit einem Computer l\u00f6sen k\u00f6nnen.<\/p>\n","protected":false},"excerpt":{"rendered":"

W\u00e4hrend meiner Auszeit erscheinen hier einige Gastbeitr\u00e4ge von anderen Bloggern. Wenn ihr auch Lust habt, euer Blog (euren Podcast, euer Videoblog, etc) hier vorzustellen oder einfach nur mal einen Artikel schreiben wollt, dann macht mit! Heute gibt es einen Artikel von Moritz Moxter, Autor des Blogs 7tupel.net.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[235,11,12],"tags":[7161,9149,302,15012],"class_list":["post-20792","post","type-post","status-publish","format-standard","hentry","category-geistes-sozialwissenschaften","category-naturwissenschaften","category-technik","tag-informatik","tag-losbarkeit","tag-mathematik","tag-unendlichkeit"],"_links":{"self":[{"href":"https:\/\/astrodicticum-simplex.ulrich.digital\/index.php\/wp-json\/wp\/v2\/posts\/20792","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/astrodicticum-simplex.ulrich.digital\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/astrodicticum-simplex.ulrich.digital\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/astrodicticum-simplex.ulrich.digital\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/astrodicticum-simplex.ulrich.digital\/index.php\/wp-json\/wp\/v2\/comments?post=20792"}],"version-history":[{"count":1,"href":"https:\/\/astrodicticum-simplex.ulrich.digital\/index.php\/wp-json\/wp\/v2\/posts\/20792\/revisions"}],"predecessor-version":[{"id":20793,"href":"https:\/\/astrodicticum-simplex.ulrich.digital\/index.php\/wp-json\/wp\/v2\/posts\/20792\/revisions\/20793"}],"wp:attachment":[{"href":"https:\/\/astrodicticum-simplex.ulrich.digital\/index.php\/wp-json\/wp\/v2\/media?parent=20792"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/astrodicticum-simplex.ulrich.digital\/index.php\/wp-json\/wp\/v2\/categories?post=20792"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/astrodicticum-simplex.ulrich.digital\/index.php\/wp-json\/wp\/v2\/tags?post=20792"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}