Algorithmus (W3)

• (1) Elementarität: die Zerlegung eines komplexen Prozesse in Grundoperationen, die selbst nicht weiter zerlegbar sind.
• (2) Determiniertheit: die Reihenfolge dieser Grundoperationen ist streng festgelegt, schematisiert.
• (3) Allgemeinheit: Die Operationen richten sich auf Objekte, deren Natur für den Algorithmus gleichgültig ist und die zu einer Klasse möglicher Objekte gehören.
• (4) Endlichkeit: Ein Algorithmus muss in doppelter Hinsicht endlich sein: Endlichkeit der Vorschrift der Ausführung und Endlichkeit der Operationszeit einzelner Schritte.

Algorithmus "Anleitung für ein Berechnungsverfahren"
...
Dieser Ausdruck hat nichts mit den obigen Wörtern zu tun, obwohl das "th" an griechisch "arithmós" "Zahl" erinnert.
...

Der persisch-arabische Mathematiker und Astronom "Mohamed ibn Musa al-Chwarismi" ("al-Khwarismi", "al-Chwarazmi", mlat. "Algorismi") (* in Charism um 780, † Bagdad nach 846) machte durch eine Bearbeitung des "Sindhind Von Brahmagupta" (628) und durch sein Rechenbuch "Hisab al-jabr w.almuqabalah" (um 825) die Araber mit dem Gebrauch indischer Ziffern, ihrem Stellenwertsystem und der Null (Dezimalsystem) bekannt. Der Anfang des arabischen Titels des Rechenbuches lebt in dem Wort "Algebra" weiter, "al-Chwarismis" Name in "Algorithmus". Das "Hisab al-jabr" erschien im 12. Jh. in lateinischer Sprache.

Das erste kaufmännische Rechenbuch auf deutschem Boden verfaßte der Regensburger Benediktinerfrater Fridericus Gerhart († 1464 oder 1465) mit seinem "Algorismus Ratisbonensis" (lat. = "Regensburger Algorithmus"). Der eine umfangreiche Aufgabensammlung ("Practica") aus dem Wirkungsbereich des Kaufmanns, Münzmeisters u.ä. enthaltende "Algorismus Ratisbonensis" ist in sechs Handschriften (teils lateinisch, teils deutsch, teils in einem Sprachgemisch) überliefert, von denen die älteste 1449-1450 geschrieben wurde.

• 6. Algorithmen zur Datumsberechnung
• Weitere Datumsalgorithmen

• 1.3 Algorithmen und Programme
• 1.3.1 Algorithmen
• 1.3.2 Algorithmenstrukturen und Darstellungsformen
• 5.2.1 Vager Algorithmusbegriff und Berechenbarkeit
• 5.2.2 Algorithmische Unlösbarkeit
• 5.2.3 Algorithmisch unlösbare Probleme
• 5.3 Effiziente Algorithmen und Komplexität
• 5.3.13 Effiziente Näherungsalgorithmen

"Algorithmus" (arab. = "Rechenbuch") ist zunächst der Personenname des Arabers "Muhammed Ibn Musa Alchwarizoni", dessen Rechenbuch (Anf. des IX. Jahrh.) im Westen durch Übersetzungen verbreitet wurde. Er nahm in den lateinischen Übersetzungen des Buches die Form "Algorithmi" an. Später verstand man unter Algorithmus ein Rechenbuch oder die Rechenkunst.

Das Rechenbuch des Alchwarizoni vermittelte dem Abendland die Kenntnis der Null und des indisch-arabischen Rechnens. Es bildete sich daher im 12ten Jahrh. eine Schule der Algorithmiker, die den Sieg über die von Papst Gerbert (Sylvester II., 940-1003) herstammende Schule der Abacisten (von abacus = Rechenbrett) davontrug.

Unter logischem Algorithmus versteht man jetzt die in der Gegenwart eifrig betriebenen Versuche, die logischen Operationen durch ein besonderes Zeichensystem und Rechnungsverfahren zu ersetzen. Vertreter dieser Bestrebungen sind in Deutschland vor allem Schroeder, in England Mc-Coll, in Amerika Peirce, in Italien Peano u. a. Vgl. Reinaud, Mémoire géographique etc. sur l'Inde. Paris 1849. Tropfke, Gesch. d. Elementarmathematik. Leipzig 1902/3. Teil I S. 13 u. 14.

fh-rhein-sieg
Textalgorithmen

Peter Becker
FH Bonn-Rhein-Sieg
Fachbereich Angewandte Informatik
Vorlesung Sommersemester 2002
...

grundstudium
Algorithmen

