Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen gezeigt.

Link zu dieser Vergleichsansicht

Beide Seiten der vorigen Revision Vorhergehende Überarbeitung
lehre:ws1314:algorithmen-und-berechnungskomplexitaeti [2014/04/11 01:05]
demir [Inhalt]
lehre:ws1314:algorithmen-und-berechnungskomplexitaeti [2017/04/17 18:04] (aktuell)
roeglin
Zeile 12: Zeile 12:
  
 ^Datum ^Inhalt ^Literatur^ ^Datum ^Inhalt ^Literatur^
-|15. Oktober| 1 Einleitung \\ 1.1 Grundbegriffe \\ 1.2 Ein erstes Beispiel: Insertionsort | [[http://​www.roeglin.org/​teaching/​WS2013/​AlgoI/​Folien.pdf|Folien]] \\ [[http://​www.roeglin.org/​teaching/​WS2013/​AlgoI/​AlgoI.pdf|Skript]]| +|15. Oktober| 1 Einleitung \\ 1.1 Grundbegriffe \\ 1.2 Ein erstes Beispiel: Insertionsort | [[http://​www.roeglin.org/​teaching/​WS2013/​AlgoI/​Folien.pdf|Folien]] \\ [[http://​www.roeglin.org/​teaching/​Skripte/​AlgoI.pdf|Skript]]| 
-|17. Oktober| 1.2 Ein erstes Beispiel: Insertionsort (Fortsetzung) \\ 1.3 Registermaschinen \\ 1.4 Größenordnungen| [[http://​www.roeglin.org/​teaching/​WS2013/​AlgoI/​AlgoI.pdf|Skript]]| +|17. Oktober| 1.2 Ein erstes Beispiel: Insertionsort (Fortsetzung) \\ 1.3 Registermaschinen \\ 1.4 Größenordnungen| [[http://​www.roeglin.org/​teaching/​Skripte/​AlgoI.pdf|Skript]]| 
-|22. Oktober| 2 Methoden zum Entwurf von Algorithmen \\ 2.1 Divide-and-Conquer \\ 2.1.1 Mergesort \\ |[[http://​www.roeglin.org/​teaching/​WS2013/​AlgoI/​AlgoI.pdf|Skript]]| +|22. Oktober| 2 Methoden zum Entwurf von Algorithmen \\ 2.1 Divide-and-Conquer \\ 2.1.1 Mergesort \\ |[[http://​www.roeglin.org/​teaching/​Skripte/​AlgoI.pdf|Skript]]| 
-|24. Oktober| 2.1.2 Strassen-Algorithmus \\ 2.1.3 Lösen von Rekursionsgleichungen |[[http://​www.roeglin.org/​teaching/​WS2013/​AlgoI/​AlgoI.pdf|Skript]]| +|24. Oktober| 2.1.2 Strassen-Algorithmus \\ 2.1.3 Lösen von Rekursionsgleichungen |[[http://​www.roeglin.org/​teaching/​Skripte/​AlgoI.pdf|Skript]]| 
-|29. Oktober| 2.2 Greedy-Algorithmen \\ 2.2.1 Optimale Auswahl von Aufgaben \\ |[[http://​www.roeglin.org/​teaching/​WS2013/​AlgoI/​AlgoI.pdf|Skript]]| +|29. Oktober| 2.2 Greedy-Algorithmen \\ 2.2.1 Optimale Auswahl von Aufgaben \\ |[[http://​www.roeglin.org/​teaching/​Skripte/​AlgoI.pdf|Skript]]| 
-|31. Oktober| 2.2.2 Rucksackproblem mit teilbaren Objekten |[[http://​www.roeglin.org/​teaching/​WS2013/​AlgoI/​AlgoI.pdf|Skript]]| +|31. Oktober| 2.2.2 Rucksackproblem mit teilbaren Objekten |[[http://​www.roeglin.org/​teaching/​Skripte/​AlgoI.pdf|Skript]]| 
-|5. November| 2.2.2 Rucksackproblem mit teilbaren Objekten (Fortsetzung) \\ 2.3 Dynamische Programmierung \\ 2.3.1 Berechnung optimaler Zuschnitte| [[http://​www.roeglin.org/​teaching/​WS2013/​AlgoI/​AlgoI.pdf|Skript]]| +|5. November| 2.2.2 Rucksackproblem mit teilbaren Objekten (Fortsetzung) \\ 2.3 Dynamische Programmierung \\ 2.3.1 Berechnung optimaler Zuschnitte| [[http://​www.roeglin.org/​teaching/​Skripte/​AlgoI.pdf|Skript]]| 
-|7. November| 2.3.1 Berechnung optimaler Zuschnitte (Fortsetzung) \\ 2.3.2 Rucksackproblem |[[http://​www.roeglin.org/​teaching/​WS2013/​AlgoI/​AlgoI.pdf|Skript]]| +|7. November| 2.3.1 Berechnung optimaler Zuschnitte (Fortsetzung) \\ 2.3.2 Rucksackproblem |[[http://​www.roeglin.org/​teaching/​Skripte/​AlgoI.pdf|Skript]]| 
-|12. November| 3 Sortieren \\ 3.1 Quicksort \\ 3.2 Eigenschaften von Sortieralgorithmen |[[http://​www.roeglin.org/​teaching/​WS2013/​AlgoI/​AlgoI.pdf|Skript]]| +|12. November| 3 Sortieren \\ 3.1 Quicksort \\ 3.2 Eigenschaften von Sortieralgorithmen |[[http://​www.roeglin.org/​teaching/​Skripte/​AlgoI.pdf|Skript]]| 
-|14. November| 3.3 Untere Schranke für die Laufzeit vergleichsbasierter Sortieralgorithmen \\ 3.4 Sortieren in Linearzeit|[[http://​www.roeglin.org/​teaching/​WS2013/​AlgoI/​AlgoI.pdf|Skript]]| +|14. November| 3.3 Untere Schranke für die Laufzeit vergleichsbasierter Sortieralgorithmen \\ 3.4 Sortieren in Linearzeit|[[http://​www.roeglin.org/​teaching/​Skripte/​AlgoI.pdf|Skript]]| 
-|19. November| 4 Dynamische Mengen \\ 4.1 Felder und Listen \\ 4.2 Suchbäume |[[http://​www.roeglin.org/​teaching/​WS2013/​AlgoI/​AlgoI.pdf|Skript]]| +|19. November| 4 Dynamische Mengen \\ 4.1 Felder und Listen \\ 4.2 Suchbäume |[[http://​www.roeglin.org/​teaching/​Skripte/​AlgoI.pdf|Skript]]| 
-|21. November| 4.2.1 AVL-Bäume |[[http://​www.roeglin.org/​teaching/​WS2013/​AlgoI/​AlgoI.pdf|Skript]]| +|21. November| 4.2.1 AVL-Bäume |[[http://​www.roeglin.org/​teaching/​Skripte/​AlgoI.pdf|Skript]]| 
-|26. November| 4.2.1 AVL-Bäume (Fortsetzung) \\ 4.2.2 B-Bäume |[[http://​www.roeglin.org/​teaching/​WS2013/​AlgoI/​AlgoI.pdf|Skript]]| +|26. November| 4.2.1 AVL-Bäume (Fortsetzung) \\ 4.2.2 B-Bäume |[[http://​www.roeglin.org/​teaching/​Skripte/​AlgoI.pdf|Skript]]| 
-|28. November| 4.2.2 B-Bäume (Fortsetzung) \\ 4.3 Hashing |[[http://​www.roeglin.org/​teaching/​WS2013/​AlgoI/​AlgoI.pdf|Skript]]| +|28. November| 4.2.2 B-Bäume (Fortsetzung) \\ 4.3 Hashing |[[http://​www.roeglin.org/​teaching/​Skripte/​AlgoI.pdf|Skript]]| 
-|3. Dezember| 4.3.1 Hashfunktionen \\ 4.3.2 Hashing mit verketteten Listen |[[http://​www.roeglin.org/​teaching/​WS2013/​AlgoI/​AlgoI.pdf|Skript]]| +|3. Dezember| 4.3.1 Hashfunktionen \\ 4.3.2 Hashing mit verketteten Listen |[[http://​www.roeglin.org/​teaching/​Skripte/​AlgoI.pdf|Skript]]| 
-|5. Dezember| 4.3.3 Geschlossenes Hashing |[[http://​www.roeglin.org/​teaching/​WS2013/​AlgoI/​AlgoI.pdf|Skript]]| +|5. Dezember| 4.3.3 Geschlossenes Hashing |[[http://​www.roeglin.org/​teaching/​Skripte/​AlgoI.pdf|Skript]]| 
-|10. Dezember| 4.3.3 Geschlossenes Hashing (Fortsetzung) \\ 5 Graphenalgorithmen \\ 5.1 Tiefen- und Breitensuche \\ 5.1.1 Tiefensuche |[[http://​www.roeglin.org/​teaching/​WS2013/​AlgoI/​AlgoI.pdf|Skript]]| +|10. Dezember| 4.3.3 Geschlossenes Hashing (Fortsetzung) \\ 5 Graphenalgorithmen \\ 5.1 Tiefen- und Breitensuche \\ 5.1.1 Tiefensuche |[[http://​www.roeglin.org/​teaching/​Skripte/​AlgoI.pdf|Skript]]| 
-|12. Dezember| 5.1.1 Tiefensuche (Fortsetzung) \\ 5.1.2 Breitensuche |[[http://​www.roeglin.org/​teaching/​WS2013/​AlgoI/​AlgoI.pdf|Skript]]| +|12. Dezember| 5.1.1 Tiefensuche (Fortsetzung) \\ 5.1.2 Breitensuche |[[http://​www.roeglin.org/​teaching/​Skripte/​AlgoI.pdf|Skript]]| 
-|17. Dezember| 5.1.2 Breitensuche (Fortsetzung) \\ 5.2 Minimale Spannbäume \\ 5.2.1 Union-Find-Datenstrukturen |[[http://​www.roeglin.org/​teaching/​WS2013/​AlgoI/​AlgoI.pdf|Skript]]| +|17. Dezember| 5.1.2 Breitensuche (Fortsetzung) \\ 5.2 Minimale Spannbäume \\ 5.2.1 Union-Find-Datenstrukturen |[[http://​www.roeglin.org/​teaching/​Skripte/​AlgoI.pdf|Skript]]| 
-|19. Dezember| 5.2.1 Union-Find-Datenstrukturen (Fortsetzung) \\ 5.2.2 Algorithmus von Kruskal |[[http://​www.roeglin.org/​teaching/​WS2013/​AlgoI/​AlgoI.pdf|Skript]]| +|19. Dezember| 5.2.1 Union-Find-Datenstrukturen (Fortsetzung) \\ 5.2.2 Algorithmus von Kruskal |[[http://​www.roeglin.org/​teaching/​Skripte/​AlgoI.pdf|Skript]]| 
-|7. Januar| 5.3 Kürzeste Wege \\ 5.3.1 Grundlegende Eigenschaften von kürzesten Wegen \\ 5.3.2 Single-Source Shortest Path Problem |[[http://​www.roeglin.org/​teaching/​WS2013/​AlgoI/​AlgoI.pdf|Skript]]| +|7. Januar| 5.3 Kürzeste Wege \\ 5.3.1 Grundlegende Eigenschaften von kürzesten Wegen \\ 5.3.2 Single-Source Shortest Path Problem |[[http://​www.roeglin.org/​teaching/​Skripte/​AlgoI.pdf|Skript]]| 
-|9. Januar| 5.3.2 Single-Source Shortest Path Problem (Fortsetzung) \\ 5.3.3 All-Pairs Shortest Path Problem |[[http://​www.roeglin.org/​teaching/​WS2013/​AlgoI/​AlgoI.pdf|Skript]]| +|9. Januar| 5.3.2 Single-Source Shortest Path Problem (Fortsetzung) \\ 5.3.3 All-Pairs Shortest Path Problem |[[http://​www.roeglin.org/​teaching/​Skripte/​AlgoI.pdf|Skript]]| 
-|14. Januar| 5.4 Flussprobleme \\ 5.4.1 Anwendungsbeispiele \\ 5.4.2 Algorithmus von Ford und Fulkerson |[[http://​www.roeglin.org/​teaching/​WS2013/​AlgoI/​AlgoI.pdf|Skript]]|  +|14. Januar| 5.4 Flussprobleme \\ 5.4.1 Anwendungsbeispiele \\ 5.4.2 Algorithmus von Ford und Fulkerson |[[http://​www.roeglin.org/​teaching/​Skripte/​AlgoI.pdf|Skript]]|  
-|16. Januar| 5.4.2 Algorithmus von Ford und Fulkerson (Fortsetzung) \\ 5.4.3 Algorithmus von Edmonds und Karp |[[http://​www.roeglin.org/​teaching/​WS2013/​AlgoI/​AlgoI.pdf|Skript]]| +|16. Januar| 5.4.2 Algorithmus von Ford und Fulkerson (Fortsetzung) \\ 5.4.3 Algorithmus von Edmonds und Karp |[[http://​www.roeglin.org/​teaching/​Skripte/​AlgoI.pdf|Skript]]| 
-|21. Januar| 5.4.3 Algorithmus von Edmonds und Karp (Fortsetzung) \\ 6 Lineare Programmierung |[[http://​www.roeglin.org/​teaching/​WS2013/​AlgoI/​AlgoI.pdf|Skript]]| +|21. Januar| 5.4.3 Algorithmus von Edmonds und Karp (Fortsetzung) \\ 6 Lineare Programmierung |[[http://​www.roeglin.org/​teaching/​Skripte/​AlgoI.pdf|Skript]]| 
-|23. Januar| 6.1 Grundlagen \\ 6.1.1 Kanonische Form und Gleichungsform \\ 6.1.2 Geometrische Interpretation |[[http://​www.roeglin.org/​teaching/​WS2013/​AlgoI/​AlgoI.pdf|Skript]]| +|23. Januar| 6.1 Grundlagen \\ 6.1.1 Kanonische Form und Gleichungsform \\ 6.1.2 Geometrische Interpretation |[[http://​www.roeglin.org/​teaching/​Skripte/​AlgoI.pdf|Skript]]| 
-|28. Januar| 6.1.2 Geometrische Interpretation (Fortsetzung) \\ 6.1.3 Algebraische Interpretation |[[http://​www.roeglin.org/​teaching/​WS2013/​AlgoI/​AlgoI.pdf|Skript]]| +|28. Januar| 6.1.2 Geometrische Interpretation (Fortsetzung) \\ 6.1.3 Algebraische Interpretation |[[http://​www.roeglin.org/​teaching/​Skripte/​AlgoI.pdf|Skript]]| 
-|30. Januar| 6.2 Simplex-Algorithmus \\ 6.2.1 Formale Beschreibung \\ 6.2.2 Berechnung der initialen Basislösung \\ 6.2.3 Laufzeit \\ 6.3 Komplexität von linearer Programmierung |[[http://​www.roeglin.org/​teaching/​WS2013/​AlgoI/​AlgoI.pdf|Skript]]| +|30. Januar| 6.2 Simplex-Algorithmus \\ 6.2.1 Formale Beschreibung \\ 6.2.2 Berechnung der initialen Basislösung \\ 6.2.3 Laufzeit \\ 6.3 Komplexität von linearer Programmierung |[[http://​www.roeglin.org/​teaching/​Skripte/​AlgoI.pdf|Skript]]| 
-|4. Februar| 7 Kontextfreie Sprachen \\ 7.1 Sprachen und Grammatiken \\ 7.2 Chomsky-Normalform und der Cocke-Younger-Kasami-Algorithmus |[[http://​www.roeglin.org/​teaching/​WS2013/​AlgoI/​AlgoI.pdf|Skript]]| +|4. Februar| 7 Kontextfreie Sprachen \\ 7.1 Sprachen und Grammatiken \\ 7.2 Chomsky-Normalform und der Cocke-Younger-Kasami-Algorithmus |[[http://​www.roeglin.org/​teaching/​Skripte/​AlgoI.pdf|Skript]]| 
-|6. Februar| 7.2 Chomsky-Normalform und der Cocke-Younger-Kasami-Algorithmus (Fortsetzung) \\ 7.3 Pumping-Lemma für kontextfreie Sprachen |[[http://​www.roeglin.org/​teaching/​WS2013/​AlgoI/​AlgoI.pdf|Skript]]|+|6. Februar| 7.2 Chomsky-Normalform und der Cocke-Younger-Kasami-Algorithmus (Fortsetzung) \\ 7.3 Pumping-Lemma für kontextfreie Sprachen |[[http://​www.roeglin.org/​teaching/​Skripte/​AlgoI.pdf|Skript]]|
  
  
Zeile 87: Zeile 87:
  
 ===== Literatur ===== ===== Literatur =====
- Die Inhalte der Vorlesung finden sich in diesem [[http://​www.roeglin.org/​teaching/​WS2013/​AlgoI/​AlgoI.pdf|Skript]],​ das während des Semesters kontinuierlich erweitert wird.+ Die Inhalte der Vorlesung finden sich in diesem [[http://​www.roeglin.org/​teaching/​Skripte/​AlgoI.pdf|Skript]],​ das während des Semesters kontinuierlich erweitert wird.
  
  Die Vorlesung basiert in wesentlichen Teilen auf der folgenden Literatur: ​  Die Vorlesung basiert in wesentlichen Teilen auf der folgenden Literatur: ​
lehre/ws1314/algorithmen-und-berechnungskomplexitaeti.txt · Zuletzt geändert: 2017/04/17 18:04 von roeglin

Benutzer-Werkzeuge