Gliederung der Vorlesung: Difference between revisions

From Alda
Jump to navigationJump to search
(Erster Ansatz)
(Beschreibendes Index des Vorlesungsskriptes sollte jetzt vollständig sein (Design ändert sich vielleicht noch))
Line 1: Line 1:
<!------------->
<!------------->
==[[Einführung]] (17.4.2012) ==
==[[Einführung]]==
(17.4.2012)
* Definition von Algorithmen und Datenstrukturen, Geschichte
* Definition von Algorithmen und Datenstrukturen, Geschichte
* Fundamentale Algorithmen: create, assign, copy, swap, compare etc.
* Fundamentale Algorithmen: create, assign, copy, swap, compare etc.
Line 13: Line 14:
* Sequenzen und Intervalle (Ranges)
* Sequenzen und Intervalle (Ranges)
<!------------->
<!------------->
==Sortieren==
==[[Sortieren]]==
# [[Sortieren|Artikel]] (24. und 26.4.2012)
(24. und 26.4.2012)
#* Spezifikation des Sortierproblems
* Spezifikation des Sortierproblems
#* Selection Sort und Insertion Sort
* Selection Sort und Insertion Sort
#* Merge Sort
* Merge Sort
#* Quick Sort und seine Varianten
* Quick Sort und seine Varianten
#* Vergleich der Anzahl der benötigten Schritte
* Vergleich der Anzahl der benötigten Schritte
#* Laufzeitmessung in Python
* Laufzeitmessung in Python
<!------------->
<!------------->
==Korrektheit==
==[[Korrektheit]]==
# [[Korrektheit|Artikel]] (3. und 8.5.2012)
(3. und 8.5.2012)
#* Definition von Korrektheit, Algorithmen-Spezifikation
* Definition von Korrektheit, Algorithmen-Spezifikation
#* Korrektheitsbeweise versus Testen
* Korrektheitsbeweise versus Testen
#* Vor- und Nachbedingungen, Invarianten, Programming by contract
* Vor- und Nachbedingungen, Invarianten, Programming by contract
#* Testen, Execution paths, Unit Tests in Python
* Testen, Execution paths, Unit Tests in Python
#* Ausnahmen (exceptions) und Ausnahmebehandlung in Python
* Ausnahmen (exceptions) und Ausnahmebehandlung in Python
<!------------->
<!------------->
==Effizienz==
==[[Effizienz]]==
# [[Effizienz|Artikel]] (10. und 15.5.2012)
(10. und 15.5.2012)
#* Laufzeit und Optimierung: Innere Schleife, Caches, locality of reference
* Laufzeit und Optimierung: Innere Schleife, Caches, locality of reference
#* Laufzeit versus Komplexität
* Laufzeit versus Komplexität
#* Landausymbole (O-Notation, <math>\Omega</math>-Notation, <math>\Theta</math>-Notation), Komplexitätsklassen
* Landausymbole (O-Notation, <math>\Omega</math>-Notation, <math>\Theta</math>-Notation), Komplexitätsklassen
#* Bester, schlechtester, durchschnittlicher Fall
* Bester, schlechtester, durchschnittlicher Fall
#* Amortisierte Komplexität
* Amortisierte Komplexität
<!------------->
<!------------->
==[[Suchen]] (22. und 24.5.2012)==
==[[Suchen]]==
#* Lineare Suche
(22. und 24.5.2012)
#* Binäre Suche in sortierten Arrays, Medianproblem
* Lineare Suche
#* Suchbäume, balancierte Bäume
* Binäre Suche in sortierten Arrays, Medianproblem
#* selbst-balancierende Bäume, Rotationen
* Suchbäume, balancierte Bäume
#* Komplexität der Suche
* selbst-balancierende Bäume, Rotationen
* Komplexität der Suche
<!------------->
<!------------->
# [[Prioritätswarteschlangen]] (29.5.2012)
==[[Prioritätswarteschlangen]]==
#* Heap-Datenstruktur
(29.5.2012)
#* Einfüge- und Löschoperationen
* Heap-Datenstruktur
#* Heapsort
* Einfüge- und Löschoperationen
#* Komplexität des Heaps
* Heapsort
* Komplexität des Heaps
<!------------->
<!------------->
# [[Hashing und assoziative Arrays]] (31.5.und 5.6.2012)
==[[Hashing und assoziative Arrays]]==
#* Implementation assoziativer Arrays mit Bäumen
(31.5.und 5.6.2012)
#* Hashing und Hashfunktionen
* Implementation assoziativer Arrays mit Bäumen
#* Implementation assoziativer Arrays als Hashtabelle mit linearer Verkettung bzw. mit offener Adressierung
* Hashing und Hashfunktionen
#* Anwendung des Hashing zur String-Suche: Rabin-Karp-Algorithmus
* Implementation assoziativer Arrays als Hashtabelle mit linearer Verkettung bzw. mit offener Adressierung
* Anwendung des Hashing zur String-Suche: Rabin-Karp-Algorithmus
<!------------->
<!------------->
# [[Iteration versus Rekursion]] (12.6.2012)
==[[Iteration versus Rekursion]]==
#* Typen der Rekursion und ihre Umwandlung in Iteration
(12.6.2012)
#* Auflösung rekursiver Formeln mittels Master-Methode und Substitutionsmethode
* Typen der Rekursion und ihre Umwandlung in Iteration
* Auflösung rekursiver Formeln mittels Master-Methode und Substitutionsmethode
<!------------->
<!------------->
# [[Generizität]] (14.6.2012)
==[[Generizität]]==
#* Abstrakte Datentypen, Typspezifikation
(14.6.2012)
#* Required Interface versus Offered Interface
* Abstrakte Datentypen, Typspezifikation
#* Adapter und Typattribute, Funktoren
* Required Interface versus Offered Interface
#* Beispiel: Algebraische Konzepte und Zahlendatentypen
* Adapter und Typattribute, Funktoren
#* Operator overloading in Python
* Beispiel: Algebraische Konzepte und Zahlendatentypen
* Operator overloading in Python
<!------------->
<!------------->
# [[Graphen und Graphenalgorithmen]] (19. bis 28.6.2012)
==[[Graphen und Graphenalgorithmen]]==
#* Einführung
(19. bis 28.6.2012)
#* Graphendatenstrukturen, Adjazenzlisten und Adjazenzmatrizen
* Einführung
#* Gerichtete und ungerichtete Graphen
* Graphendatenstrukturen, Adjazenzlisten und Adjazenzmatrizen
#* Vollständige Graphen
* Gerichtete und ungerichtete Graphen
#* Planare Graphen, duale Graphen
* Vollständige Graphen
#* Pfade, Zyklen
* Planare Graphen, duale Graphen
#* Tiefensuche und Breitensuche
* Pfade, Zyklen
#* Zusammenhang, Komponenten
* Tiefensuche und Breitensuche
#* Gewichtete Graphen
* Zusammenhang, Komponenten
#* Minimaler Spannbaum
* Gewichtete Graphen
#* Kürzeste Wege, Best-first search (Dijkstra)
* Minimaler Spannbaum
#* Most-Promising-first search (A*)
* Kürzeste Wege, Best-first search (Dijkstra)
#* Problem des Handlungsreisenden, exakte Algorithmen (erschöpfende Suche, Branch-and-Bound-Methode) und Approximationen
* Most-Promising-first search (A*)
#* Erfüllbarkeitsproblem, Darstellung des 2-SAT-Problems durch gerichtete Graphen, stark zusammenhängende Komponenten
* Problem des Handlungsreisenden, exakte Algorithmen (erschöpfende Suche, Branch-and-Bound-Methode) und Approximationen
* Erfüllbarkeitsproblem, Darstellung des 2-SAT-Problems durch gerichtete Graphen, stark zusammenhängende Komponenten
<!------------->
<!------------->
<!---#* Repetition--->
<!--* Repetition-->
<!---#* Orthogonale Zerlegung des Problems--->
<!--* Orthogonale Zerlegung des Problems-->
<!---#* Hierarchische Zerlegung der Daten (Divide and Conquer)--->
<!--* Hierarchische Zerlegung der Daten (Divide and Conquer)-->
<!---#* Randomisierung--->
<!--* Randomisierung-->
<!---#* Optimierung, Zielfunktionen--->
<!--* Optimierung, Zielfunktionen-->
<!---#* Systematisierung von Algorithmen aus der bisherigen Vorlesung--->
<!--* Systematisierung von Algorithmen aus der bisherigen Vorlesung-->
<!------------->
<!------------->
<!---# [[Analytische Optimierung]] (25.6.2008)--->
<!--==[[Analytische Optimierung]]==
<!---#* Methode der kleinsten Quadrate--->
(25.6.2008)//-->
<!---#* Approximation von Geraden--->
<!--* Methode der kleinsten Quadrate-->
<!--* Approximation von Geraden-->
<!------------->
<!------------->
# [[Randomisierte Algorithmen]] (3. und 5.7.2012)
==[[Randomisierte Algorithmen]]==
#* Zufallszahlen, Zyklenlänge, Pitfalls
(3. und 5.7.2012)
#* Zufallszahlengeneratoren: linear congruential generator, Mersenne Twister
* Zufallszahlen, Zyklenlänge, Pitfalls
#* Randomisierte vs. deterministische Algorithmen
* Zufallszahlengeneratoren: linear congruential generator, Mersenne Twister
#* Las Vegas vs. Monte Carlo Algorithmen
* Randomisierte vs. deterministische Algorithmen
#* Beispiel für Las Vegas: Randomisiertes Quicksort
* Las Vegas vs. Monte Carlo Algorithmen
#* Beispiele für Monte Carlo: Randomisierte Lösung des k-SAT Problems  
* Beispiel für Las Vegas: Randomisiertes Quicksort
#* RANSAC-Algorithmus, Erfolgswahrscheinlichkeit, Vergleich mit analytischer Optimierung (Methode der kleinsten Quadrate)
* Beispiele für Monte Carlo: Randomisierte Lösung des k-SAT Problems  
* RANSAC-Algorithmus, Erfolgswahrscheinlichkeit, Vergleich mit analytischer Optimierung (Methode der kleinsten Quadrate)
<!------------->
<!------------->
# [[Greedy-Algorithmen und Dynamische Programmierung]] (10. und 12.7.2012)
==[[Greedy-Algorithmen und Dynamische Programmierung]]==
#* Prinzipien, Aufwandsreduktion in Entscheidungsbäumen
(10. und 12.7.2012)
#* bereits bekannte Algorithmen: minimale Spannbäume nach Kruskal, kürzeste Wege nach Dijkstra
* Prinzipien, Aufwandsreduktion in Entscheidungsbäumen
#* Beispiel: Interval Scheduling Problem und Weighted Interval Scheduling Problem
* bereits bekannte Algorithmen: minimale Spannbäume nach Kruskal, kürzeste Wege nach Dijkstra
#* Beweis der Optimalität beim Scheduling Problem: "greedy stays ahead"-Prinzip, Directed Acyclic Graph bei dynamischer Programmierung
* Beispiel: Interval Scheduling Problem und Weighted Interval Scheduling Problem
* Beweis der Optimalität beim Scheduling Problem: "greedy stays ahead"-Prinzip, Directed Acyclic Graph bei dynamischer Programmierung
<!------------->
<!------------->
# [[NP-Vollständigkeit]] (17. und 19.7.2012)
==[[NP-Vollständigkeit]]==
#* die Klassen P und NP
(17. und 19.7.2012)
#* NP-Vollständigkeit und Problemreduktion
* die Klassen P und NP
* NP-Vollständigkeit und Problemreduktion
<!------------->
<!------------->
# Reserve und/oder Wiederholung (24. und 26.7.2012)
==Reserve und/oder Wiederholung==
(24. und 26.7.2012)

