Etymologie, Etimología, Étymologie, Etimologia, Etymology
DE Deutschland, Alemania, Allemagne, Germania, Germany
Algorithmus (Algorithmentheorie), Algoritmo, Théorie des algorithmes, Algoritmo, Algorithm Theory

A

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.

• 2.4.1 Algorithmen
• 6.1 Algorithmen und Datenstrukturen
• 6.1.2 Sortier-Algorithmen
• 6.1.3 Such-Algorithmen

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.

"Genetische Algorithmen" sind ein neues Teilgebiet der Informatik, das vor dem Hintergrund der Darwinschen Selektion versucht, intelligente Software hervorzubringen. Dazu wird ein Optimum aus mehreren Richtungen gleichzeitig gesucht, und die Pfade zum Optimum werden simultan verarbeitet. Genetische Algorithmen eignen sich unter anderem für Roboterprogrammierungen, Mustererkennungsprobleme, Minimax-Strategien oder das Training Neuronaler Netze. Aber auch bei der Vorhersage von Preisentwicklungen an den Finanzmärkten kommen induktive Methoden (wie der genetischen Algorithmen) zum Einsatz.

B

C

D

E

F

fh-rhein-sieg
Textalgorithmen

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

G

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

H

I

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
• Bin Packing oder Wie bekomme ich die Klamotten in die Kisten? - 24. 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
• Gewinnstrategie für ein Streichholzspiel - 14. 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)

J

K

L

M

N

NULL-Algorithmus (W3)

O

P

Q

R

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)
• 14. Algorithmus der Woche (6. Juni): Gewinnstrategie für ein Streichholzspiel (Jochen Könemann, U Waterloo - Kanada)
• 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)

S

T

U

V

W

X

Y

Z

Buecher zur Kategorie:

Etymologie, Etimología, Étymologie, Etimologia, Etymology
DE Deutschland, Alemania, Allemagne, Germania, Germany
Algorithmus (Algorithmentheorie), Algoritmo, Théorie des algorithmes, Algoritmo, Algorithm Theory

amazon - Algorithmus (Algorithmentheorie), Algoritmo, Théorie des algorithmes, Algoritmo, Algorithm Theory

      Algoritmo (IT)    

A

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

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

C

D

E

F

G

H

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

I

J

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.

K

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

L

M

N

O

P

Q

R

S

T

U

V

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.

W

X

Y

Z