| Rekurrenzen | Euklid (Bestimmung des ggTs) | Binäre Suche | Mergesort | Quicksort | Worst-Case | Average Case | Mastertheorem | Übersicht | Verständnis des Beweises | Ableitung der untersten Schranke von Sortierverfahren | Weitere Sortierverfahren | Countingsort | Bucketsort | Radixsort | Graphen - Tiefensuche/Breitensuche | Dijkstra-Beweis | Bäume | Definition | Höhe und Tiefe | Regeln | Allgemeine | Für Binär-Bäume | Erzeugung von Wäldern aus Graphen | Ungerichtete Graphen | Allgemeine Eigenschaften | Äquivalente Aussagen | Minimumheap | Darstellung durch Arrays | Einfügen | Löschen | Heapsort | Algorithmus | Laufzeit | Union-Find-Wälder | Kruskal zur Erstellung des MST | Abbruchkriterium | Laufzeit | Speichermöglichkeiten von Datenmengen mit dynamischer Größe | Hashing | Verschiedene Hashfunktionen | Offenes Hashing mit Kollisionslisten | Geschlossenes Hashing mit offener Adressierung | Dynamisches Hashing | Balancierte Bäume | Höhe von Bäumen | Suchbäume | AVL | Blatt | B-Bäume | Greedy | Huffman-Codes | Graph-Färbe-Problem | Rucksackproblem | Spielbäume | 15er-Puzzle | Tic-Tac-Toe | Dynamisches Programmieren | Floyd | Beweis | Beispiel | Negative Zyklen | Konstruktion des Pfades | Warshall | TSP | TSP mit dynamischen Programmieren | Kosten TSP mit dynamischen Programmieren | Graphen | DFS in Digraphen (Baumkante,Vorwärtskante,Rückwärtskante und Seitwärtskante) | Topologische Sortierung | SCCs - ,,strongly connected component'' - Starke Zusammenhangskomponenten | Algorithmus - Aho/Hopcroft/Ullman | Beweis des SCC-Algorithmusses | Netzwerkflußproblem | Ford&Fulkerson-Algorithmus | Algorithmus | Worst Case | Optimierung | Bipartites Matching | Mustererkennung | Naives Verfahren | KMP - Knuth, Morris und Pratt | Boyer-Moore | Scanlines | Sichtbarkeitsproblem für horizontale Objekte | Schnittproblem für horizontale und vertikale Objekte | Geometrisches Divide&Conquer für horizontal und vertikal liegende Objekte | Schnittproblem für (fast) beliebig liegende Objekte | Voronoidiagramme (nur eine kurze Vorstellung) | Randomisierte Algorithmen | Las Vegas & Monte Carlo | Randomisiertes Quicksort | Mustererkennung - Karp&Rabin | Universelles Hashing | Skip-Listen

informatikjahr
Der Algorithmus der Woche

Liste der bisherigen Algorithmen der Woche

