Das klassische Klischee, wie ich es immer wieder angetroffen habe, ist, dass ein Informatiker stuidert, wie man Word und Excel bedient, und wie man am schnellsten bei Counterstrike gewinnt und Computerdrucker anschließt. Das klingt schon komisch, und ist auch falsch! Auch die schon etwas näher liegende Meinung, ein Informatiker sei so etwas wie ein Programmierer, kann ich so nicht stehen lassen.
Es ist schwierig, das in einen Satz zu fassen, aber die Aussage „Informatik ist die Wissenschaft von der maschinellen Infomationsverarbeitung“ trifft es schon ganz gut. Das Wort „maschinell“ impliziert bereits, dass man es mit besonderen Anforderungen zu tun hat, denn eine Maschine kann sich nicht auf Intuition, Gefühle oder Lebenserfahrungen stützen. Somit muss noch etwas sehr wichtiges festgehalten werden: „Informatik ist angewandte Mathematik“, denn nur mit mathematischen Berechnungen können unsere heutigen Maschinen Aufgaben überhaupt lösen. Hinzu kommen ishcerlich auch noch weitere Wissenschaften, die den Informatikern helfen, zum Beispiel die Physik, Nachrichtentechnik, Elektrotechnik, aber das dürfte wohl in vielen Wissenschaften der Fall sein
Am Anfang vor allem und fast ausschließlich Mathematik. Ich habe in den ersten 2 Semestern praktisch nur Mathematik gehört, zwei Drittel des Studienplans wurden von Linearer Algebra und Analysis eingenommen. Wer Angst vor Mathematik hat und sich niemals zutrauen würde, mathematische Beweise zu führen, der wird praktisch unmöglich Informatik studieren können! Es ist auch falsch, zu meinen, die Mathematik diene zum „Aussieben“ von Studenten, denn daran hat eigentlich keiner Interesse. Die Mathematik, die man dort lernt, braucht man später immer wieder, und es wäre ziemlich sinnlos, die Mathematikvorlesungen an das Ende des Studium zu setzen.
Daneben lernt man in den ersten Semestern auch Programmierung (ich habe zum Beispiel die Programmiersprache Java im ersten Semester gelernt) und technische Informatik. Im weiteren Verlauf lernt man dann noch theoretische Informatik (auch die gibt es) und Algorithmik, was praktisch die Vorstellung einiger bekannter Algorithmen ist. Außerdem lernt man dort auch, wie man die Laufzeit von Algorithmen analyisiert und Algorithmen schreibt, die möglichst effizient sind.
Für Menschen scheint Sortieren kein besonders großes Problem zu sein. Gibt man jemandem einen Stapel Bücher, die er alphabetisch nach dem Autor sortieren soll, dann wird er das meistens hinkriegen. Einem Computer musss man aber sehr genau sagen, was er tun soll. Zuerst einmal muss er wissen, welche Reihenfolge das Alphabet hat. Glücklicherweise ist in praktisch jedem Computer das Alphabet schon in der uns bekannten Reihenfolge hinterlegt, so dass man sich hierum nich kümmern muss. Auch haben die meisten Programmiersprachen schon einen Vergelich von zwei Zeichenfolgen eingebaut, er kann also entscheiden, ob „Aachen“ vor „Zwickau“ liegt. Man sagt dann in mathematischer Beschreibung auch „Aachen“ < „Zwickau“.
Ein einfacher Sortieralgorithmus lautet:
Durchlaufe die gesamte Liste der zu sortierenden Einträge, und vertausche solange Einträge, die in der falschen Reihenfolge sind, bis alle Einträge in der richtigen Reihenfolge sind.
Man nennt diese Methode auch „Bubblesort“, weil dabei die falschen Einträge wie Blasen aufsteigen. Diese Methode liest sich recht vernünftig. Sie muss auch bei einer schon sortierten Liste nur einmal die Liste durchlaufen. Ist die Liste jedoch genau falschherum sortiert, so stellt man schnell fest, dass diese Methode „quadratische“ Zeit braucht, dass heißt bei 10 Einträge braucht man schon 100 Durchläufe, bei 1000 also eine Million. Das ganze sieht also ziemlich unrentabel aus.
Ein andere Algorithmus funktioniert so: Man teilt die Listen so lange in Hälfte, bis man nur noch Teillisten mit zwei Elementen hat. Dann sortiert man diese Mini-Listen und fügt diese mittels eines Reißverschlussverfahrens wieder zusammen. Man kann zeigen (genau das ist zum Beispiel ein Übungsaufgabe im Informatikstudium), dass man jetzt bei 10 Elementen nur noch 2*log(2) braucht, also ungefähr 30, bei 1000 Elementen nur noch 10000. Außerdem kann man auch noch zeigen, dass man nicht mehr besser werden kann, d.h. es gibt keinen Algorithmus, der schneller sortieren könnte, jedenfalls nicht, wenn der Algorithmus keine weiteren Vorkenntnisse hat.
Auch so eine Frage, die ich oft gehört habe. Es stört sicherlich nicht, wenn man schon programmieren kann, wenn man im Studium anfängt. Ich konnte damals schon in einigen Programmiersprachen programmieren, habe dann aber im Laufe des Studiums noch einige dazugelernt. In meiner Programmiersprachensynopse kann man sehen, dass sich die meisten Sprachen nicht so viel untereinander tun. Viel schwieriger als das eigentliche Programmieren ist das gut durchdachte Design von Programmen, denn schließlich sollen diese auch nicht nur „irgendwie“ laufen, sondern auch sicher oder erweiterbar sein. Genauso wie es keine Schwierigkeit ist, eine Bretterbude zusammenzunageln, die beim Nächsten Windstoß umfällt und die keine Tür hat, so kann man auch furchtbar schlechte Programme schreiben. Außerdem muss man immer davon ausgehen, dass auch mal jemand anderes den Code lesen oder erweitern möchte oder muss, zumindest im Berufsleben. Oft überdauert Software den ursprünglichen Programmierer. Und dann soll sie ja auch noch bedienbar sein.
Allerdings sollte man auch nicht allzuviel Angst vor dem Porgrammieren haben. Dank der OpenSource-Bewegung der vergangenen Jahre hat es sich auch Gottseidank immer mehr durchgesetzt, dass man sich den Quelltext von vielen Programmen ansehen und sich dort Sachen abkupfern kann. Und im Internet finden sich massenhaft Tutorials. Man kann es auf jeden Fall lernen!
Nein, das ist keine Voraussetzung. Während meines Studiums habe ich jedenfalls bedeutend länger vor Büchern, im Hörsaal, vor Übungsblättern und an Füller und Papier gesessen, als vor dem Computer. Dass die meisten Informatiker schon ziemliche Computerfans sind, stimmt allerdings auch. Aber Flugzeugingeneure sind oft auch ziemlich Flugzeugfans, oder?
Ja.
Dies ist eine der wichtigsten ungelösten Fragen der Informatik. Zunächst mal: Dies kryptischen Abkürzungen bedeuten: „Ist die Klasse der deterministisch polynomiell lösbaren Probleme gleich der Klasse der nicht-deterministisch lösbaren Probleme?“. Dazu muss man wissen:
Ein Problem ist in polynomieller Zeit Lösbar, wenn es eine Laufzeit hat, die durch ein Polynom beschränkt ist, d.h. die Laufzeit wächst nicht schneller als na, wobei a eine positive Zahl ist und n die Größe des Eingabeproblems. So sind die oben angesprochenen Sortieralgorithmen in polynomieller Zeit lösbar.
Eine Maschine (also ein Computer...) ist deterministisch, wenn sie nur einen Lösungsweg auf einmal berechnen kann. So funktionieren heute alle Computer. Sie ist nicht-deterministisch, wenn sie beliebig viele Wege betrachten kann, und davon auch noch immer den besten wählt. Ein solcher Computer ist nur ein Gedankenmodell!
Ein Problem liegt nun in P, wenn es auf einer deterministischen Maschine in polynomieller Zeit lösbar ist. Ein Problem liegt in NP, wenn es auf einer nicht-deterministischen Maschine in polynomieller Zeit läuft. Beide Probleme haben also die gleiche Laufzeitklasse, aber auf unterschiedlichen Rechnermodellen.
Es lassen sich leicht folgende Tatsachen einsehen:
Die nicht-deterministische kann offensichtlich schonmal alles das, was die deterministische auch kann. Darum ist auch ziemlich schnell gezeigt worden, dass P eine Teilmenge von NP ist
Man kann eine nicht-deterministische Maschine mit einer deterministischen simulieren, indem man alle Lösungen hintereinander ausprobiert. Da es man nach jedem Schritt einen anderen Lösungsweg einschlagen kann, gibt es exponentiell viele Lösungswege. Also hat ein Problem aus NP auf einer deterministischen Maschine höchstens exponenentielle Laufzeit.
Die Frage die sich nun stellt: Geht es auch besser? Denn exponentielle Laufzeit ist ziemlich haarig, weil ein Problem der Größe 10 schon 1024 Schritte, eines mit 1000 schon 21000 Schritte benötigt (dieses Zahl ist echt riesig!).
Bisher ist es niemandem gelungen, auf diese Frage eine Antwort zu finden. Folgendes steht aber fest:
Gelingt es, ein Algorithmus für ein sog. NP-vollständiges Problem zu finden, dass auf einer deterministischen Maschine inpolynomiller Zeit lösbar ist, dann ist P=NP
Gelingt es, einen Nachweis dafür zu finden, dass es keinen solchen Algorithmus geben kann, dann ist P!=NP
Ein dritte zu bedenkenden Möglichkeit ist, dass es sich nicht nachweisen lässt, ob beide Klassen gleich sind. Tatsächlich muss diese Möglichkeit auf Grund des Gödel'schen Unvollständigkeitssatzes (der besagt, dass man nicht alles beweisen kann) in Betracht gezogen werden.
Gerade die letzte Möglichkeit klingt für mich persönlich allerdings etwas kurios, weil man dann gezeigt hätte, dass man dann unter Umständen nie wüsste, ob man einen Algorithmus finden könnte...
Ein NP-vollständiges Problem ist übrigens ein solches Problem, auf das man alle anderen NP-schweren Probleme reduzieren kann, das heißt, kann man dieses Problem lösen, kann man alle mit nur „wenig“ Mehraufwand lösen. Die Bedingung hierbei ist, dass der Mehraufwand auch nur polynomiell beschränkt ist. Aus diesem Grund reicht es, einen Algorithmus für NP-vollständige Probleme zu finden, um den Beweis zu lösen.
Der allgemeine Trend geht heutzutage, gut 60 Jahre nach dem ersten Auftreten der Frage, dahin, von einer Ungleichheit der Klassen aszugehen, einfach deshalb, weil noch niemand einen passenden Algorthmus gefunden hat. Dies ist aber noch lange kein Beweis!
Ein Problem heißt NP-vollständig, wenn es
In NP liegt
Jedes andere Probleme aus NP sich in polynomieller Zeit auf dieses Problem reduzieren lässt. Das heißt also, man nimmt ein Problem, steckt es in eine polynomielles Programm rein, und erhält dann das NP-vollständige Problem
Beide Bedingungen sind dabei wichtig, weil man die Probleme aus NP auch auf Probleme aus komplexeren Klassen reduzieren könnte. Die Definition ist genau so gebastelt, dass es reicht, für ein NP-vollständiges Problem zu zeigen, dass es in P liegt, um P=NP zu beweisen. Dann kann man nämlich jedes Problem erst reduzieren und dann das bekannte Problem lösen. Da die Hintereinanderausführungen zweier Polynomialzeitalgorithmen wiederum nur polynomielle Zeit benötigt, wäre jedes Problem aus NP in P-Zeit lösbar.
Dies ist eine klassische Fehlübersetzung aus dem Englischen. Dort heißt der Begriff NP-hard und müsste eigentlich mit NP-schwer übersetzt werden. Ein Problem ist NP-schwer, wenn sich alle anderen Probleme aus NP auf dieses Problem in polynomieller Zeit reduzieren lässt. Ein NP-hartes Problem muss aber nicht zwangsläufig in NP liegen.
Ja, denn viele Probleme des täglichen Lebens sind NP-schwer. So ist zum Beispiel folgendes Problem NP-schwer: Ein Handelsreisender möchte mehrer Orte abfahren, und dies auf möglichst kurzem Weg. Allerdings möchte er jeden Ort nur einmal betreten. Wie ist seine optimale Wegstrecke?
Tatschälchlich ist die einzige Möglichkeit heutzutage, dieses Problem zu lösen, die, alle Wege auszuprobieren, was natürlich entsprechend lange dauert. Eine nicht-deterministische Maschine würde einfach den kürzesten Weg raten und dann in polynomieller Zeit die Gültigkeit prüfen (es ist immer möglich, dass es keine Lösung gibt, z.B. wenn ein Ort auf einer Insel liegt...)
Viele weitere Probleme sind NP-vollständig: Das Stundenplanproblem, das 0/1-Rucksackproblem, das Graphfärbeproblem etc.
Wenn beide Klassen ungleich sind, heißt das, dass unser Handelsmann niemals einen effizienten Algorithmus finden könnte, um sein Problem zu lösen. Wollte er 100 Stationen abfahren, so wäre er wohl schon tot, noch ehe er seine Reise antreten könnte. Aber er hat einen Ausweg: Es gibt schnelle, approximative Algorithmen, die sein Problem näherungsweise lösen. Er würde vielleicht einen nicht so optimalen Weg finden, aber immerhin einen, der zu 99% oder so an der besten Lösung liegt. Auch Quantencomputer könnten bei der Lösung von NP-Problemen helfen, da Quantencomputer mehrere Zustände gleichzeitig verarbeiten können.
Wenn wirklich P=NP, dann wären auf den ersten Blick viele Probleme, die heute noch in der Praxis nicht lösbar erscheinen, schnell gelöst. Viele Verschlüsselungsalgorithmen wären zum Beispiel in polynomieller Zeit geknackt. Aber: Polynomiell heißt noch nicht zwansgsläufig schnell. Ein Algorithmus, der in einer Zeit n10000 liegt, dauert immer noch viel zu lange, um in einer vernünftigen Zeit gelöst zu werden.
Dies hilft leider auch nicht, denn macht man einen Computer doppelt so schnell, so löst er ein NP-schweres Problem auch nicht wesentlich schneller. Statt 1000 Stationen könnte unser Handelsreisender nur 1001 Stationen in der gleichen Zeit berechnen, dies hilft ihm nicht sonderlich viel.
Nein, sie sind alle lösbar, aber es dauert halt zu lange, jedenfalls ab einer bestimmten Eingabegröße.
Ja, die gibt es definitv. So kann man das Halteproblem niemals lösen. Das Halteproblem soll für jeden Algorithmus entscheiden, ob er anhält, oder nicht. Durch einen relativ einfachen Beweis kann man zeigen, dass ein solcher Algorithmus, auf sich selbst angewandt, genau dann halten müsste, wenn er nicht anhält. Da dies widersprüchlich ist, kann es einen solchen Algorithmus nicht geben. Aber: Das gilt nur für den allgemeinsten Fall. Natürlich kann man für eine ganze Reihe von Algorithmen zeigen, dass sie anhalten, und dies sollte man auch tun.
Hier ein Beispiel für einen Algorithmus, der evtl. nie anhält:
Würfele so lange, bis eine 6 geworfen wird.
Tatsächlich ist es möglich, dass niemals eine 6 geworfen wird. Zwar strebt die Wahrscheinlichkeit dafür gegen 0, aber sie erreicht niemals die 0! Tatsächlich ist die Wahrscheinlichkeit dafür aber so gering, dass sie unter dem Transistorfehler heutiger Prozessoren liegt. Trotzdem ist die Laufzeit solcher gefährlicher Algorithmen nicht bekannt.
Übrigens ist der Beweis für die Unlösbarkeit des Halteproblems ein fundamentaler Beweis, er beruht nicht auf bestimmten Computervorstellungen oder ähnlichem. Es steht für alle Zeiten fest, dass man das Problem nicht lösen wird. Es ist nicht so, dass nur alle "zu doof" wären, es zu lösen. Ich finde das ein sehr wichtiges Ergebnis.
Das kann man genauso gut beantworten wie die Frage nach dem bestem Auto. Ein 911er ist sicherlich nicht besser und nicht schlechter als ein MAN-Truck. Jeder hat nur sein eigenes Anwendungsgebiet.
Wer jedoch eine Programmiersprache lernen möchte, dem würde ich zunächst eine der moderneren Programmiersprachen empfehlen, etwa Java, C++ oder auch C##. Der Grund liegt einfach darin, dass diese Sprachen sehr verbreitet sind, man viele Dokumentationen in Büchern und im internet findet und viele Quellcodes dazu verfügbar sind. Es gibt durchaus gegensätzliche Meinungen, die damit begründet werden, diese Sprachen enthielten zuviel „Overhead“ und Einsteigern eher alte Progammiersprachen wie Pascal ans Herz legen möchten. Dem kann ich mich schon vor dem Hitnergrund nicht anschließen, dass es kaum noch nützliche Sachen gibt, die man damit programmieren könnte. Klar, zum Lernen von Grundalgorithmen wird es sicherlich taugen, aber schnell möchte man doch auch mal ein Bild auf dem Bildschirm zeichnen, eine kleine Anwendung mit Web-Zugang schreiben etc.
Wer mit Java anfangen möchte. braucht außer der wohl meist schon vorhandenen Internet-Anbindung nicht viel zu investieren. Man lädt sich einfach das Java-SDK und Eclipse als Programmierumgebung herunter und schon kann es losgehen.
Wer mit C++ anfangen möchte, kann auch Eclipse verwenden, muss sich dann aber neben der Java-Laufzeitumgebung (hierunter läuft Eclipse) noch einen C++-Compiler, z.B. den von GNU, herunterladen. Außerdem gibt es von Microsoft auch Testversionen, die allerdings dann in ihrer Funktionalität schon eingeschränkt sind.
Wer sich nur für einfache Ein-/Ausgabeskripte interessiert, kann sich auch ruhig mal PHP ansehen. Damit muss man eigentlich nur seinen Quellcode eintippen und dann laufen lassen. Dass man damit auch ganz schnell Web-Seiten erstellen kann, sei nur am Rande erwähnt. Wer allerdings das meiste rausholen will, sollte sich auch mit Datenbanksystemen auskennen.
Zunächst einmal ist ein endlicher Automat auch meist nur ein Gedankenmodell (er lässt sich aber auch im Computer modellieren). Man geht hierbei von einem "Automaten" aus, der ein bestimmtes Wort (dies kann man sich wirklich als Zeichenkette vorstellen) erhält. Dieses Wort liest er zeichenweise ein. Nach jedem Zeichen wechselt der Automat in einen anderen Zustand. Die Übergänge sind vorher einmal festgelegt worden, und dürfen sich während des Programmablaufs nicht ändern. Auch kann sich der endliche Automat immer nur das aktuelle Zeichen ansehen, und er kann sich außer diesem Zeichen und seinem aktuellen Zustand nichts merken. Einige Zustände werden dabei als "akzeptierend" gekennzeichnet, alle anderen gelten als verwerfend (dies gilt auch, wenn der Übergang nich definiert ist).
Interessant ist bei den endlichen Automaten, dass nur eine bestimmte Teilmenge von Wörtern akzeptiert werden kann. Diese Teilmengen nennt man "Sprachen". Noch interessanter ist, dass man nicht für alle ausgedachten Sprachen einen endlichen Automaten definieren kann. So kann man für die Sprache aller Palindrome ab, abba, aabbbbaa usw. keinen Automaten definieren, weil dieser sich merken müsste, was er schon alles eingelesen hat.
Aber es geht noch komplizierter: Bei einem "normalen" endlichen Automaten (man nennt ihn auch deterministisch) ist die Übergangsfunktion stets eindeutig definiert. Man kann sich aber noch einen "nicht-deterministischen" endlichen Automaten ausdenken, der immer die optimalsten Übergänge wählt. Man könnte meinen, ein solcher Automat könne auch mehr Sprachen verarbeiten, aber dem ist nicht so! Tatsächlich kann man zeigen, dass eine nicht-deterministischer endlicher Automat genauso viel kann wie ein deterministischer. Dies gilt wohlgemerkt nur für endliche Automaten, nicht für Turingmaschinen.
Eine Turingmaschine erweitert prinzipiell den endlichen Automat um die Idee, Informationen auch abspeichern und wieder lesen zu können. Dadurch kann eine solche Maschine auch direkt viel mehr. So könnte sie bei den oben beschriebenen Palindromen immer abspeichern, was sie schon gelesen hat und dann vergleichen. Im Großen und Ganzen kommt die Turingmaschine unseren heutigen Computern sehr nahe, aber im Gedankenmodell wird stets von einem unendlichen großen Datenspeicher ausgegangen. So etwas kann es natürlich niemals geben! Aber für modellhafte Überlegungen reicht dies meist aus. Übrigens, wenn man eine Turingmaschine um Nicht-Determinismus erweitert, so bleibt die Menge der akzeptierbaren Sprachen gleich, aber die Laufzeit ändert sich.
© 2003-2006 by
Gereon Schüller.
Alle Rechte vorbehalten.
Design: Gereon Schüller
<email@gereon.de>