Revision as of 01:14, 27 May 2012

Einführung

(17.4.2012)

  • Definition von Algorithmen und Datenstrukturen, Geschichte
  • Fundamentale Algorithmen: create, assign, copy, swap, compare etc.
  • Fundamentale Datenstrukturen: Zahlen, Container, Handles
  • Python-Grundlagen

Container

(19.4.2012)

  • Anforderungen von Algorithmen an Container
  • Einteilung der Container
  • Grundlegende Container: Array, verkettete Liste, Stack und Queue
  • Sequenzen und Intervalle (Ranges)

Sortieren

(24. und 26.4.2012)

  • Spezifikation des Sortierproblems
  • Selection Sort und Insertion Sort
  • Merge Sort
  • Quick Sort und seine Varianten
  • Vergleich der Anzahl der benötigten Schritte
  • Laufzeitmessung in Python

Korrektheit

(3. und 8.5.2012)

  • Definition von Korrektheit, Algorithmen-Spezifikation
  • Korrektheitsbeweise versus Testen
  • Vor- und Nachbedingungen, Invarianten, Programming by contract
  • Testen, Execution paths, Unit Tests in Python
  • Ausnahmen (exceptions) und Ausnahmebehandlung in Python

Effizienz

(10. und 15.5.2012)

  • Laufzeit und Optimierung: Innere Schleife, Caches, locality of reference
  • Laufzeit versus Komplexität
  • Landausymbole (O-Notation, <math>\Omega</math>-Notation, <math>\Theta</math>-Notation), Komplexitätsklassen
  • Bester, schlechtester, durchschnittlicher Fall
  • Amortisierte Komplexität