• Faires Teilen - 43. Algorithmus der Woche
• Kleinster umschließender Kreis - 42. Algorithmus der Woche
• Simulated Annealing - 41. Algorithmus der Woche
• Das Travelling Salesman Problem - 40. Algorithmus der Woche
• Gauß-Seidel Iteration zur Berechnung physikalischer Probleme - 39. Algorithmus der Woche
• Zufallszahlen - 38. Algorithmus der Woche
• Fingerprinting - 37. Algorithmus der Woche
• Turnier- und Sportligaplanung - 36. Algorithmus der Woche
• Zyklensuche - 35. Algorithmus der Woche
• Hashing - 34. Algorithmus der Woche
• Mehrheitsbestimmung - Wer wird Klassensprecher? - 33. Algorithmus der Woche
• Kreise zeichnen mit Turbo - 32. Algorithmus der Woche
• Dynamische Programmierung: Evolutionäre Distanz - 31. Algorithmus der Woche
• Texte durchsuchen  aber schnell: Der Boyer-Moore-Horspool-Algorithmus - 30. Algorithmus der Woche
• Poker per E-Mail - 29. Algorithmus der Woche
• Teilen von Geheimnissen - 28. Algorithmus der Woche
• Der One-Time-Pad-Algorithmus - Der einfachste und sicherste Verschlüsselungsalgorithmus - 26. Algorithmus der Woche
• Das Sieb des Eratosthenes - Wie schnell kann man alle Primzahlen bis eine Milliarde berechnen? - 25. Algorithmus der Woche
• Maximale Flüsse - Die ganze Stadt will zum Stadion - 23. Algorithmus der Woche
• Partnerschaftsvermittlung - 22. Algorithmus der Woche
• Minimale aufspannende Bäume - 21. Algorithmus der Woche
• Online-Algorithmen: Was ist es wert, die Zukunft zu kennen? - 20. Algorithmus der Woche
• Der Alphabeta-Algorithmus für Spielbaumsuche: Wie bringe ich meinen Computer zum Schachspielen? - 19. Algorithmus der Woche
• Der Euklidische Algorithmus - 18. Algorithmus der Woche
• Einweg-Funktionen - Vorsicht Falle: Rückweg nur für Eingeweihte! - 17. Algorithmus der Woche
• Multiplikation langer Zahlen ...schneller als in der Schule - 16. Algorithmus der Woche
• Das Rucksackproblem - Die Qual der Wahl bei zu vielen Möglichkeiten - 15. Algorithmus der Woche
• 13. (30. Mai): Algorithmen zum EAN-Barcode - Fehlererkennende Codes: Was ist eigentlich ISBN? (Angelika Steger, ETH Zürich)
• 12. (23. Mai): Paralleles Sortieren (Rolf Wanka, FAU Erlangen-Nürnberg)
• 11. (16. Mai): Broadcasting (Gerüchte verbreiten) (Christian Scheideler, TU München)
• 10. (9. Mai): Page-Rank-Algorithmus (Ulrik Brandes und Gabi Dorfmüller, U Konstanz)
• 9. (2. Mai): Eulerkreise - Wie Leonhard Euler das Haus vom Nikolaus zeichnet - (Peter Liske, Michael Behrisch und Amin Coja-Oghlan, HU Berlin)
• 8. (25. April): Topologisches Sortieren (Hagen Höpfner, IU Bruchsal)
• 7. (18. April): Kürzeste Wege (Peter Sanders und Johannes Singler, TU Karlsruhe)
• Der Pledge-Algorithmus - Wie man im Dunkeln aus einem Labyrinth entkommt - 6. Algorithmus der Woche
• Tiefensuche - 5. Algorithmus der Woche
• 4. (28. März): Zahlen richtig aussprechen (Lothar Schmitz, Univ. der Bundeswehr München)
• 3. (21. März): Schnelle Sortieralgorithmen (Helmut Alt, FU Berlin)
• 2. (14. März): Sortieren durch Einfügen (Wolfgang Kowalk, U Oldenburg)
• 1. (7. März): Binäre Suche (Jost Enderle und Thomas Seidl, RWTH Aachen)

NP-Problem (W3)

12.11.2013

Das NP-Problem der E-Autos: Algorithmen für die städtische E-Mobilität

Der Markt für Elektroautos kommt allmählich in Schwung. Doch dem Angebot von Herstellern wie Tesla Motors, Nissan, BMW, Ford oder Honda steht noch keine ausreichende Anzahl von Ladestationen in Städten gegenüber. Informatiker um Albert Lam von der Hongkong Baptist University haben nun die Frage untersucht: Wie sähe eine ideale räumliche Verteilung von Ladestationen aus? Ihre Antwort: Das Problem ist mathematisch gesehen „NP-schwer“ (NP steht für nichtdeterministische Polynomialzeit).

Das bedeutet, dass es keine Abkürzung gibt, um rasch Lösungen zu finden. Man muss das Problem erschöpfend durchrechnen.
...

Das NP-Problem der Elektromobilität

12.11.2013 - TR Online

Informatiker aus Hongkong haben gezeigt, dass die optimale Verteilung von Ladestationen für E-Autos leider nicht einfach und elegant zu berechnen ist. Man muss verschiedene Strukturen durchprobieren.
...

NP-Probleme - Begriffliches

Problemen sieht man im Allgemeinen nicht an, ob sie aufwandsmäßig leicht oder schwer lösbar sind. Es ist sogar so, dass ganz ähnliche Probleme, deren Formulierung nur geringfügige Abweichungen aufweisen, fundamental unterschiedliche Aufwände zur Lösung beanspruchen.
...

A problem is assigned to the NP (nondeterministic polynomial time) class if it is solvable in polynomial time by a nondeterministic Turing machine.
...

NULL-Algorithmus (W3)

raikas.net
Quadratische Gleichungen bei al-Khwarizmi

Vorspann:

Wir lösen heute quadratische Gleichungen im Prinzip genauso wie der arabische Mathematiker al-Khwarizmi es bereits vor mehr als 1000 Jahren getan hat. Sein Lösungsverfahren, welches er geometrisch begründete, unterscheidet sich von unserem eigentlich nur durch eine ungewohnte sprachliche Darstellungsweise. Al-Khwarizmis originale Erläuterungen sind durchaus zugänglich, so daß es möglich ist, seine Denkweisen an authentischen Texten nachzuvollziehen.

