\documentclass[a4paper]{report} % PACKAGES \usepackage{ngerman} \usepackage{fullpage} \usepackage[utf8]{inputenc} \usepackage{multicol} \usepackage[sf]{titlesec} \usepackage{amsmath} \usepackage{amsfonts} \usepackage{amssymb} \usepackage[dvips,pdftex]{geometry} \usepackage{graphicx} \usepackage{pstricks} \usepackage{pst-node} \usepackage{pst-plot} \usepackage{bibgerm} \usepackage{listings} \usepackage{ulem} \usepackage{type1cm} % CONFIGURATION \pagenumbering{arabic} \pagestyle{myheadings} \setcounter{tocdepth}{2} %\topmargin25mm \headheight10mm \headsep10mm \parindent10pt \parskip1mm \setlength{\unitlength}{1cm} \author{Lukas Prokop} \title{Kerngebiet Algorithmen} \date{1. -- 11. Juni 2009} \begin{document} \selectfont \begin{titlepage} \makeatletter \null \thispagestyle{empty} \vspace*{10pt} \begin{center} \normalfont {\LARGE \@title \par} \vskip 15pt {\Large \@author \par} {\Large \@date \par} \vskip 2pt \textbf{Dank an} \\ {\small Prof. Schmidhofer \par} \vskip 20pt \small {''Beware of bugs in the above code; \\ I have only proved it correct, not tried it.'' \par} \vskip 5pt \small {''A mathematical formula should never be \textit{owned} by anybody! \\ Mathematics belong to God.'' \par} \vskip 5pt \small {''Any inaccuracies in this index may be explained by the fact, \\ that it has been sorted with the help of a computer.'' \\ (all quotes above by Donald Ervin Knuth) \par} \vskip 5pt \small {''A man provided with paper, pencil, and rubber, and subject to \\ strict discipline, is in effect a universal machine'' \\ (Alan Turing) \par} {\tiny \par} \vskip20pt \begin{figure}[!ht] \centering \fbox{ \includegraphics[scale=0.5]{travelling_salesman_problem.png} } \label{fig:titlecomic} \\ \end{figure} ''Travelling Salesman Problem'' \hskip10pt \texttt{http://xkcd.com/399/} \end{center} \end{titlepage} \tableofcontents \newcommand{\life}[2]{* #1 $\dagger$ #2} \chapter{Der Begriff Algorithmus} \begin{quote} ''Ein Algorithmus ist die schrittweise Anleitung zur L\"osung eines Problems. Idealerweise ben\"otigt der Algorithmus wenig Ressourcen und hat eine endliche Laufzeit. Ein Programm ist die Realisierung eines Algorithmus in einer Programmiersprache.'' \end{quote} Der Begriff Algorithmus stammt vom zentralasiatischen Mathematiker Muhammed al-Chwarizmi (etwa \life{783}{850}) ab. Im Mittelalter wurde sein Ausdruck ''Dixit Algorismi'' ins Lateinische \"ubersetzt: algorismus. Algorithmen sind das zentrale Element der theoretischen Informatik, die sich mit der Komplexit\"atstheorie und der Berechenbarkeitstheorie befasst. \section{Der erste Algorithmus} Charles Babbage (siehe Spezialgebiet Kryptologie) entwickelte den ''Analytical Engine'' (Rechenmaschine). Seine Mitarbeiterin Ada Lovelace ging als erste Programmierer(in) in die Geschichte ein, weil sie die erste Programmiersprache ''ADA'' formalisierte und einen Algorithmus zur Berechnung von Bernoulli-Zahlen entwickelte. Weil Babbage's Engine (wegen fehlender finanzieller Mittel) nicht fertig gestellt wurde, wurde der Algorithmus nie implementiert. Der Begriff gewinnt ab dem 20. Jahrhundert (mit dem Aufkommen von Rechenanlagen) an Bedeutung. Bedeutende Wissenschaftler waren Alan Turing, Alonzo Church, Andrei Markow und Naom Chomsky. Sie lieferten wichtige linguistische Arbeiten, die zur Weiterentwicklung von Programmiersprachen und der mathematischen Probleml\"osung f\"uhrten. Besonders Alan Turing m\"ochte ich vorherheben, der die Komplexit\"atstheorie durch seine Turingmaschine begr\"undete, zeigte dass alle Methoden (Lamda-Kalk\"ul, Turingmaschine, Registermaschinen, Markow-Algorithmen) gleich m\"achtig sind und Wikipedia\footnote{ http://de.wikipedia.org/wiki/Algorithmus\#Turingmaschinen\_und\_Algorithmusbegriff} zitiert aus seinen Arbeiten: \begin{quote} Eine Berechnungsvorschrift zur L\"osung eines Problems hei\ss{}t genau dann Algorithmus, wenn eine zu dieser Berechnungsvorschrift \"aquivalente Turingmaschine existiert, die f\"ur jede Eingabe, die eine L\"osung besitzt, stoppt. Daraus sind folgende Eigenschaften ableitbar: \begin{enumerate} \item Das Verfahren muss in einem endlichen Text eindeutig beschreibbar sein (Finitheit) \item Jeder Schritt des Verfahrens muss tats\"achlich ausf\"uhrbar sein (Ausf\"uhrbarkeit) \item Das Verfahren darf zu jedem Zeitpunkt nur endlich viel Speicherplatz ben\"otigen (Dynamische Finitheit, Platzkomplexit\"at) \item Das Verfahren darf nur endlich viele Schritte ben\"otigen (Terminierung, Zeitkomplexit\"at) \end{enumerate} Erweiterte Eigenschaften: \begin{enumerate} \item Der Algorithmus muss bei gleichen Voraussetzungen das selbe Ergebnis liefern (Determiniertheit) \item Die n\"achste anzuwendende Regel im Verfahren ist zu jedem Zeitpunkt eindeutig definiert (Determinismus) \end{enumerate} \end{quote} \section{Ein Beispiel} Ein bekanntes Beispiel bildet die sogenannte ''Identische Abbildung'' in der Mathematik. Eine Funktion gibt ihren Eingabeparameter wieder zur\"uck. Eine Funktion $f$ ist also definiert durch\ldots $$ f(x) = x $$ Wenn wir beispielweise die ganze Zahl $5$ als Argument \"ubergeben, erhalten wir $f(5) = 5$ zur\"uck. Der entsprechende Algorithmus k\"onnte dann beispielweise wie folgt aussehen: \begin{enumerate} \item Empfange den Parameter $a$ \item Initialisiere die Variable $b$ als 0 ($b=0$) \item Solange a ungleich 0 \\ inkrementiere b und dekrementiere a \item Gib $b$ zur\"uck \end{enumerate} \"Ubergeben wir der Funktion (bzw. dem Algorithmus) den Parameter 3, wird er wie folgt ausgef\"uhrt: \begin{enumerate} \item $a = 3$ \item $b = 0$ \item $a \neq 0$ (wahr) \\ $b = 0 + 1 = 1$ \\ $a = 3 - 1 = 2$ \item $a \neq 0$ (wahr) \\ $b = 1 + 1 = 2$ \\ $a = 2 - 1 = 1$ \item $a \neq 0$ (wahr) \\ $b = 2 + 1 = 3$ \\ $a = 1 - 1 = 0$ \item $a \neq 0$ (falsch) \\ return 3 \end{enumerate} \section{Ein bekannteres Beispiel} Ein bekannteres Beispiel ist die Division, wie man sie in der Grundschule lernt. \begin{verbatim} 86 : 3 = 28.666 26 20 20 20 2 Rest \end{verbatim} Der Algorithmus lautet formuliert: \begin{enumerate} \item Nehme die zwei Zahlen $a, b$ entgegen (b als Divisor) \item Wenn b gleich 0, dann Exception/Error werfen (''Divsion by zero'') \item Solange (Stellen noch \"ubrig) oder (Rest periodisches Verhalten aufweist) \\ nehme die gr\"o\ss{}te Stelle (hier: Zehnerstelle) und dividiere sie durch $b$ \\ notiere das Ergebnis nach dem Gleichzeichen \\ Schreibe den Rest der letzten Division unter diejenige Zahl \\ Wenn \"ubrige Stelle vorhanden \\ \begin{enumerate} \item dann schreibe sie hinunter, sodass sie Einerstelle des neuen Wertes wird \\ \end{enumerate} Wenn keine \"ubrige Stelle vorhanden \\ \begin{enumerate} \item dann schreibe eine Null hinunter \item wenn das Ergebnis noch kein Kommazeichen enth\"alt \begin{enumerate} \item notiere ein Kommazeichen im Ergebnis \end{enumerate} \end{enumerate} \item definiere die n\"achste Stelle als die ''gr\"o\ss{}te Stelle'' \\ \item Gib das Ergebnis zur\"uck \end{enumerate} \section{Darstellungen} Oft ist es hilfreich einen Algorithmus visuell darzustellen. Dabei definiert man bereits Elemente, die klar machen, welche Werkzeuge wir zur Formulierung von Algorithmen ben\"otigen. Man kann verschiedene Darstellungen unterscheiden. \begin{itemize} \item Flussdiagramm \item Struktogramm (Nassi-Shneiderman-Diagramm) \item Aktivit\"atsdiagramm \item Jackson-Diagramme \end{itemize} Es gibt verschiedene ISO und DIN-Spezifikationen, die diese Abl\"aufe festlegen. Die UML (Unified Modeling Language) Spezifikation ist seit den 90ern vertreten und bietet Darstellungsm\"oglichkeiten f\"ur alle Einsatzgebiete. Die UML umfasst die oben angesprochenen Darstellungen. Im folgenden m\"ochte ich zwei Diagramme besprechen. Das Struktogramm (bzw. Nassi-Shneiderman-Diagramm nach den beiden Softwareentwicklern Isaac Nassi und Ben Shneidermani benannt) teilt Algorithmen in rechteckige Bl\"ocke auf. Der ganze Algorithmus wird in ein gro\ss{}es Rechteck eingebettet. Die einzelne Schritte werden nur als kleinere Rechtecke eingetragen. F\"ur bedingte Anweisungen wird ein Rechteck definiert, das in drei Dreiecke zerlegt wird. In das mittlere Dreieck wird die Entscheidungsfrage formuliert und den beiden anderen die m\"ogliche Antwort auf die Frage. Die beiden Antwortsdreiecke schlie\ss{}en mit ihren jeweiligen weiteren Schritten an. F\"ur Schleifen wird der beeinflusste Quelltext einger\"uckt. Ein Aufruf eines Unterprogramms wird durch ein Rechteck mit doppelten R\"andern symbolisiert. \begin{figure}[!ht] \begin{center} \includegraphics[scale=0.7]{NassiShneiderman.png} \end{center} \caption{Euklidischer Algorithmus im NassiShneiderman-Diagramm \label{fig:NassiShneiderman}} \end{figure} Dank an Wikipedia f\"ur dieses Bild. Und mein pers\"onliche Liebling ist das Flussdiagramm (auch Programmablaufsplan genannt). Hierbei werden Aktionen durch geometrische Formen dargestellt und durch Pfeile verbunden. Ein ovaler K\"orper steht f\"ur Grenzpunkte (Start, Stop). Ein Pfeil oder eine Linie stellen eine Relation her (\"Ubergabe von Parametern oder Markierung als nachfolgender Schritt). Ein Rechteck steht f\"ur eine Operation (zB einer Zuweisung). Ein Rechteck mit doppelten vertikalen R\"andern f\"ur einen Aufruf eines Unterprogramms, eine Raute f\"ur eine bedingte Anweisung (Verzweigung) und ein Parallelogramm f\"ur Ein- und Ausgabe. \begin{figure}[!ht] \begin{center} \includegraphics[scale=0.7]{Flussdiagramm.png} \end{center} \caption{Beispiel f\"ur ein Flussdiagramm \label{fig:Flussdiagramm}} \end{figure} Dank an Wikipedia f\"ur dieses Bild. Was wir an dieser Stelle festhalten wollen: Die Algorithmen werden \textit{schrittweise} formuliert. Dieses Wort findet sich auch in der Definition von Algorithmen am Anfang des Dokuments wieder. Die Idee der schrittweisen Anleitung entspricht den Idealen der imperativen Programmierung, wo Befehle Schritt f\"ur Schritt abgearbeitet werden. Die imperative Programmierung ist ein sehr fr\"uhes Programmierparadigma und ist heute Element jeder Programmiersprache. Daraus folgt, dass jeder (klassische) Algorithmus in jeder Programmiersprache (bzw. Programmiersprachen jeder Generation) implementiert werden kann. Ein gr\"o\ss{}eres Problem bei der Implementierung stellen Ressourcenverbrauch und Laufzeit dar. Die Formulierung eines Algorithmus in einer Programmiersprache selbst nahezu nie. Es ist schlie\ss{}lich auch Aufgabe einer Programmiersprache die Arbeit des Programmierers zu erleichtern. \section{Das Urheberrecht} Gem\"a\ss{} dem Patentrecht lassen sich Algorithmen patentieren. Viele Probleme werfen mehr als eine L\"osung auf und Wissenschaftler stecken viel Arbeit in die Entwicklung von Algorithmen und wollen deshalb ihr Werk patentieren lassen. So ist dies zum Beispiel beim MP3-Komprimierungsverfahren der Fall, wo Elemente des Verfahrens gesch\"utzt sind. Implementierungen des MP3-Algorithmus sind also nicht gestattet und die freie Verbreitung von MP3-Programmen ist nicht m\"oglich. \chapter{Aus der Komplexit\"ats- und Berechenbarkeitstheorie} Die Komplexit\"atstheorie versucht die Komplexit\"at von Algorithmen zu analysieren bzw. Algorithmen zu klassifizieren. Die Berechenbarkeitstheorie versucht hingegen nur die Frage zu beantworten welche Probleme ''l\"osbar'' sind. \section{Klassische Probleme der Informatik} \subsection{Problem des Handlungsreisenden} Das Problem findet sich in nahezu allen Bereichen. Im Design von Mikrochips, in der Logistik und in der Entwicklung Routenplanern. Es sind mehrere Zielorte angegeben. Zum Beispiel muss der Handlungsreisende zu allen Standorten von Firmen anreisen, um sich mit ihnen zu treffen. Dazu m\"ochte er m\"oglichst wenig Zeit aufwenden. Es ist also sein Ziel die Reihenfolge der Besuche so zu w\"ahlen, dass die Gesamtreisezeit minimal gehalten wird und die R\"uckkehr an den Ausgansort m\"oglichst schnell erfolgt. Das Problem: Er darf nicht alle Wege zuvor abfahren und ihre L\"ange messen. Dieses Problem ist unl\"osbar. \subsection{Speisende Philosophen} Das Problem findet sich bei der Prozessverwaltung bzw. Verwaltung von Prozessen. Die 5 f\"unf Philosophen sitzen am Tisch und philosophieren. Wird einer der Philosophen hungrig wird, ergreift er die Gabel links und rechts und beginnt zu essen. Leider stehen nur 5 Gabeln f\"ur 5 Philosophen zur Verf\"ugung, aber solange nur einzelne Personen essen m\"ochte, stellt dies kein Problem dar. Ein Problem wird es, wenn sich alle zugleich entschlie\ss{}en zu essen. Dann greifen alle Philosophen zugleich zu der Gabel links und k\"onnen die Gabel rechts nicht beanspruchen (weil der rechte Nachbar sie in der linken Hand hat). Als Folge halten alle ihre Gabel und warten auf eine zweite. Es kommt zu einem unver\"anderlichen Zustand und die Philosophen verhungern. Das Warten auf Gabeln ist analog zum Warten auf Ressourcen von anderen Prozessen. Man spricht von einem ''dead lock'' \subsection{Rucksackproblem} Das Problem findet sich in der Logistik und allgemein in Bereichen mit beschr\"ankten Kapazit\"atsverh\"altnissen. Man haben einen Rucksack, der insgesamt 100kg tr\"agt. Wir haben jetzt die Gewichte 75kg, 65kg, 35kg, 12kg, 14kg, 4kg, 5kg, 2kg, 19kg und 20kg. Finde die Permutation, wo das Gewicht des Rucksacks m\"oglichst gro\ss{} wird, jedoch nicht die Schranke 100kg \"uberschreitet. In der Kryptologie ist dieses Problem unter dem Begriff Subset-Sum bekannt. Dieses Problem ist am besten durch Backtracking l\"osbar. \subsection{Damenproblem} Es sollen acht Damen so auf einem Schattbrett verteilt werden, dass keine Dame eine andere ''bedroht''. Gem\"a\ss{} den Schachregeln bedroht eine Dame eine Figur, wenn die Figur in einer geraden oder diagonalen Linie zur Dame steht. Das Problem wird meist durch rekursives Backtracking gel\"ost. Die Anzahl der L\"osungen w\"achst etwas schneller als exponentiell mit der Brettgr\"o\ss{}e an. Auf einem 6$\times$6-Brett gibt es interessanterweise weniger L\"osungen als auf einem 5$\times$5-Brett. \subsection{Landkartenf\"arbungsproblem} Du hast eine Landkarte vor dir und musst die L\"ander mit verschiedenen Farben eindeutig einf\"arben. Zwei benachbarte L\"ander d\"urfen also nicht die selbe Farbe tragen. Reduziere die Anzahl der verwendeten Farben auf ein Minimum. Unter den Bedingungen, dass zwei F\"lachen mit einem gemeinsamen Punkt nicht als benachbart gelten und ein Land keine Exklaven besitzt, ist die Frage mit 4 zu beantworten. Das Problem ist heute als Vier-Farben-Problem bekannt. Das Besondere ist, dass Mathematiker im 19/20. Jahrhundert verschiedene Beweise f\"ur das Problem formulierten, die sich gegenseitig wiedersprachen. Mit dem Einsatz von Computer wurde zum ersten Mal gezeigt, dass der Computer immer blo\ss{} vier Farben brauchte. Die Mathematiker erkannten diese Tatsache nicht an, da das Problem nicht von Menschenhand gel\"ost wurde. \subsection{Beziehung von Problemen und Algorithmen} Diese Probleme sind entweder selbst algorithmisch zu l\"osen, oder sie eignen sich als verallgemeinerter Problemaufriss f\"ur reale Beispiele. Probleme (dieser Art) allgemein lassen sich mathematisch formulieren und beweisen. Algorithmen sind eine L\"osungsanleitung um diese Probleme in jeder Situation effizient und effektiv zu l\"osen. \section{Turingmaschine} Die Church-Turing-These (nach Alonzo Church und Alan Turing) behauptet, dass alle mathematischen Probleme (die ein Mensch l\"osen kann) auch von einer Turingmaschine gel\"ost werden k\"onnen. Die Annahme eine Turingmaschine k\"onnte alle mathematischen Probleme l\"osen ist allerdings bewiesen falsch. Alan Turing bewies, dass das Halteproblem nicht mit der Turingmaschine entscheidbar ist. Das Halteproblem ist Algorithmus, der nicht terminiert werden kann. Entweder der Algorithmus selbst terminiert. In dem Fall springt der Algorithmus in eine while-Schleife, die nicht terminiert und keine Befehle ausf\"uhrt. Geben wir an, dass der Algorithmus nicht terminiert, so terminiert der Algorithmus sofort. Dies endet in einem Widerspruch. Alan M. Turing konnte 1936 beweisen, dass es keine Turingmaschine gibt, die das Problem f\"ur alle Eingaben l\"ost, wobei das Problem mathematisch als korrekt anzusehen ist. Es ist das erste bewiesene Entscheidungsproblem, welches nicht algorithmisch bewiesen werden kann. \lstset{language=python} \begin{lstlisting} def halting_test(program, parameter): if program_halts(programm(parameter)): return True else: return False def test(program): while program_halts(halting_test(program, program)): pass # do nothing test(test) \end{lstlisting} Bei der Turingmaschine handelt es sich um eine reduzierte Rechenmaschine, die nur 3 Operationen ausf\"uhren kann: Schreiben, Lesen und Bewegen. Mit diesen Operationen lassen sich jedoch Addition, Subtraktion und damit der Gro\ss{}teil der mathematischen Funktionen simulieren. Man k\"onnte es sich als endloses Band vorstellen, welches sich mit Einsen und Nullen beschreiben l\"asst. Ein Lesekopf f\"uhrt jetzt entsprechend einem Algorithmus die Befehle Schreiben, Lesen und Bewegen aus. Lassen sich Probleme auf einer Turingmaschine l\"osen, kann jeder Computer das selbe Problem auch l\"osen. Es dient als Gedankenexperiment \"uber die F\"ahigkeitsgrenze von logisch-algorithmischen behandelten Problemen. \section{Klassifikationskriterien f\"ur Algorithmen} Die Turingmaschine eignet sich ideal in der Berechenbarkeitstheorie, um Entscheidungen \"uber die Berechenbarkeit von Problemen zu treffen. Alternative Maschinenmodelle sind beispielweise die Registermaschine, der endliche Automat und der Kellerautomat. Die folgenden Begriffe werden sowohl von der Berechenbarkeitstheorie wie auch Komplexit\"atstheorie verwendet. Teilweise wurden sie oben angesprochen: \begin{description} \item[Finitheit] allgemein: Endlichkeit \begin{description} \item[statisch] die Beschreibung des Algorithmus ist endlich \item[dynamisch] es werden endlich viele Ressourcen gebraucht \end{description} \item[Terminiertheit] ein Algorithmus terminiert; ein Problem wird in endlicher Zeit gel\"ost. Das Halteproblem zeigt, dass es keinen Algorithmus gibt, der sagen kann, ob ein Programm f\"ur die Eingabe terminiert. Das gleichm\"a\ss{}ige Halteproblem besagt, dass ein Algorithmus selbst nicht beweisen kann, ob er \"uberall (unter beliebigen Umst\"anden) terminiert \item[Determinismus] Es treten nur definierte (reproduzierbare) Zust\"ande auf. Auf eine Anweisung im Algorithmus folgt unter den gleichen Voraussetzung immer eine genau definierte Anweisung. Ein deterministischer Algorithmus ist immer determiniert, aber es gibt nichtdeterministische Algorithmen, die trotzdem determiniert sind. \item[Determiniertheit] Ein Algorithmus ist deterministisch, wenn er unter allen Voraussetzungen das selbe Ergebnis liefert. \item[Nichtdeterminiert] Ggt. von Determinismus. Nichtdeterministische Algorithmen sind randomisiert (zB AKS-Primzahltest) \begin{description} \item[Las-Vegas] randomisierte Algorithmen, die nie ein falsches Ergebnis liefern \item[Monte-Carlo] randomisierte Algorithmen, die eventuell ein falsches Ergebnis liefern (zB Miller-Rabin-Primzahltest) \end{description} \end{description} Ein Kriterium m\"ochte ich hinzuf\"ugen, welches vorwiegend nur bei Sortieralgorithmen wichtig ist: Stabilit\"at. Als stabil wird ein Algorithmus bezeichnet, der ein Ergebnis ausgibt, das sich an der Eingabe orientiert. In einer Liste mit den Zahlen [1, 4, 1, 3] k\"onnte der erste Einser an die Position 1 und der zweite Einser (aktuell an der Position 2) an die Stelle 0 r\"ucken (instabil). Bleibt die Reihenfolge jedoch wie in der Urliste erhalten (0$\rightarrow$0, 2$\rightarrow$1), spricht man von Stabilit\"at. \section{Erfassen der Komplexit\"at von Algorithmen} Um die Schwere und den Aufwand von Algorithmen zu analysieren, m\"ussen wir die Landau-Notation kennen lernen. \begin{table}[!ht] \begin{center} \begin{tabular}{| c | l |} \hline Notation & Wirkung \\ \hline $ f \in \mathcal{O}(g) $ & f w\"achst nicht wesentlich schneller als g \\ $ f \in \hbox{o}(g) $ & f w\"achst langsamer als g \\ $ f \in \Omega(g) $ & f w\"achst mindestens so schnell wie g \\ $ f \in \omega(g) $ & f w\"achst schneller als g \\ $ f \in \Theta(g) $ & f w\"achst genauso schnell wie g \\ \hline \end{tabular} \end{center} \end{table} Diese Definition ziehen wir heran, um die Laufzeit eines Algorithmus' zu beschreiben. $x$ ist jeweils das Argument der Funktion $f$. Alle ''Bedeutungen'' sind ''ungef\"ahr''. \begin{table}[!ht] \begin{center} \begin{tabular}{| c | l |} \hline Notation & Bedeutung \\ \hline $f \in \mathcal{O}(1) $ & $f$ besitzt eine Schranke (die unabh\"angig vom Argument ist) \\ $f \in \mathcal{O}(\log{x}) $ & doppeltes Argument, $f$ w\"achst um konstanten Wert \\ $f \in \mathcal{O}(\sqrt{x}) $ & $f$ doppeltes $f$, vierfaches $x$ \\ $f \in \mathcal{O}(x) $ & lineares Wachstum, doppeltes $x$, doppeltes $f$ \\ $f \in \mathcal{O}(x\log{x}) $ & super-lineares Wachstum \\ $f \in \mathcal{O}(x^2) $ & $f$ vierfach, wenn $x$ doppelt \\ $f \in \mathcal{O}(2^x) $ & $x+1$ resultiert in $f$ doppelt \\ $f \in \mathcal{O}(x!) $ & $f$ w\"achst um das x-fache, wenn $x-1$ zu $x$ erh\"oht \\ \hline \end{tabular} \end{center} \end{table} Bez\"uglich sehr gro\ss{}er Zahlen ist diese Liste geordnet ($x!$ w\"achst bei gro\ss{}en Zahlen ganz schnell). Wichtig ist jedoch, dass diese Landau-Symbole keine Zahlen ausgeben, die sich in die (ideale) Laufzeit umrechnen lassen, sondern blo\ss{} um Richtwerte, die ein Wachstum definieren. So ist beispielweise die Basis des Logarithmus komplett egal. Die meisten Sortieralgorithmen haben einen Speicherverbrauch von $\mathcal{O}(1)$, da sie bei einer Eingabe von $n$ Elementen $n$ Pl\"atze ben\"otigen. Bei einer Eingabe von $n+1$ Elementen ben\"otigen sie $n+1$ Pl\"atze. Das Wachstum ist konstant und wird deshalb mit $1$ beschrieben. Beispiele sind beispielweise das bin\"are Suchen (logarithmisch), lineare Suchen (linear), Quicksort (leicht \"uberlineare Komplexit\"at), Sortieren durch Auswahl oder Bubblesort (quadratisch) oder Problem des Handlungsreisenden oder T\"urme von Hanoi (exponentiell) \subsection{worst and best case} Neben dem average-Case (wie Algorithmen sich im Durchschnitt verhalten), wird auch der best und worst case in Landau-Notation festgehalten. So gibt es Sortieralgorithmen, die zwar eine total ungeordnete Liste (worst case) in sehr geringer Zeit ordnen k\"onnen, doch beginnen eine geordnete Liste (best case) ebenfalls durcheinander zu w\"urfeln. Der average-case reicht nicht aus, um die Komplexit\"at eines Algorithmus' zu erfassen. Einige Algorithmen haben jedoch bei best, worst und average case das selbe Verhalten (bzw. Komplexit\"at) \subsection{Komplexit\"atsklasse} Eine Komplexit\"atsklasse umfasst Probleme, die alle die selbe Komplexit\"at aufweisen. Am bekanntesten ist die Klasse NP (nichtdeterministisch polynomielle Zeit). Nichtdeterminismus bezeichnet (wie oben erw\"ahnt) Algorithmen, dessen n\"achster Schritt nicht eindeutig festgelegt ist. Polynomiell bezieht sich auf die Eingabemenge und bezeichnet Algorithmen, die mit steigendem Eingabeparameter eine steigende Laufzeit besitzen, die unterhalb der von Polynomen liegt. Ein Problem ist genau dann NP-vollst\"andig, wenn dessen Eigenschaften innerhalb der NP-Komplexit\"atsklasse liegen. Das Rucksackproblem und das Problem des Handlungsreisenden sind NP-vollst\"andig. Eine andere Komplexit\"atsklasse ist P (aka PTIME). Sie umfasst Probleme, die polynomielle Eigenschaften aufweisen, aber deterministisch sind. \section{L\"osungsans\"atze} \subsection{Heuristik} Unter Heuristik versteht man Algorithmen, die mit geringem Rechenaufwand und kurzer Laufzeit zul\"assige L\"osungen f\"ur ein bestimmtes Problem liefern. Bei Algorithmen besitzt man den Anspruch auf optimale L\"osungen in optimaler Laufzeit. Heuristische Algorithmen verzichten auf eine der Kriterien, um andere Eigenschaften zu gew\"ahrleisten. \textbf{Anwendung:} Man entwickelt einen Algorithmus, um ein Problem zu l\"osen. \begin{itemize} \item Der Algorithmus hat eine sehr gro\ss{}e Laufzeit \item Der Algorithmus liefert mehrere L\"osungen \item Der Algorithmus liefert zuverl\"assig eine L\"osung \end{itemize} Man schreibt jetzt den Algorithmus heuristisch, dann besitzt er beispielweise die folgenden Eigenschaften: \begin{itemize} \item Der Algorithmus hat eine vergleichsweise geringe Laufzeit \item Der Algorithmus liefert nur eine L\"osung \item Der Algorithmus liefert eine zuverl\"assige L\"osung \end{itemize} Als triviales Beispiel kann das Erf\"ullen einer mathematischen Gleichung herangezogen werden. Man verzichtet darauf alle Ergebnisse zu errechnen und erreicht daf\"ur eine geringere Laufzeit. \subsection{Backtracking} Backtracking wurde bereits oben erw\"ahnt. Einige der oben angesprochene Probleme sind durch Backtracking l\"osbar. Backtracking bezeichnet dabei den L\"osungsansatz alle L\"osungswege durchzuwandern und am Ende den besten Weg herauszusuchen (Minimum bzw. Maximum). zB Einen Algorithmus f\"ur das Damenproblem beginnt man damit eine Dame am Anfang an einen beliebigen Ort zu setzen. Danach setzt man die zweite Dame in der zweiten Reihe. Tritt ein Fehler (Dame bedroht Dame) auf, setzt man die zweite Dame zur\"uck (backtrackt sie). Schrittweise versucht man so zu einer L\"osung zu kommen. Bei einem Fehler geht man einen Schritt zur\"uck. Kommt man zu einer validen L\"osung, dokumentiert man das Ergebnis (beim Damenproblem kann man sogar Schachnotation verwenden). Am Ende vergleicht man die Ergebnisse und retourniert die optimale L\"osung. Das Problem des Handlungsreisenden w\"are auch mit Backtracking l\"osbar, jedoch ist es laut Problemstellung nicht erlaubt jeden Weg abzufahren. Durch Backtracking steigt die Laufzeit erfahrungsgem\"a\ss{} enorm. \subsection{Teile und herrsche} Das Prinzip ''divide and conquer'' schreibt eine L\"osung vor, wo das Problem in kleinere Teilprobleme aufgeteilt wird. Beispielweise arbeitet der Sortieralgorithmus Mergesort so, dass das Problem so weit geteilt wird, bis nur mehr Buchstabenpaare \"ubrig bleiben. Diese Buchstabenpaare werden alphabetisch sortiert und dann mit den anderen Paaren zusammengef\"uhrt. \chapter{Bekannte Algorithmen} \section{Ein Algorithmus im Detail: Mergesort} Mergesort ist ein Sortieralgorithmus nach dem Prinzip Teile und herrsche. Er teilt die -- zu verarbeitende Liste -- in mehrere Teile und sortiert die einzelnen Buchstaben, die in Teilen gespeichert sind. \lstset{language=python} \begin{lstlisting} def mergesort_rec(liste): if len(liste) <= 1: return liste else: mid = (len(liste) / 2) left, right = liste[0:mid], liste[mid:] return merge_it(mergesort_rec(left), mergesort_rec(right)) def merge_it(left, right): nlist = [] while len(left) > 0 and len(right) > 0: if left[0] <= right[0]: nlist.append(left[0]) del left[0] else: nlist.append(right[0]) del right[0] while len(left) > 0: nlist.append(left[0]) del left[0] while len(right) > 0: nlist.append(right[0]) del right[0] return nlist \end{lstlisting} Mergesort ist ein ideales Beispiel, welches zeigt, dass Rekursion oftmals besser zum Programmieren geeignet ist, da der Algorithmus dadurch \"ubersichtlicher und k\"urzer ist. Der Algorithmus ist stabil und besitzt in jedem (worst, best, average case) Fall eine Komplexit\"at von $\mathcal{O}( n \cdot \log(n) )$. Durch sein Divide-and-conquer-Verhalten steigt der Wachstum des Speicherbedarfs bei einer wachsenden Eingabe von Elementen. Die Raumkomplexit\"at wird mit $\mathcal{O}(n)$ beschrieben. \section{Euklidischer Algorithmus} \lstset{tabsize=8, language=C} \begin{lstlisting} #include #include int main(int argc, char* argv[]) { int a, b, base = 10; char *endptr; int unsigned tmp; a = strtol(argv[1], &endptr, base); b = strtol(argv[2], &endptr, base); // euklidean algorithm while (b != 0) { tmp = a % b; a = b; b = tmp; } printf("greatest common divisor: %d \n", a); return 0; } \end{lstlisting} Der euklidische Algorithmus errechnet den gr\"o\ss{}ten gemeinsamen Teiler zweier ganzer Zahlen. Man kann vier Varianten unterscheiden: \begin{itemize} \item klassisch, iterativ \item klassisch, rekursiv \item modern, iterativ \item modern, rekursiv \end{itemize} Der oben (in C) notierte Algorithmus ist modern und iterativ. Der klassische Algorithmus basiert auf der Idee, dass durch st\"andiges Subtrahieren des kleineren Wertes vom Gr\"oseren am Ende die beiden Werte zusammenfallen, einer der Wert null wird und der andere Wert (wird zur\"uckgegeben und) ist der der ggT (engl. gcD). Der moderne Algorithmus verwendet hier einfach den Rest der Division. Bei Subtraktion handelt es sich um das Gegenteil der Addition. Bei einem Teiler handelt es sich um das Gegenteil eines Vielfachen. Addiert man einen Wert definiert oft, entsteht ein Vielfaches des Wertes. Diesen Weg zur\"uckgedacht, ergibt den euklidischen Algorithmus Eine Verbesserung des Euklidischen Algorithmus ist der Steinsche Algorithmus. Also muss er richtig implementiert werden, damit er schneller als der moderne iterative Euklid ist (wie ich unweigerlich erfahren musste). \section{Bin\"ares Suchen} Interessant ist eine Erfahrung, die wohl die meisten Menschen unbewusst im Leben gemacht haben: Suchen. Suchen wir ein Wort in einem W\"orterbuch, so werden wir nicht damit beginnen jedes Wort von Anfang an durchzugehen, sondern werden das Buch in der Mitte aufschlagen. An der Buchstabenangabe sehen wir, ob sich das Wort in der linken oder rechten H\"alfte befindet. Hat man die entsprechende H\"alfte gefunden, wird diese wieder in die H\"alfte geteilt\ldots und so weiter bis nur mehr ein Element \"ubrig bleibt, welches mit dem Suchelement \"uberein stimmt. Die Idee jedes Wort der Reihe durchzugehen, bezeichnet man als lineares Suchen. Die Idee des Halbierens bezeichnet man als bin\"ares Suchen. Bin\"ares Suchen setzt eine geordnete Liste von Elementen voraus. Lineares Suchen nicht. Den best case f\"ur lineares Suchen bildet der Fall, dass sich das gesuchte Element am Anfang befindet. Den best case f\"ur bin\"ares Suchen bildet der Fall, dass sich das gesuchte Element in der H\"alfte befindet (das Element eines daneben bildet den worst case). \section{Weitere Algorithmen} Es gibt eine Vielzahl von Algorithmen. Im Folgenden folgt nur ein Auszug von Algorithmen, die mir schon vor der Besch\"aftigung mit dem Thema bekannt war. Ich gehe also davon aus, dass jene Algorithmen den meisten Informatikern bzw. Mathematikern bekannt sind. $\frac{1}{3}$ der Rechenzeit eines modernen Heimrechners beanspruchen Sortierungen. Deshalb ist dieses Feld besonders beliebt als Einstieg zu Erkl\"arungen. Man kann sich selbst einmal damit befassen, wie Algorithmen zu verfassen sind. Man hat eine ungeordnete Liste von Algorithmen vor sich. Jetzt m\"ochte man diese Liste ordnen. Das menschliche Auge versucht hier einfach die gr\"o\ss{}te Karte zu erkennen. Diese Karte wird entnommen und als letztes Element der neuen Liste (out-of-place) definiert. Aber dabei handelt es sich gar nicht um ein optimales Verfahren. Der Zeiger muss jedes Mal die gesamte Liste durchgehen und kann dann erst entscheiden, welches das $x$-gr\"o\ss{}te Element ist. Dieser Algorithmus ist verkehrt (das kleinste Element wird ausgesucht) als Insertion-Sort bekannt. Sortieralgorithmen (Sortieren der Elemente einer Liste) (znlE = zwei nebeneinander liegende Elemente): \begin{description} \item[Gnomesort] ordne znlE. wenn ge\"andert, Schritt zur\"uck, sonst vor \item[Mergesort] divide and conquer, teile alles in Buchstabenpaare auf und sortiere sie einzeln. F\"uhre alles wieder zusammen \item[Quicksort] \"ahnlich MergeSort \item[Selectionsort, Heapsort] w\"ahle das kleinste Element und stelle es an Position 0 \item[Shellsort, Insertsort] vergleiche znlE und verschiebe evtl. Element ganz nach vorne \item[Bubblesort] vergleiche znlE und tausche sie, falls verkehrt. Wenn in einem Durchlauf etwas ver\"andert wurde, dann fange wieder von vorne an, sonst bereits sortiert \item[Simplesort] vergleiche znlE und sortiere bis alle korrekt liegen \item[Slowsort] sortiere alles au\ss{}er dem gr\"o\ss{}ten Element \end{description} Algorithmen aus der Informatik und Mathematik: \begin{itemize} \item String-Matching-Algorithmen (suchen Stichw\"orter in einer Sammlung von Texten) \item Gaussches Eliminationsverfahren (L\"osen von Gleichung mit mehreren Bedingungen) \item Sieb des Eratosthenes (Erzeugung von Primzahlen) \item Sieb des Atkin (Optimierung des Sieb des Eratosthenes) \item Miller-Rabin-Test (Primzahltest) \item Erweiterter euklidischer Algorithmus ($ggT(a,b) = s{\cdot}a + t{\cdot}b$) \end{itemize} \chapter{Implementierung von Algorithmen} \section{Der Begriff Syntax} Jede Sprache besteht im Grunde aus zwei Elementen: dem Vokabular und der Grammatik. Eine Programmiersprache ebenfalls. Ein Vokabular einer Programmiersprache bezeichne ich in den folgenden Sektionen als ''Schl\"usselwort'' (engl. keyword). Und die Grammatik einer Programmiersprache wird als Syntax bezeichnet. Es gibt Linguisten, die Programmiersprachen genau untersucht haben und teilweise den Begriff Syntax abgrenzt, aber f\"ur Nichtprogrammierer ist die Erkl\"arung hinreichend eindeutig. Programmierer wissen sowieso, was man unter Syntax versteht. \section{Hello World} ''Hello World'' ist eine ber\"uhmte Phrase, die Programmiereinsteigern ans Herz gelegt wird. Hello World setzt voraus, dass man den Interpreter oder Compiler starten kann, was die Basis jedes Programmierens ist. Danach muss man noch die Struktur eines allgemeinen Programms beherrschen (zB Einbinden der notwendigen Bibliotheken zur stdout-Ausgabe) und es folgt ein Programm, welches den schlichten Text ''Hello World'' ausgibt. Es ist das erste Programm, welches man beim Erlernen einer neuen Sprache schreiben sollte. Da es bei jeder Programmiersprache um das Ausgeben von Daten geht, l\"asst sich Hello World in jeder gew\"ohnlichen (nicht unbedingt turing-vollst\"andigen) Programmiersprache implementieren. \section{Werkzeuge aus der Programmierung} Wikipedia gibt nette Beispiele. Diese folgenden Beispiele sollen nur zeigen, welche Operationen abarbeiten k\"onnen m\"ussen. \begin{description} \item[einfache Operation] ''$2 {\cdot} 2$'' \item[sequentielle Notation] ''Bier auf Wein, lass es sein'' (Reihenfolge wichtig!) \item[nebenl\"aufig] ''C++ und python'' (Reihenfolge egal; evtl. gleichzeitig) \item[parallel] ''mit Gabel und Messer essen'' (kann nur gleichzeitig erfolgen) \item[nichtdeterministisch, nichtdeterminiert] ''Vanille- oder Schokoeis'' (Ergebnis von Wahl abh\"angig) \end{description} Weitere Anweisungen, die Computer k\"onnen m\"ussen haben wir bei den visuellen Darstellungen von Algorithmen gesehen. Als Basis geh\"ort dazu: \begin{itemize} \item Bedingte Anweisungen (wenn \textit{das}, dann \textit{das} sonst \textit{das}) \item For-Schleife (Wiederholen einer Befehlsfolge mithilfe einer Laufvariable) \item While-Schleife (Wiederholen einer Befehlsfolge mit unbekannte Laufzeit) \end{itemize} \subsection{Bedingte Anweisungen} Mithilfe der Logik wird ein Entscheidung getroffen, welche einen Wahrheitswerte oder sein Gegenteil liefert. Trifft die Entscheidung zu, so wird der nachfolgend definierte Codeblock ausgef\"uhrt (if). Es existieren auch immer Deklarationen f\"ur Bl\"ocke die ausgef\"uhrt werden, wenn der Wahrheitswert nicht gegeben ist (else). Bei Programmiersprachen findet man die bedingte Anweisung typischerweise unter dem Schl\"usselwort \textit{if}. Eines meines der ersten Probleme beim Programmieren war es nicht zu verstehen, was sich \"andern sollte. 3 ist immer kleiner als 5 ($3 < 5 \rightarrow$ true) und mein Vorname wird immer Lukas sein. Ich habe 3 Elemente definiert, die sich \"andern k\"onnen und auf das die meisten Programme reagieren m\"ussen: \begin{description} \item[Umwelt, System] der Computer (installierte Software, Betriebsystem, \ldots) und die Peripherie des Computers (W\"arme der CPU, Festplatte\ldots) \item[Umgebungsvariablen] Zeit, Daten aus einer Datenbank \item[Benutzereingabe] Passwort, Username, Auswahl von Elementen, Maus, Tastatur \end{description} \subsection{Schleifen} \label{sec:loops} Codebl\"ocken m\"ussen manchmal mehrfach ausgef\"uhrt werden. Daf\"ur verwendet man in der Programmierung Schleifen. Man unterscheidet zwei Arten: \begin{description} \item[for] Es wird eine genau definierte Anzahl an Wiederholung vollf\"uhrt. Zugleich l\"auft meist eine Laufvariable mit, die die aktuelle Zahl der Wiederholung zur\"uckgibt (1, 2, 3, 4, 5\ldots). Die Laufvariable wirst standardm\"a\ss{}ig inkrementiert, k\"onnte jedoch auch dekrementiert werden. \item[while] Ein Codeblock wird ausgef\"uhrt, wobei noch niemand wei\ss{} wie oft dies erfolgen wird. Meist wird in dem Codeblock selbst entschieden, ob der Code nun aus der Schleife springen soll, oder nicht. Es gibt auch Schleifen, die niemals terminieren. Sogenannte Endlosschleifen finden bei Servern und der Computer warten mittels eine Endlosschleife st\"andig auf neue Eingaben von Maus und Tastaur. \end{description} Ebenfalls ist es wichtig auf Datentypen reagieren zu k\"onnen. Jede Programmiersprache besitzt ein Containerelement, wo mehrere Elemente in einer Variable zusammengefasst werden. Es ist jetzt notwendig jedes Element dieses Container durchschreiten zu k\"onnen. Hierf\"ur wird oft das Schl\"usselwort \textit{for} selbst angewandt (die weitere Syntax unterscheidet dann eine Schleife mit Z\"ahlvariable von einem Containerdurchlauf) oder \textit{foreach}, wobei die Programmiersprachen nat\"urlich die Schl\"usselw\"orter selbst definieren d\"urfen (siehe Programmiersprachen wie Brainf*uck, Whitespace oder beatnik). \subsection{Logik} Die Logik befasst sich mit Wahrheitswerten und den darauf zugrunde liegenden Operationen. Als erstes m\"ochte ich die Vergleichsoperationen illustrieren (LE = Linkes Element): \begin{table}[!ht] \begin{center} \begin{tabular}{l | l | c} \hline $<$ & kleiner & LE kleiner als Rechtes? \\ $\leq$ & kleiner gleich & LE kleiner oder gleich Rechtes? \\ $==$ & Vergleich & LE gleicher Wert wie rechts? \\ $\geq$ & gr\"o\ss{}er gleich & LE gr\"o\ss{}er oder gleich Rechtes? \\ $>$ & gr\"o\ss{}er & LE gr\"o\ss{}er als Rechtes? \\ \hline \end{tabular} \end{center} \end{table} All diese Operationen geben einen boolschen Werte (wahr oder falsch) zur\"uck. Aufgrund dieser Entscheidung kann dann der auszuf\"uhrende Codeblock mithilfe einer bedingte Anweisung durchgef\"uhrt werden. Wichtig ist die Unterscheidung von = (Zuweisung) und == (Gr\"o\ss{}envergleich). \textit{Gr\"o\ss{}envergleich} ist f\"ur Nichtprogrammierer unter Identit\"at besser verst\"andlich, jedoch kann sich Gewichtsvergleich und Identit\"at unterscheiden (zB in python, wo Elemente ident sind, wenn sie am selben Ort gespeichert werden, aber gleich, wenn sie die selben Gr\"o\ss{}e besitzen. Der andere Bereich ist die boolsche Algebra. Beispielweise ist die Anweisung ''Nehme einen Apfel und eine Banane'' nur dann erf\"ullt (wahr), wenn sowohl Apfel als auch Banane genommen wurde. F\"ur ODER gilt beispielweise\ldots \begin{table}[!ht] \begin{center} \begin{tabular}{l | l | l} \hline Ereignis 1 & Ereignis 2 & Ereignis 1 ODER Ereignis 2 \\ \hline nicht e. & nicht e. & falsch \\ nicht e. & erf\"ullt & wahr \\ erf\"ullt & nicht e. & wahr \\ erf\"ullt & erf\"ullt & wahr \\ \hline \end{tabular} \end{center} \end{table} In der rechten Spalte k\"onnen wir die Werte wahr, wahr, wahr und falsch lesen. Mit dem Alphabet 0 (n. e.) und 1 (erf\"ullt) bedeutet das 1110. Und mit diesem System sind die Ergebnisse der folgenden Tabelle in der linken Spalte notiert: \begin{table}[!ht] \begin{center} \begin{tabular}{l c} \hline Antworten & Bezeichnung \\ \hline 0000 & falsch \\ 1000 & NOR \\ 0100 & Inhibition aus $E_2$ \\ 0010 & Inhibition aus $E_1$ \\ 0001 & AND \\ 1100 & Negation aus $E_1$ \\ 0110 & XOR, Kontravalenz, Antivalenz \\ 0101 & $E_2$ \\ 1010 & Negation aus $E_2$ \\ 0011 & $E_1$ \\ 1110 & NAND \\ 0111 & ODER \\ 1111 & wahr \\ \hline \end{tabular} \end{center} \end{table} \subsection{Prozeduren und Funktionen} Befehle wiederholen sich unweigerlich, wenn die Probleme etwas komplexer werden. Zum Beispiel nehmen ein Drittel der Rechenzeit eines Computers Sortieralgorithmen in Anspruch. Programmierer w\"urden viel Zeit vergeuden, wenn sie diese Algorithmen bzw. ganz allgemein Codebl\"ocke mehrfach notieren m\"ussten. Man teilt deshalb Codebl\"ocke in Einheiten auf. Diese Einheiten spricht man mit einem Namen an. Da ein Codeblock oft andere Vorgaben verwendet (zB die zu sortierende Liste), k\"onnen Parameter verwendet werden. Funktionen sind Codebl\"ocke, die mit einem Namen angesprochen werden und der Parameter \"ubergeben werden. Als Resultat der Berechnungen wird ein R\"uckgabeparameter wieder retourniert. Der Unterschied zwischen Funktionen und Prozeduren: Funktionen geben diesen Parameter zur\"uck; Prozeduren nicht. Wozu braucht man einen Codeblock, der kein Ergebnis besitzt und somit nichts errechnet? Falsch, es gibt schon ein Ergebnis, nur muss dar\"uber kein Resultat bekannt sein. zB k\"onnte ich in einer Prozedur notieren, dass die graphische Oberfl\"ache immer die Farbe Orange verwenden soll. Die GUI (''Graphical User Interface'') sagt jetzt nicht, ob diese Operation erfolgreich war. Also kann auch die Prozedur keine n\"aheren Angaben dar\"uber retournieren und gibt keinen Wert zur\"uck. Ein anderes Beispiel: Das gesamte Programm ver\"andert die ganze Zeit nur eine Variable. Diese wird als ''global'' notiert, damit alle Funktionen und Prozeduren (und weitere Komponenten) darauf zur\"uckgreifen k\"onnen. Die Prozedur f\"uhrt jetzt einen Algorithmus aus (zb $2{\cdot}x$). Da diese Variable sowieso global behandelt wird, wird die Ver\"anderung auch global wirksam und die Variable ist ge\"andert worden. Die Prozedur braucht jetzt keine Variable ver\"andern. Delphi ist die bekannteste Sprache, die diese strikte Unterscheidung f\"uhrt. Andere Programmiersprachen machen keinen Unterschied. Entweder wird ein ''return'' (retournieren des R\"uckgabeparameters) ausgef\"uhrt (dann ist es eine Funktion) oder eben nicht (Prozedur). \lstset{language=python} \begin{lstlisting} # function a = 5 def function(x): return x * 2 a = function(a) print a # procedure b = 5 def procedure(): global b b = b * 2 procedure() print b # this program outputs # 10 # 10 \end{lstlisting} Die Definition von Funktion stimmt mit der von der Mathematik \"uberein. \subsection{GOTO} Wir m\"ochten also Codebl\"ocke definieren, auf die wir jederzeit wieder zugreifen m\"ochten. In modernen Sprachen werden diese Bl\"ocke mit Namen angesprochen und Sonderzeichen zeigen welchen Teil der Codeblock umfasst. Das folgende Programm (Implementierung eines Algorithmus' in einer Programmiersprache) zeigt dies anhand eines Beispiels: \lstset{language=php} \begin{lstlisting} \end{lstlisting} (PHP verwendet immer das Schl\"usselwort \textit{function} wobei es sich hier um eine Prozedur handelt) Das Programm gibt viermal ''Hello World!'' aus. In dieser Programmiersprache (PHP) wird wie in C die geschwungene Klammer genutzt \{\}. Aber die Frage lautet: Wie wird dies im Computer selbst gehandhabt? Der Interpreter/Compiler \"ubersetzt es ja in Maschinensprache. Wie schaut es dort aus? Die Antwort findet sich in antiken Programmiersprachen und lautet in etwa JMP oder GOTO. Diese beiden Begriffe sind Schl\"usselelemente mit denen innerhalb des Programms gesprungen werden kann. Das folgende Programm hat den selben Zweck wie das Programm oben. Ich habe nicht die ''richtige'' PHP Kontrollstruktur ''goto'' verwendet, sondern so angepasst, dass sie besser verst\"andlich ist. Das folgende Programm ist also kein funktionierendre Quelltext (siehe Sektion \pageref{sec:pseudocode}). \lstset{numbers=left} \begin{lstlisting} i = 0 print 'Hello World!' if (i < 4) { i = i + 1; goto line 2; } \end{lstlisting} PASCAL ist bekannt f\"ur sein GOTO. GOTO kann entweder eine Zeilennummer ansprechen (siehe Beispiel oben) oder ein Label (wie in PHP eigentlich vorgesehen). Das GOTO-Statement ist umstritten, weil es den Quelltext un\"ubersichtlich machen kann. Linus Torvalds und Linux-Entwickler sprechen sich aber f\"ur die Verwendung aus. Dementsprechend finden sich im Linux-Kernel eine Menge dieser Befehle. \section{in-place} Im Zuge der Sortieralgorithmen und in Zusammenhang mit Prozeduren (vs. Funktionen) m\"ochte ich in-place ansprechen. Bei in-place-Funktionen handelt es sich um Funktionen, die den \"ubergebenen Wert wirklich ver\"andern und nicht blo\ss{} Werte (bei Sortieralgorithmen: eine geordnete Liste) zur\"uckgeben. Das folgende Beispiel sollte es demonstrieren: \lstset{language=python} \begin{lstlisting} liste = [1, 2, 4, 3] # out-of-place liste = sorted(liste) # in-place sort(liste) # anyway, it's [1, 2, 3, 4] print liste \end{lstlisting} Bei out-of-place wird das Ergebnis empfangen und in die Variable a geschrieben. Bei in-place wird die Eingabe direkt ver\"andert. Damit entspricht die Funktion \textit{sort} einer Prozedur und \textit{sorted} einer Funktion. python organisiert sich allgemein so, dass Funktionen mit der Endung \textit{-ed} out-of-place arbeiten und die ohne Endung in-place. \section{Pseudocode} \label{sec:pseudocode} Bei Pseudocode handelt es sich um eine programmiersprachenunabh\"angige Notation. F\"ur Kommandos werden keine spezifischen Namen von Programmiersprachen verwendet, sondern der naheliegendste Begriff, der die Aktion beschreibt. F\"ur Zuweisungen wird das allgemein \"ubliche Gleichzeichen $=$ oder ein Pfeil $\rightarrow$ verwendet. Die Pseudocodes k\"onnen so auch gelesen werden ohne, dass man die genaue Schl\"usselw\"orter oder syntaktischen Elemente einer speziellen Sprache verstehen muss. Daher ist Pseudocode f\"ur Seiten wie Wikipedia geeignet, wo versucht wird, Algorithmen allgemein zu erkl\"aren ohne auf Programmiersprachen einzugehen. \section{Iteration} Unter Iteration versteht man das Durchwandern eines Containerelements, welches ich bereits in der Sektion \pageref{sec:loops} angesprochen habe. Wie Iteration in einer Programmiersprache notiert wird, ist spezifisch. Jedoch steht es in jeder Sprache zur Verf\"ugung. Oftmals sind die Elemente eines Containers mit Indizes ansprechbar. Dabei kann man die Indizes durch eine Laufvariable bei for-Schleifen erzeugen. \section{Rekursion} Bei Rekursion handelt es sich um Codebl\"ocke, die sich selbst aufrufen. Das Adjektiv hei\ss{}t rekursiv und ist das Gegenteil von iterativ. Meine pers\"onliche Lieblingsdefinition ist die aus einem W\"orterbuch: \begin{quote} Re-kur-sion (-en/-en) siehe \textit{Rekursion} \end{quote} Man beginnt also Rekursion nachzuschlagen und in weiterer Folge nochmals. Und nochmals und nochmals bis man in einer Endlosschleife endet. Eine Rekursion ist eine Funktion, die sich selbst aufruft. Oben haben wir ein Beispiel wo wir eine Endlosschleife erhalten, jedoch haben wir genauso begrenzte Schleifen, wie zB bei der rekursiven Implementierung des euklidischen Algorithmus'. \lstset{language=python} \begin{lstlisting} def euklid(a, b): if b == 0: return a else: return euklid(b, a % b) \end{lstlisting} Ein weiterer und wesentlich komplexerer Algorithmus ist PageRank. PageRank beurteilt Webseiten auf Basis der Links und ist das urspr\"ungliche Konzept der Suchmaschine Google. \subsection{rekursiv vs. iterativ} Jedes Problem, welches rekursiv gel\"ost werden kann, kann auch iterativ gel\"ost werden. Nicht jedoch umgekehrt. Typischerweise findet man in der iterativen Implementierung eines urspr\"unglich rekursiven Algorithmus' eine while-Schleife. \section{Programmiersprachen} Was ist jetzt eine Programmiersprache? Eine Programmiersprache ist im Grunde eine Notation, die in die (Maschine)sprache des Computers \"ubersetzt werden und damit Berechnungen durchgef\"uhrt werden k\"onnen. Jeder Mensch kann es sich vorstellen, dass es komplizierter ist Einsen und Nullen zu schreiben als mit Schl\"usselw\"orter umzugehen. Einsen und Nullen sind wesentlich fehleranf\"alliger (eine Null zu viel kann den Computer schon abst\"urzen lassen) und enth\"alt oft Wiederholungen (DRY -- ''Don't repeat yourself''). Solche Probleme versuchen Programmiersprachen zu beheben. Ich nenne wie folgt ein paar: \begin{itemize} \item C, Objective-C, C++ \item C\#, Java \item python, ruby \item bash, zsh \item PHP, Perl \item Fortran \item BASIC \item PASCAL \item LISP \item Haskell \end{itemize} Alle Programmiersprachen lassen sich jetzt nach Kriterien erfassen (zB Turing-Vollst\"andigkeit), nach Paradigmen gliedern (Programmierparadigmen) und Phasen der Entwicklung zuordnen (Generationen). \subsection{Turing-Vollst\"andigkeit} Jeder kann seine eigene Programmiersprache entwickeln. In etwa die H\"alfte (nach eigener Sch\"atzung) der Programmiersprachen ist aus Anlass f\"ur Firmenzwecke entwickelt worden. Die Firma erschlie\ss{}t einen neuen Arbeitsbereich und ben\"otigt hierf\"ur eine Sprache, in der sich die behandelten Probleme besser formulieren lassen. Entwickelt wurden die meisten Programmiersprachen von Programmierern aber aufgrund des philologischen Hintergrunds finden sich genauso Linguisten als Entwickler. Ok\ldots du entwickelst deine eigene Programmiersprache. Sagen wir du m\"ochtest bedingte Anweisungen notieren k\"onnen, aber Schleifen brauchst du nicht f\"ur deinen Anwendungsbereich. Mit dem Fehlen von Schleifen kann man einige Probleme nicht mehr l\"osen. Damit gilt nicht mehr der Standard, dass mathematische und andere Probleme (wie Turing an der Turingmaschine illustrierte) l\"osbar sind. Turing hat hierf\"ur den Begriff der Turing-Vollst\"andigkeit eingef\"uhrt: Ist ein Problem (genauer: welches auf einer Turingmaschine l\"osbar w\"are) nicht in einer Programmiersprache formalisierbar, so ist die Sprache nicht turing-vollst\"andig. Ist ein Problem nicht auf einem Computer bearbeitbar, so ist der Computer nicht turing-vollst\"andig. (Um das Kriterium der Turing-Vollst\"andigkeit zu erf\"ullen, ist es nicht notwendig einen unendlichen Speicher zur Verf\"ugung zu stellen, wie es bei der Turingmaschine -- mit dem unendlichen Magnetband -- definiert wurde) \section{Programmierparadigmen, Generationen} Es gibt verschiedene L\"osungsans\"atze an Probleme. Dies haben wir oben bei den besprochenen Problemen gesehen. Genauso geht es bei Programmiersprachen nicht nur darum die Probleme zu l\"osen, sondern auch darum, dass ein Programmierer sie effizient l\"osen kann. Ich erkl\"are hier einige Programmierparadigmen und schauen uns nachher an, wie man sie in Generationen einteilen kann. \begin{description} \item[imperativ] Die Befehle werden schrittweise abgearbeitet, wobei besonderer Wert auf die klare Definition der einzelnen Schritte gelegt wird (zB C, Pascal, Fortran). Typisch f\"ur solche Sprachen sind h\"aufige Anwendung von bedingten Anweisungen und globalen Variablen \item[logisch] Das Paradigma basiert auf der Idee der mathematischen Logik. Klassisches Beispiel ist die Verwandtschaft. Der Vater von Daniel ist Matthias. Wer ist Matthias Sohn? (zB Prolog) \item[iterativ] rekursive Ausdr\"ucke sind nicht erlaubt, um die Effizienz zu erh\"ohen (zB urspr\"ungliches PASCAL) \item[prozedural] Im Zentrum stehen Prozeduren. Ein Programm wird in kleine Prozeduren aufgeteilt, die globale Variablen verarbeiten bzw. anderen Komponenten (GUI, anderen Programmbibliotheken) (zB Fortran, ALGOL, COBOL) \item[funktional] Im Zentrum stehen Funktionen. Diese werden am Programmanfang notiert und eine Hauptfunktion ruft dann einzelne Funktionen auf, die zur Programmabarbeitung notwendig sind. Dadurch wird beispielweise der Programmablauf stark verschleiert. Typisch sind auch stark reduzierte Ausdr\"ucke, die eine leichte Verarbeitung von Containerelementen erlaubt (zB Haskell) \item[modular] Die Komplexit\"at von Programmen wird minimiert indem man Programme in Module unterteilt, die verschiedene Teilprobleme l\"osen \item[deklarativ] Es wird nicht der Algorithmus spezifiziert, sondern das Resultat. Es wird also keine Anweisung gegeben, wie eine Liste geordnet werden soll, sondern wie das Ergebnis aussieht (das jetzt darauffolgende Element muss gr\"o\ss{}er als das vorhergehende sein) (zB Haskell, SQL, XSLT) \item[strukturiert] basierend auf prozedural, jedoch unterscheidet man nur Sequenzen (Codebl\"ocke), Auswahlen (bedingte Anweisungen) und Wiederholungen (Schleifen) \item[objektorientiert] Daten werden als Einheiten (Objekte) aufgefasst, die eine Identit\"at (Klassennahmen), Verhalten (Methoden, functions) und Eigenschaften (properties). Die Objekte werden als Klassen definiert und Instanzen sind laufende Kopien von Klasse mit spezifischen Eigenschaften. Erm\"oglicht wird dadurch Vererbung (Kopieren von Methoden einer h\"oheren Klasse), Polymorphismus (Abhebung von Datentypen-Basis) und Kaspelung (Daten liegen im privaten oder \"offentlichen Bereich vor) \item[nebenl\"aufig, parallel] Progammkomponenten werden so weit es geht in Teilprobleme untergegliedert, damit sie parallel abgearbeitet werden k\"onnen und die Laufzeit minimiert wird. \item[hybrid] Vereint mehrere der verschiedenen Programmierparadigmen \end{description} Um einen \"Uberblick zu geben, verzichte ich auf die genaue Definition und richtige zeitliche Zuordnung der Programmierparadigmen,aber m\"ochte dadurch eine klareren \"Uberblick geben (heuristisch vollf\"uhrt sozusagen): \begin{quote} Programme wurden urspr\"unglich schrittweise angegeben. Beispielweise soll zu einer Zahl der Wert Eins addiert werden und dann durch 2 dividiert werden (imperativ). Man f\"uhrt jedoch bedingte Anweisungen ein, um auf Ereignisse reagieren zu k\"onnen und f\"uhrt Datentypen ein, damit man mit unterschiedlichen Daten arbeiten kann. Man m\"ochte sich von der Mathematik entfernen, beh\"alt jedoch die logischen Aspekte bei, da sie unverzichtbar sind bei der L\"osung von Problemen (logisch). Man hat das Problem des DRY -- Wiederholung von Befehlssequenzen. Man m\"ochte dem Programmierer die Arbeit erleichtern und teilt Programme in kleinere Programme auf (prozedural). Jedoch gibt es noch einige Probleme, wenn Variablen von Komponenten ver\"andert werden, die von ganz anderen Bibliotheken stammen. Man weist jedem kleineren Programm einen eigenen Namensraum zu (funktional). Die neue Idee auf Basis der funktionalen Programmierung war die Rekursion. Einige Programmiersprachen finden diese Idee toll und implementieren sie, aber einige wehren sich jedoch dagegen, da sie oft langsamer arbeiten (iterativ). Software ist komplex. Das bedeutet, dass ein kleine Gruppe von Programmierern nicht mehr ausreicht, um den Quelltext eines gro\ss{}en Produkts verwalten kann. Als Konsequenz teilt man das Programm in mehrere Einheiten. Funktionen und Prozeduren sind hierf\"ur ein Ansatz, aber sollten mehr diesen datei\"ubergreifenden Ansatz besitzen. Man beginnt also damit Module zu definieren, die \"uber Schl\"usselw\"orter importiert werden (modular). Die Softwareentwicklung wird aber auch vielf\"altig. Man ist aufgeschlossen gegen\"uber neuen Ideen. So besteht darin eine Idee Programme zu notieren, wo nur das Resultat definiert wird, der Weg weitgehendst nicht (deklarativ). Man besitzt jedoch das Problem der Effizienz. Die Programmiersprache bildet dadurch nicht mehr einen sch\"ones Mittelweg zwischen Optimierung und Menschlichkeit f\"ur den Programmierer. Man versucht sich also wieder zur\"uck zur Basis zu orientieren und die Sprache leicht verst\"andlich zu machen (strukturiert) und Arbeiten parallel ablaufen zu lassen (nebenl\"aufig). Doch in den 60ern ist eine Paradigma aufgekommen, welches die bisherigen Problemans\"atze (Komplexit\"at des Quelltexts, geteiltes Arbeiten, Effizienz, No-DRY) sauber in sich l\"ost: Objektorientierung. Es handelt sich um einen v\"ollig anderen Ansatz an Probleme heranzugehen. \end{quote} Ok\ldots ein netter Aufsatz, aber wesentlich inhaltlicher korrekter sind die Generationen nach denen Programmiersprachen geordnet werden\footnote{zitiert aus ''Grundlagen der Informatik'' von Herold, Lurz und Wohlrab, S. 143}: \begin{table}[!ht] \begin{center} \begin{tabular}{| l | l | l | l |} \hline G & Sprachenart & Beispiel & Abstraktion \\ \hline 1 & Maschinen & Maschinencode & Bin\"are Befehle \\ 2 & Assembler & Assembler-Code & Symbolische Befehle \\ 3 & prozedular & FORTRAN, COBOL & Hardwareunabh\"angig \\ 3+ & funktional, objektorientiert & PASCAL, C, C++, Java, C\# & Strukturiert, OOP \\ 4 & deklarativ & LISP, PROLOG, SQL & Transaktions-orientiert \\ 5 & ? & & \\ \hline \end{tabular} \end{center} \end{table} Die Programmiersprachen ab G3 werden als ''Hochsprachen'' bezeichnet. Was wir hier quasi neu haben: Maschinencode. Maschinencode ist nichts weiter als das, was Interpreter / Compiler von Programmiersprachen \"ubersetzt. Man schreibt also einen Quelltext in C und jener wird in Maschinencode \"ubersetzt. Was sind Interpreter und Compiler? \section{Interpreter vs. Compiler} Interpreter und Compiler haben die Aufgabe Quelltexte in Maschinensprache zu \"ubersetzen und damit ausf\"uhrbar zu machen. Der Unterschied liegt darin, dass Compiler das Programm translatieren -- genauer: kompilieren -- und dadurch eine fertige Datei speichern, die abgespeichert wird. Diese Datei ist Maschinencode und jederzeit ausf\"uhrbar. Somit ist sie auch plattformabh\"angig (''Plattform'' bezeichnet ein Betriebsystem mit all seinen Softwarekomponenten). Die kompilierte Datei muss nun ausgef\"uhrt werden, damit das Ergebnis sichtbar ist. Das Gegenst\"uck sind Interpreter, wo der Quelltext in Echtzeit abgearbeitet wird und die Ausgabe direkt erfolgt. Es gibt keine kompilierte Dateien. Nat\"urlich gibt es wieder Mischformen. So gibt es JIT (''Just in time'') Compiler, die Bytecode erstellen. Dieser Bytecode ist eine plattformunabh\"angige, fast kompilierte Datei. Java ist hierf\"ur das bekannteste Beispiel. Bei python sieht man es ebenso: wird ein Programm auf der Konsole mit \textit{python program.py} gestartet, so erzeugt python eine Datei \textit{program.pyc}, die Bytecode enth\"alt. \section{Eine Sprache im Detail: python} python hat imperative (ein Befehl pro Zeile und Zeile f\"ur Zeile abarbeiten), funktionale (List Comprehension, def), prozedurale (def, global), modulare (import), strukturierte (Einr\"uckung, reduzierte Schleifenschl\"usselnotation) und vor allem objektorientierte (alles ist ein Objekt, class) Aspekte. python l\"asst sich durch entsprechende Bibliotheken leicht zu einer logischen und nebenl\"aufigen Sprache weiterentwickeln. Es handelt sich jedenfalls um eine hybride (der Begriff wird gerne vermieden, weil es urspr\"unglich die prozedural-objektorientierte Kombination bezeichnete), multiparadigmatische Skriptsprache. Sie ist turing-vollst\"andig und entstammt der Generation G3+. \chapter{Dokument und Lernstoff} \section{Status and Copyleft} \subsection{Copyleft} Use this document as you would like to. \subsection{Status} Version alpha-overbuggy \\ not proofread! Die Algorithmen sind in PHP, python und C geschrieben, da ich einmal an der Stelle mit PHP die C-Syntax brauchte, wobei ich nicht C selbst verwenden wollte (wegen main()), python syntaktisch wundersch\"on finde und C performant arbeitet. Mit PHP und python habe ich selbst am meisten Erfahrung. Weitere (nicht behandelte) Stichw\"orter: \begin{itemize} \item Komplexit\"atsklassen (weitere und im Vergleich) \item Registermaschinen (und weitere Rechenautomaten) \item NP-Schwere \item Lambda-Kalk\"ul \item Datentypen allgemein \item Dynamik (bez. Datentypen) von Programmiersprachen \item Unterschied Programmier- und Skriptsprachen \item Bitweise Berechnungen (Bit-Shift, \ldots) \item T\"urme von Hanoi \item Meta-Heuristik \item Nearest Neighbour Heuristik \item Greedy-Algorithmen \item Pseudozufallszahlen \item A* Algorithmus \item Rekursiv erzeugte Graphiken \end{itemize} \section{Fragen} \begin{itemize} \item Definiere den Begriff Algorithmus allgemein und gehe danach auf Turings Definition ein. \begin{itemize} \item schrittweise Anleitung zur L\"osung eines Problems \item Chwarizmi, Babbage (Bernoulli-Zahlen), Turing, Church, \ldots \item Finitheit \item Ausf\"uhrbarkeit \item Platzkomplexit\"at, dynamische Finitheit \item Terminierung, Zeitkomplexit\"at \item Determiniertheit \item Determinismus \end{itemize} \item Zeige einfache Algorithmen und ihre visuellen Darstellungen \begin{itemize} \item Identische Abbildung \item Division \item Struktogramm (Nassi-Shneiderdiagramm, Bl\"ocke) \item Flussdiagramm (Pfeile) \end{itemize} \item Zeige einige Probleme auf und definiere sie bez\"uglich ihrer L\"osbarkeit \begin{itemize} \item Problem des Handlungsreisenden (unl\"osbar) \item Speisende Philosophen (bedingt l\"osbar) \item Rucksackproblem (l\"osbar) \item Damenproblem (l\"osbar) \item Landkartenf\"arbungsproblem (l\"osbar) \end{itemize} \item Definiere allgemeine L\"osungsans\"atze an diese Probleme \begin{itemize} \item Heuristik \item Backtracking \item Divide and conquer \end{itemize} \item Erkl\"are die Grundelemente der beiden Wissenschaften aus der theoretischen Informatik \begin{itemize} \item siehe oben (Finitheit, \ldots) \item Landau-Symbole \item Komplexit\"atsklasse \end{itemize} \item Erkl\"are die Turingmaschine und ihre Bedeutung \begin{itemize} \item Aufbau \item Anwendung \item Halteproblem \end{itemize} \item Analysiere den Algorithmus MergeSort nach den genannten Kriterien \begin{itemize} \item Funktionsweise \item Stabilit\"at \item rekursiv / iterativ? \item (best, worst, average case) Zeitkomplexit\"at \item Raumkomplexit\"at \end{itemize} \item Implementiere den euklidischen Algorithmus auswendig \begin{itemize} \item alt, iterativ \item alt, rekursiv \item modern, iteratv \item modern, rekursiv \end{itemize} \item Erkl\"are Grundelemente von Programmiersprachen \begin{itemize} \item Bedingte Anweisungen \item Schleifen (for, while, Container-Iteration) \item Logik (Vergleichsoperatoren, Boolsche Algebra) \item Prozeduren vs. Funktionen \item GOTO \end{itemize} \item Erkl\"are die Begriffe Turing-Vollst\"andigkeit, Programmierparadigma und Generation in Bezug auf Programmiersprachen und teile sie historisch zu \begin{itemize} \item imperativ, logisch, iterativ, prozedural, funktional, modular, deklarativ, strukturiert, objektorientiert, nebenl\"aufig, hybrid \item 1, 2, 3, 3+, 4. Begriff Hochsprachen \item FORTRAN als erste Hochsprache Sprache \item PASCAL, BASIC, C, C++, python, Java, C\# folgend \item LISP, PROLOG, SQL \end{itemize} \item Nenne Beispiele f\"ur Programmiersprachen und gehe n\"aher auf die besprochenen Kriterien ein, die an Programmierer und Maschine gestellt werden \begin{itemize} \item python wurde im Dokument besprochen (Interpreter, Compiler, erlaubte Paradigmen, Generation, Turing-Vollst\"andigkeit) \end{itemize} \end{itemize} \section{Fragen} \begin{itemize} \item Wie nennt man das? Dreieckstausch? \item n*log(n) liegt zwischen n und $n^2$ \end{itemize} \section{Vorgehensweise bei Matura} \begin{itemize} \item Immer Problemaufriss machen! \item Struktogramme, Flussdiagramme vorbereiten \item M\"oglichst \"Uberschriften aus Dokument verwenden \item Graphiken, \"Ubersichten vorbereiten \item Algorithmen genau durchdenken \end{itemize} \end{document}