Suchen

(22. und 24.5.2012)

  • Lineare Suche
  • Binäre Suche in sortierten Arrays, Medianproblem
  • Suchbäume, balancierte Bäume
  • selbst-balancierende Bäume, Rotationen
  • Komplexität der Suche

Prioritätswarteschlangen

(29.5.2012)

  • Heap-Datenstruktur
  • Einfüge- und Löschoperationen
  • Heapsort
  • Komplexität des Heaps

Hashing und assoziative Arrays

(31.5.und 5.6.2012)

  • Implementation assoziativer Arrays mit Bäumen
  • Hashing und Hashfunktionen
  • Implementation assoziativer Arrays als Hashtabelle mit linearer Verkettung bzw. mit offener Adressierung
  • Anwendung des Hashing zur String-Suche: Rabin-Karp-Algorithmus

Iteration versus Rekursion

(12.6.2012)

  • Typen der Rekursion und ihre Umwandlung in Iteration
  • Auflösung rekursiver Formeln mittels Master-Methode und Substitutionsmethode

Generizität

(14.6.2012)

  • Abstrakte Datentypen, Typspezifikation
  • Required Interface versus Offered Interface
  • Adapter und Typattribute, Funktoren
  • Beispiel: Algebraische Konzepte und Zahlendatentypen
  • Operator overloading in Python