Interessant sind insbesondere die geometrischen Begründungen, die al-Khwarizmi angibt - sie führen zu einem tieferen Verständnis des algebraischen Lösungsverfahrens für quadratische Gleichungen.

Der folgende Text beschreibt al-Khwarizmis Lösungsverfahren - es ist eine abgewandelte Version meines Artikels in mathematik lehren 91, S. 14-18 (Friedrich Verlag, Velber, 1998).

Alle Zitate entstammen dem Buch The Algebra of Mohammed Ben Musa von Frederic Rosen (Olms, Hildesheim, 1986). Gleiches gilt für die Abbildungen 1 und 3. Quelle der Abbildung 2 ist die sowjetische Post (??? ???, 1983).
...
Mit dem "Buch der Addition und Subtraktion für die indische Rechenmethode" veröffentlichte er das erste Buch, in dem das Rechnen mit den indischen Zahlzeichen erläutert wurde. Dieses Werk heißt im Original" Al-kitab al-gam' wa'l-tafriq bi hisab al-hind" und kam über Spanien, welches damals zum arabischen Reich gehörte, nach Europa. Dort wurde es unter dem Titel "Algorismi de numero indorum" übersetzt. Der Name "al-Khwarizmi" wurde in "Algorismi" verändert, und aus "Algorismi" entstand der heutige Begriff "Algorithmus".

Zu jener Zeit schrieb al-Khwarizmi auf Wunsch von al-Ma'mum auch sein Werk "Ein kurzgefaßtes Buch über die Rechenverfahren durch Ergänzen und Ausgleichen" (im Original: "Al-kitab al-muhtasar fi hisab al-gabr wa'l-muqabala". Aus dem arabischen Wort für "Ergänzen" "al-gabr" entstand der heutige Begriff "Algebra").
...

rwth-aachen
Algorithmus der Woche

Algorithmen sind clevere Verfahren, die Probleme verschiedenster Art effizient lösen. Dabei geht es nicht nur um arithmetische Probleme wie etwa die effiziente Addition oder Multiplikation, sondern auch um ganz alltägliche Fragestellungen.

• Wie durchsuche ich möglichst schnell mein CD-Regal?
• Wie finde ich den Ausgang aus einem Labyrinth?
• Wie berechne ich die kürzeste Verbindung zwischen zwei Städten?

Diese und andere Fragen können durch geschickte Algorithmen effizient gelöst werden. Die Aktion "Algorithmus der Woche" widmet jeweils eine Woche der Präsentation eines besonders interessanten Algorithmus, der Grundprinzipien des Algorithmendesigns illustriert und anhand von interessanten Anwendungen erläutert.

Der neue "Algorithmus der Woche" wird jeweils Dienstags präsentiert.

Liste der bisherigen Algorithmen der Woche

