Gedanken zum Fundament des Informatikturms Jrg Nievergelt, ETH Zrich, 1995AnwendungenSystem RealisierungAlgorithmikTheorielanglebig$$$$$

Gedanken zum Fundament des Informatikturms Jrg Nievergelt, ETH Zrich, 1995Anwendungen: das Gesicht der Informatik Marketing & Verkauf; Installation & BetriebSystem-Realisierung: ProjekteProgrammierung, ProjektleitungAlgorithmik: klein, aber fein! Forschung & EntwicklungTheorie: was ewig whrt Die Grbler

AnwendungenSystem-RealisierungAlgorithmikTheorie

Warum wir nur einen kurzen Abstecher in die theoretische Informatik machen I would advise students to pay more attention to the fundamental ideas rather than the latest technology. The technology will be out-of-date before they graduate. Fundamental ideas never get out of date. However, what worries me about what I just said is that some people would think of Turing machines and Goedel's theorem as fundamentals. I think those things are fundamental but they are also nearly irrelevant. I think there are fundamental design principles, for example structured programming principles, the good ideas in "Object Oriented" programming, etc.

David Parnas (1999). Software Engineering Notes, Vol. 24, No. 3. http://www.sigsoft.org/SEN/parnas.html.

Beispiel: Wie sicher ist mein Geld ... ?Oder anders gefragt: wie schwierig ist es, die Verschlsselung zu knacken?

Beispiel: Willst Du mich heiraten?

... und wenn sie nicht gestorben sind, so leben sie ...Eine mgliche stabile Verheiratung: alle sind glcklich verheiratet!

... noch heute ...Eine mgliche stabile Verheiratung: alle sind glcklich verheiratet!

Probleme, Probleme!P effizient lsbare ProblemeGibt es eine stabile Verheiratung?

Von Igeln und von Hasen was heisst hier effizient?

Die 1000000 US$ FrageEigenschaft von NP-vollstndigen Problemen:

wenn jemand fr eines davon eine effiziente Lsung findet, wre das der Beweis dafr, dass alle NP-Probleme effizient gelst werden knnen: P = NP!P = NP oder P # NP ?

Theorie: Was tun Informatiker?Auguste Rodin, Der DenkerSie denken.

Sie grbeln.

Sie beweisen.

Vielleicht.

Sie verffentlichen.

In obskuren Zeitschriften.

Grundsatzfragen der InformatikWelche Probleme knnen mit gegebenen Mittelnberhaupt gelst werden ?Welche Probleme knnen mit welchen Mitteln wie effizient gelst werden?abhngig vom Programmiermodell:

Automaten Turingmaschinen Quantencomputer Bio-Computer ? ?

Berechnungsmodell oder: Was kann Kara, was kann er nicht?Abhngig von Annahme:

Read-Only World: Kara darf die Welt nicht verndern Endlicher Automat2. In-Place Memory World: Kara darf einen beschrnkten Bereich der Welt verndern Spezialfall Linear Bounded Automaton 3.Read-Write World: Kara darf die Welt beliebig verndern Turing-Maschine (bei unbeschrnkter Weltgrsse)

... und trotzdem kann er einige interessante Aufgaben lsen! Read-Only World

... und trotzdem kann er einige interessante Aufgaben lsen!In-Place Memory WorldRead-Only World

... und trotzdem kann er einige interessante Aufgaben lsen!In-Place Memory WorldRead-Only World

... aber es gibt auch unlsbare Aufgaben! In-Place Memory WorldRead-Only WorldRead-Write Memory World

Beispiel: Raum parkettieren

Beispiel: Raum parkettierenbeliebig geformte Rume: es scheint intuitiv unmglich zu sein... gibt es dafr einen Beweis?

... und was ist mit Hindernissen in den Rumen?

Kara kann es eben doch!Den Beweis dafr liefert: Horst Mller: A One-Symbol Printing Automaton Escaping from every labyrinth. Computing 19, 95-110 (1977).(Mehr Information auf der Webseite zu Kara.)

Die Kernidee des AlgorithmusMan will Backtracking implementieren. Eigentlich msste man dazu auf ein Feld einen Pfeil legen knnen: von daher ist Kara gekommen.

Das wird simuliert, indem vier Felder zu einem Makrofeld zusammengefasst werden. Dann berlegt man sich die Kombinationen von diesen Feldern mit Kara, Kleeblttern und Bumen eine clevere und nicht-triviale Auswahl dieser Kombinationen implementiert man dann als Pfeile. Und schon kann man Backtracking implementieren... Hinweis: ein JavaKara-Programm, das das Verfahren umsetzt, ist rund 20 Seiten lang...(Stark vereinfacht!)

Beispiel: Raum parkettierenbeliebig geformte Rume, mit beliebig geformten Hindernissen:

und es geht doch wenn Kara wrfeln darf...Kara kann auch nicht-deterministische Automaten ausfhren...