Graphen und Graphenalgorithmen

(19. bis 28.6.2012)

  • Einführung
  • Graphendatenstrukturen, Adjazenzlisten und Adjazenzmatrizen
  • Gerichtete und ungerichtete Graphen
  • Vollständige Graphen
  • Planare Graphen, duale Graphen
  • Pfade, Zyklen
  • Tiefensuche und Breitensuche
  • Zusammenhang, Komponenten
  • Gewichtete Graphen
  • Minimaler Spannbaum
  • Kürzeste Wege, Best-first search (Dijkstra)
  • Most-Promising-first search (A*)
  • Problem des Handlungsreisenden, exakte Algorithmen (erschöpfende Suche, Branch-and-Bound-Methode) und Approximationen
  • Erfüllbarkeitsproblem, Darstellung des 2-SAT-Problems durch gerichtete Graphen, stark zusammenhängende Komponenten

Randomisierte Algorithmen

(3. und 5.7.2012)

  • Zufallszahlen, Zyklenlänge, Pitfalls
  • Zufallszahlengeneratoren: linear congruential generator, Mersenne Twister
  • Randomisierte vs. deterministische Algorithmen
  • Las Vegas vs. Monte Carlo Algorithmen
  • Beispiel für Las Vegas: Randomisiertes Quicksort
  • Beispiele für Monte Carlo: Randomisierte Lösung des k-SAT Problems
  • RANSAC-Algorithmus, Erfolgswahrscheinlichkeit, Vergleich mit analytischer Optimierung (Methode der kleinsten Quadrate)

Greedy-Algorithmen und Dynamische Programmierung

(10. und 12.7.2012)

  • Prinzipien, Aufwandsreduktion in Entscheidungsbäumen
  • bereits bekannte Algorithmen: minimale Spannbäume nach Kruskal, kürzeste Wege nach Dijkstra
  • Beispiel: Interval Scheduling Problem und Weighted Interval Scheduling Problem
  • Beweis der Optimalität beim Scheduling Problem: "greedy stays ahead"-Prinzip, Directed Acyclic Graph bei dynamischer Programmierung

NP-Vollständigkeit

(17. und 19.7.2012)

  • die Klassen P und NP
  • NP-Vollständigkeit und Problemreduktion

Reserve und/oder Wiederholung

(24. und 26.7.2012)

Retrieved from "https://alda.iwr.uni-heidelberg.de/index.php?title=Gliederung_der_Vorlesung&oldid=5026"