• 1. Algorithmus der Woche (7. März): Binäre Suche (Jost Enderle und Thomas Seidl, RWTH Aachen)
• 2. Algorithmus der Woche (14. März): Sortieren durch Einfügen (Wolfgang Kowalk, U Oldenburg)
• 3. Algorithmus der Woche (21. März): Schnelle Sortieralgorithmen (Helmut Alt, FU Berlin)
• 4. Algorithmus der Woche (28. März): Zahlen richtig aussprechen (Lothar Schmitz, Univ. der Bundeswehr München)
• 5. Algorithmus der Woche (4. April): Labyrinth und Tiefensuche (Michael Dom, Falk Hüffner und Rolf Niedermeier, U Jena)
• 6. Algorithmus der Woche (11. April): Roboter im Labyrinth (Rolf Klein und Tom Kamphans, Bonn)
• 7. Algorithmus der Woche (18. April): Kürzeste Wege (Peter Sanders und Johannes Singler, TU Karlsruhe)
• 8. Algorithmus der Woche (25. April): Topologisches Sortieren (Hagen Höpfner, IU Bruchsal)
• 9. Algorithmus der Woche (2. Mai): Eulerkreise (Peter Liske, Michael Behrisch und Amin Coja-Oghlan, HU Berlin)
• 10. Algorithmus der Woche (9. Mai): Page-Rank-Algorithmus (Ulrik Brandes und Gabi Dorfmüller, U Konstanz)
• 11. Algorithmus der Woche (16. Mai): Broadcasting (Gerüchte verbreiten) (Christian Scheideler, TU München)
• 12. Algorithmus der Woche (23. Mai): Paralleles Sortieren (Rolf Wanka, U Erlangen-Nürnberg)
• 13. Algorithmus der Woche (30. Mai): Fehlererkennende Codes (Alexander Souza und Angelika Steger, U Freiburg und ETH Zürich)
• 15. Algorithmus der Woche (13. Juni): Das Rucksackproblem (Rene Beier und Berthold Vöcking, MPI Saarbrücken und RWTH Aachen)
• 16. Algorithmus der Woche (20. Juni): Wie schnell kann man multiplizieren? (Arno Eigenwillig und Kurt Mehlhorn, MPI Saarbrücken)
• 17. Algorithmus der Woche (27. Juni): Einwegfunktionen (Rüdiger Reischuk und Markus Hinkelmann, U Lübeck)
• 18. Algorithmus der Woche (4. Juli): Euklidischer Algorithmus (Friedrich Eisenbrand, U Dortmund)
• 19. Algorithmus der Woche (11. Juli): Der Alphabeta-Algorithmus für Spielbaumsuche (Ulf Lorenz, Burkhard Monien, Daniel Warner, U Paderborn)
• 20. Algorithmus der Woche (18. Juli): Online-Algorithmen: Was ist es wert, die Zukunft zu kennen? (Susanne Albers, Swen Schmelzer, U Freiburg)
• 21. Algorithmus der Woche (25. Juli): Minimale aufspannende Bäume (Katharina Langkau und Martin Skutella, U Dortmund)
• 22. Algorithmus der Woche (1. August): Partnerschaftsvermittlung (Volker Claus, Volker Diekert, Holger Petersen, U Stuttgart)
• 23. Algorithmus der Woche (8. August): Maximale Flüsse (Robert Görke, Steffen Mecke, Dorothea Wagner, U Karlsruhe)
• 24. Algorithmus der Woche (15. August): Online Algorithmen für Bin Packing (Joachim Gehweiler, Friedhelm Meyer auf der Heide, U Paderborn)
• 25. Algorithmus der Woche (22. August): Das Sieb des Eratosthenes (Rolf H. Möhring, Martin Oellrich, Robert Pankrath, TU Berlin)
• 26. Algorithmus der Woche (29. August): One-Time-Pad (Till Tantau, U Lübeck)
• 28. Algorithmus der Woche (12. September): Geheimnisse teilen (Johannes Blömer, U Paderborn)
• 29. Algorithmus der Woche (19. September): Pokern im Internet (Detlef Sieling, U Dortmund)
• 30. Algorithmus der Woche (26. September): Texte durchsuchen - aber schnell (Markus Nebel, TU Kaiserslautern)
• 31. Algorithmus der Woche (3. Oktober): Dynamische Programmierung: Evolutionäre Distanz (Norbert Blum, Matthias Kretschmer, U Bonn)
• 32. Algorithmus der Woche (10. Oktober): Kreise zeichnen mit Turbo (Leif Kobbelt, Dominik Sibbing, RWTH Aachen)
• 33. Algorithmus der Woche (17. Oktober): Mehrheitsbestimmung - Wer wird Klassensprecher? (Thomas Erlebach, ETH Zürich)
• 34. Algorithmus der Woche (24. Oktober): Hashing (Christian Schindelhauer, U Freiburg)
• 35. Algorithmus der Woche (31. Oktober): Zyklensuche (Holger Schlingloff, HU Berlin)
• 36. Algorithmus der Woche (7. November): Turnier- und Sportligaplanung (Sigrid Knust, U Osnabrück)
• 37. Algorithmus der Woche (14. November): Fingerprinting (Martin Dietzfelbinger, TU Ilmenau)
• 38. Algorithmus der Woche (21. November): Zufallszahlen (Bruno Müller-Clostermann, Tim Jonischkat, U Duisburg-Essen)
• 39. Algorithmus der Woche (28. November): Gauß-Seidel Iteration zur Berechnung physikalischer Probleme (Christoph Freundl, Ulrich Rüde, U Erlangen-Nürnberg)
• 40. Algorithmus der Woche (5. Dezember): Das Travelling Salesman Problem (Stefan Näher, U Trier)
• 41. Algorithmus der Woche (12. Dezember): Simulated Annealing (Peter Rossmanith, RWTH Aachen)
• 42. Algorithmus der Woche (19. Dezember): Kleinster umschließender Kreis (Emo Welzl, ETH Zürich)
• 43. Algorithmus der Woche (26. Dezember): Cake Cutting (Raimund Seidel, U Saarbrücken)

Arndt, Jörg (Autor) / Haenel, Christoph (Autor)
Pi
Algorithmen, Computer, Arithmetik

Kurzbeschreibung
Ausgehend von der Programmierung moderner Hochleistungsalgorithmen stellen die Autoren das mathematische und programmtechnische Umfeld der Zahl Pi ausführlich dar. So werden zur Berechnung von Pi sowohl die arithmetischen Algorithmen, etwa die FFT-Multiplikation, die super-linear konvergenten Verfahren von Gauß, Brent, Salamin, Borwein, die Formeln von Ramanujan und Borwein-Bailey-Plouffe bis zum neuen Tröpfel-Algorithmus behandelt. Der Leser findet viel Anregendes wie auch Skurriles, etwa interessante Anmerkungen zur Quadratur des Kreises. Die beigelegte CD-ROM bietet dem User mannigfaltigen Nutzen, z.B. die ausgeführte Langzahlarithmetik hfloat im C++ Source-Code, die FFT- Multiplikation und Algorithmen zur Pi-Berechnung. Die zweite, überarbeitete Auflage nimmt zahlreiche Leseranregungen auf und berichtet über die wichtigsten neuesten Ergebnisse der Pi-Forschung. Zahlreiche Verweise auf Internetquellen, ausführlicher Index und Literaturverzeichnis ergänzen das Buch.

3. überarb. Aufl., 2011, 260 S.
Geb., ISBN 978-3-540-48246-8
Erscheinungstermin: Oktober 2011

3., überarbeitete und erweiterte Auflage mit neuen Pi-Entdeckungen
Viel Anregendes sowie auch Skurriles
Interessante Anmerkungen zur Quadratur des Kreises
...
Der Stand der Dinge.- Wie zufällig ist Pi?- Näherungen für Pi und Kettenbrüche.- Arcus Tangens.- Tröpfel-Algorithmen.- Gauß und Pi.- Ramanujan und Pi.- Die Borweins und Pi.- Das BBP-Verfahren.- Arithmetik.- Vermischtes.- Historie.- Die Zukunft: Internet und Pi-Berechnungen.- Formelsammlung Pi.- Tabellen.- Documentation for the hfloat library.- Other high precision libraries.- Literaturverzeichnis.- Index.

Böttcher, Martin (Autor)
Unifikation disjunktiver Attributterme
Auswertealgorithmen und Anwendungen in einer Valenzgrammatik zur Textanalyse

Hochstättler, Winfried (Autor)
Algorithmische Mathematik

Kurzbeschreibung
Mit diesem Buch wollen wir verschiedene Teilgebiete der Mathematik aus algorithmischer Perspektive vorstellen und dabei auch Implementierungs- und Laufzeitaspekte diskutieren. Gleichzeitig möchten wir, bei einer verkürzten Grundausbildung in Mathematik in naturwissenschaftlichen und informatischen Studiengängen, möglichst viele Teilaspekte der Mathematik vorstellen und vielleicht zu einer vertiefenden Beschäftigung mit dem einen oder anderen Aspekt anregen.

Unser Ziel ist es dabei nicht, den Leser zu einem versierten Anwender der besprochenen Algorithmen auszubilden, sondern wir wollen, immer ausgehend von konkreten Problemen, Analyse- und Lösungsstrategien in den Mittelpunkt stellen. Hierbei spielen insbesondere Beweise und Beweistechniken eine zentrale Rolle.

Inhaltsverzeichnis 1 Notation und Grundstrukturen . . . 1 1.1 Gliederung und Motivation . . . 1 1.2 Notation . . . 2 1.3 Abbildungen . . . 4 1.4 Beweismethoden und das Prinzip der vollständigen Induktion . . . 5 1.4.1 Beweis durch Kontraposition . . . 5 1.4.2 Widerspruchsbeweis oder reductio ad absurdum . . . 7 1.4.3 Das Prinzip der vollständigen Induktion . . . 7 2 Elementare Abzählprobleme und diskrete Wahrscheinlichkeiten . . 11 2.1 Abbildungen und Mengen . . . 11 2.2 Injektive Abbildungen, Permutationen und Fakultät . . . 12 2.3 Binomialkoeffizienten. . . 15 2.4 Abschätzungen . . . 20 2.5 Abschätzungen für Fakultäten und Binomialkoeffizienten . . . 23 2.6 Das Prinzip von Inklusion und Exklusion. . . 28 2.7 Diskrete Wahrscheinlichkeitsrechnung . . . 33 2.7.1 Wahrscheinlichkeitsraum . . . 33 2.7.2 Bedingte Wahrscheinlichkeiten . . . 35 2.7.3 Paradoxa . . . 36 2.7.4 Zufallsvariablen . . . 38 3 Graphen . . . 41 3.1 Relationen . . . 41 3.1.1 Äquivalenzrelationen . . . 41 3.1.2 Partialordnungen . . . 43 3.2 Definition eines Graphen, Isomorphismus . . . 45 3.3 Teilgraphen . . . 49 3.4 Zusammenhang . . . 50 3.5 Kodierung von Graphen . . . 51 3.6 Effiziente Algorithmen . . . 55 3.7 Breitensuche . . . 56 3.8 Tiefensuche . . . 58 3.9 Valenzsequenzen . . . 60 3.10 Eulertouren. . . 64 3.11 Gerichtete Graphen und Eulertouren . . . 69 3.12 2-Zusammenhang . . . 72 4 Bäume und Matchings . . . 77 4.1 Definition und Charakterisierungen . . . 77 4.2 Isomorphismen von Bäumen . . . 79 4.3 Aufspannende Bäume . . . 84 4.4 Minimale aufspannende Bäume. . . 86 4.5 Die Algorithmen von Prim-Jarnik und Boruvka . . . 88 4.6 Die Anzahl aufspannender Bäume . . . 93 4.7 Bipartites Matching . . . 94 4.8 Stabile Hochzeiten . . . 101 5 Numerik und lineare Algebra . . . 105 5.1 Etwas mehr Notation. . . 105 5.2 Kodierung von Zahlen . . . 107 5.3 Fehlerquellen und Beispiele . . . 113 5.4 Gaußelimination und LU-Zerlegung, Pivotstrategien . . . 116 5.5 LU-Zerlegung . . . 119 5.6 Gauß-Jordan-Algorithmus . . . 127 5.7 Elementares über Eigenwerte . . . 128 5.8 Choleskyfaktorisierung . . . 128 5.9 Matrixnormen . . . 133 5.10 Kondition . . . 136 6 Nichtlineare Optimierung . . . 141 6.1 Steilkurs mehrdimensionale Differentialrechnung . . . 142 6.1.1 Kurven . . . 142 6.1.2 Partielle Ableitungen . . . 146 6.2 Notwendige und hinreichende Bedingungen für Extremwerte . . . 151 6.3 Exkurs Mannigfaltigkeiten und Tangentialräume . . . 155 6.4 Bedingungen für Extrema auf gleichungsdefinierten Mengen . . 156 6.5 Bedingungen für Extrema auf ungleichungsdefinierten Mengen . . 161 7 Numerische Verfahren zur Nichtlinearen Optimierung . . . 169 7.1 Das allgemeine Suchverfahren . . . 169 7.2 Spezielle Suchverfahren . . . 175 7.3 Koordinatensuche und Methode des steilsten Abstiegs . . . 181 7.4 Newtonverfahren . . . 186 7.5 Verfahren der konjugierten Richtungen . . . 190 8 Lineare Optimierung . . . 199 8.1 Modellbildung . . . 199 8.2 Der Dualitätssatz der Linearen Optimierung . . . 207 8.3 Das Simplexverfahren. . . 211 8.4 Tableauform des Simplexalgorithmus . . . 216 8.5 Pivotwahl, Entartung, Endlichkeit . . . 218 8.6 Bemerkungen zur Numerik . . . 221 8.7 Die Zweiphasenmethode . . . 222 8.8 Sensitivitätsanalyse . . . 226 9 Lösungsvorschläge zu den Übungen . . . 229 9.1 Lösungsvorschläge zu den Übungen aus Kapitel 1 . . . 229 9.2 Lösungsvorschläge zu den Übungen aus Kapitel 2 . . . 231 9.3 Lösungsvorschläge zu den Übungen aus Kapitel 3 . . . 238 9.4 Lösungsvorschläge zu den Übungen aus Kapitel 4 . . . 246 9.5 Lösungsvorschläge zu den Übungen aus Kapitel 5 . . . 254 9.6 Lösungsvorschläge zu den Übungen aus Kapitel 6 . . . 265 9.7 Lösungsvorschläge zu den Übungen aus Kapitel 7 . . . 273 9.8 Lösungsvorschläge zu den Übungen aus Kapitel 8 . . . 283 Symbolverzeichnis . . . 291 Index . . . 293 Literaturhinweise . . . 301

Jansen, Klaus (Autor)
Margraf, Marian (Autor)
Approximative Algorithmen und Nichtapproximierbarkeit

Kurzbeschreibung
Gegenstand dieses Lehrbuchs ist die Behandlung schwer lösbarer diskreter Optimierungsprobleme. Im ersten Teil werden schnelle Algorithmen vorgestellt, die solche Probleme näherungsweise lösen können. Der zweite Teil behandelt Komplexitätstheorie und Nichtapproximierbarkeit von Optimierungsproblemen. Das Lehrbuch enthält zudem zahlreiche Anwendungsbeispiele, Übungsaufgaben, Illustrationen und Abschnitte über Grundlagen wie etwa die Turingmaschine.

Über den Autor
Klaus Jansen, Christian-Albrechts-Universität zu Kiel; Marian Margraf, Bundesamt für Sicherheit in der Informationstechnik, Bonn.

Klenk, Ursula (Herausgeber)
Computatio Linguae II
Aufsätze zur algorithmischen und quantitativen Analyse der Sprache

Ottmann, Thomas (Autor)
Widmayer, Peter (Autor)
Algorithmen und Datenstrukturen

Kurzbeschreibung
In diesem Lehrbuch werden alle Themen ausführlich behandelt, die üblicherweise den Kern des Curriculums zur Standardvorlesung "Algorithmen und Datenstrukturen" bilden. Das Themenspektrum reicht von Algorithmen zum Suchen und Sortieren über Adreßberechnungsmethoden und Listenstrukturen (Bäume aller Art) bis zu Geometrischen Algorithmen und Graphenalgorithmen. Dabei wird sowohl der Entwurf effizienter Algorithmen und Datenstrukturen als auch die Analyse ihres Verhaltens mittels mathematischer Methoden behandelt. Zahlreiche Übungsaufgaben erleichtern die Aneignung dieses Pflichtlehrstoffes. Unterstützt durch die übersichtliche Gliederung und eine präzise Sprache wird dieses Buch sicher viele Studenten erfolgreich durchs Vordiplom bringen.

Stiller, Sebastian
Planet der Algorithmen

Algorithmen: Die wichtigste Denkweise unserer Zeit unterhaltsam erklärt.

Ob Suchmaschine, Navigationssystem, Datensicherheit, Online-Dating oder Studienplatzvergabe - Algorithmen sind überall. Sie zu verstehen, ist wichtiger denn je. Mit diesem Buch kann das sogar Spaß machen. Denn Sebastian Stiller zeigt den Planeten der Algorithmen, wie wir ihn noch nie gesehen haben: jenseits von Hype und Panik, überraschend und glasklar.

Das Buch versteht sich als Reiseführer, vom Experten für die Allgemeinheit geschrieben. Schließlich gehört der Autor, ein angewandter Mathematiker, zu den Einheimischen auf dem Planeten der Algorithmen. Am Anreisetag der 7-tägigen Tour erleben wir, wie nahe uns der Planet der Algorithmen liegt, ganz egal, ob wir ein Smartphone benutzen oder noch Telefonbücher wälzen. Am 2.Tag nehmen wir uns Zeit für eine schlichte Frage: Was ist ein Algorithmus? Am 3. Tag erleben wir, wie real Komplexität auf unserem Planeten ist. Am 4.Tag erlernen wir ein paar einfache Techniken, um auf die Jagd nach Informationen zu gehen. Für den 5. Tag ist klassisches Touristenprogramm vorgesehen, unter anderem die berühmten kalifornischen Suchmaschinen. Am 6.Tag erkunden wir, wie Algorithmen menschliches Zusammenleben gestalten, und am Abreisetag machen wir die Bekanntschaft von vier alten Meistern des algorithmischen Denkens. Los geht's !

Sebastian Stiller, 1974 in Erlangen geboren, ist angewandter Mathematiker. Er entwirft und analysiert Algorithmen. In Erlangen, Leuven, Belgien, und am Massachusetts Institute of Technology (MIT) studierte er Mathematik und Philosophie. Heute forscht er an der TU Berlin und ist der lebende Beweis dafür, dass Mathematik und Sprache bestens zusammenpassen.

Vöcking, Berthold (Herausgeber)
Alt, Helmut (Herausgeber)
Dietzfelbinger, Martin (Herausgeber)
Reischuk, Rüdiger (Herausgeber)
Scheideler, Christian (Herausgeber)
Vollmer, Heribert (Herausgeber)
Wagner, Dorothea (Herausgeber)
Taschenbuch der Algorithmen

Kurzbeschreibung
Hinter vielen Computer-Programmen stecken intelligente Verfahren, die man als Algorithmen bezeichnet. Algorithmen lösen nicht nur mathematische Zahlen-Aufgaben, sondern auch ganz alltägliche Probleme: Wie ermittle ich den kürzesten Weg zwischen zwei Orten? Oder, wie kann ich einen Kuchen gerecht aufteilen? In diesem Buch erklären Informatiker 43 besonders elegante Algorithmen und illustrieren die Grundprinzipien des Algorithmendesigns anhand von interessanten Anwendungen, ohne dabei vom Leser spezielle Vorkenntnisse zu erwarten.