Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

Link zu dieser Vergleichsansicht

Beide Seiten der vorigen Revision Vorhergehende Überarbeitung
en:lehre:ws1314:algorithmen-und-berechnungskomplexitaeti [2014/03/21 16:24]
127.0.0.1 Externe Bearbeitung
en:lehre:ws1314:algorithmen-und-berechnungskomplexitaeti [2014/03/31 12:42] (aktuell)
demir
Zeile 5: Zeile 5:
 ^Art ^Wann ^Wo ^Beginn ^LP ^Dozent^ ^Art ^Wann ^Wo ^Beginn ^LP ^Dozent^
 |V4 |Dienstag 12:30 -14:00 \\ Donnerstag 12:30 - 14:00 | AVZ III / HS 1 \\ AVZ III / HS 1  | 15. Oktober 2013 | 5,5 | Röglin| |V4 |Dienstag 12:30 -14:00 \\ Donnerstag 12:30 - 14:00 | AVZ III / HS 1 \\ AVZ III / HS 1  | 15. Oktober 2013 | 5,5 | Röglin|
-|Ü2 |s.u |s.u| 21. Oktober 2013 | 3,5 | Bruckschen, Brunsch, Loka, Omlor, Rösner, Schäfer, Seume| +|Ü2 |[[http://​www.i1.cs.uni-bonn.de/​de/​content/​ws-1314-algorithmen-und-berechnungskomplexit%C3%A4t-i#​uebungsgruppen|Termine]] || 21. Oktober 2013 | 3,5 | Bruckschen, Brunsch, Loka, Omlor, Rösner, Schäfer, Seume|
  
 +<color red>Die Ergebnisse der Nachklausur können nun in Basis eingesehen werden. Die Einsicht findet am 7. April zwischen 13:00 und 13:45 Uhr in Raum E.08 im LBH statt.</​color>​
 ===== Inhalt ===== ===== Inhalt =====
  
 In dieser Vorlesung werden wir uns mit dem Entwurf und der Analyse von Algorithmen beschäftigen. Ein Algorithmus ist eine Handlungsvorschrift zur Lösung eines Problems, die so präzise formuliert ist, dass sie von einem Computer ausgeführt werden kann. Algorithmen sind heute so allgegenwärtig,​ dass sie kaum wahrgenommen oder gewürdigt werden. Wie selbstverständlich nutzen wir Navigationsgeräte,​ um den besten Weg vom Start zum Ziel zu bestimmen, oder Suchmaschinen,​ um innerhalb kürzester Zeit riesengroße Datenmengen zu durchsuchen. Dass dies überhaupt möglich ist, liegt zum Teil an der immer besseren Hardware, zu einem viel größeren Teil liegt es aber an den cleveren Algorithmen,​ die für diese Anwendungen entwickelt wurden. In dieser Vorlesung werden wir Techniken zum Entwurf und zur Analyse von Algorithmen kennenlernen und diese nutzen, um effiziente Algorithmen für zahlreiche grundlegende Probleme zu entwerfen. In dieser Vorlesung werden wir uns mit dem Entwurf und der Analyse von Algorithmen beschäftigen. Ein Algorithmus ist eine Handlungsvorschrift zur Lösung eines Problems, die so präzise formuliert ist, dass sie von einem Computer ausgeführt werden kann. Algorithmen sind heute so allgegenwärtig,​ dass sie kaum wahrgenommen oder gewürdigt werden. Wie selbstverständlich nutzen wir Navigationsgeräte,​ um den besten Weg vom Start zum Ziel zu bestimmen, oder Suchmaschinen,​ um innerhalb kürzester Zeit riesengroße Datenmengen zu durchsuchen. Dass dies überhaupt möglich ist, liegt zum Teil an der immer besseren Hardware, zu einem viel größeren Teil liegt es aber an den cleveren Algorithmen,​ die für diese Anwendungen entwickelt wurden. In dieser Vorlesung werden wir Techniken zum Entwurf und zur Analyse von Algorithmen kennenlernen und diese nutzen, um effiziente Algorithmen für zahlreiche grundlegende Probleme zu entwerfen.
 +
 +^Datum ^Inhalt ^Literatur^
 +|15. Oktober| 1 Einleitung \\ 1.1 Grundbegriffe \\ 1.2 Ein erstes Beispiel: Insertionsort | [[Folien]] \\ [[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/​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/​WS2013/​AlgoI/​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]]|
 +|29. Oktober| 2.2 Greedy-Algorithmen \\ 2.2.1 Optimale Auswahl von Aufgaben \\ |[[http://​www.roeglin.org/​teaching/​WS2013/​AlgoI/​AlgoI.pdf|Skript]]|
 +|31. Oktober| 2.2.2 Rucksackproblem mit teilbaren Objekten |[[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/​WS2013/​AlgoI/​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]]|
 +|12. November| 3 Sortieren \\ 3.1 Quicksort \\ 3.2 Eigenschaften von Sortieralgorithmen |[[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/​WS2013/​AlgoI/​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]]|
 +|21. November| 4.2.1 AVL-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/​WS2013/​AlgoI/​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]]|
 +|3. Dezember| 4.3.1 Hashfunktionen \\ 4.3.2 Hashing mit verketteten Listen |[[http://​www.roeglin.org/​teaching/​WS2013/​AlgoI/​AlgoI.pdf|Skript]]|
 +|5. Dezember| 4.3.3 Geschlossenes Hashing |[[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/​WS2013/​AlgoI/​AlgoI.pdf|Skript]]|
 +|12. Dezember| 5.1.1 Tiefensuche (Fortsetzung) \\ 5.1.2 Breitensuche |[[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/​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/​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/​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/​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/​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/​WS2013/​AlgoI/​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]]|
 +|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]]|
 +|28. Januar| 6.1.2 Geometrische Interpretation (Fortsetzung) \\ 6.1.3 Algebraische Interpretation |[[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/​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/​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/​WS2013/​AlgoI/​AlgoI.pdf|Skript]]|
 +
  
 ===== Übungen ===== ===== Übungen =====
 +
 +Für den Erhalt des Übungsscheins müssen insgesamt mindestens 50% der zu erreichenden Punkte bei den Übungsaufgaben erreicht werden und Lösungen von drei Aufgaben müssen im Laufe des Semesters erfolgreich in den Tutorien präsentiert werden. Eine Abgabe der Übungsaufgaben in Gruppen bis zu drei Studierenden ist möglich.
  
 ^ ^Wann ^Wo ^ Tutor^ ^ ^Wann ^Wo ^ Tutor^
-|1| Montag 8:15 - 9:45| AVZ III / A301| tba+|1| Montag 8:15 - 9:45| AVZ III / A301| Yvonne Omlor
-|2| Montag 12:15 - 13:45| AVZ III / A6c| tba+|2| Montag 12:15 - 13:45| AVZ III / A6c| Patrick Loka
-|3| Montag 12:15 - 13:45| AVZ III / A7a| tba+|3| Montag 12:15 - 13:45| AVZ III / A7a| Patrick Seume
-|4| Montag 12:15 - 13:45| AVZ III / A7b| tba+|4| Montag 12:15 - 13:45| AVZ III / A7b| Tobias Brunsch
-|5| Montag 14:15 - 15:45| AVZ III / A7a| tba+|5| Montag 14:15 - 15:45| AVZ III / A7a| Patrick Seume
-|6| Dienstag 8:15 - 9:45| AVZ III / A301| tba+|6| Dienstag 8:15 - 9:45| AVZ III / A301| Yvonne Omlor
-|7| Mittwoch 12:15 - 13:45| AVZ III / A301|tba+|7| Mittwoch 12:15 - 13:45| AVZ III / A301|Patrick Loka
-|8| Mittwoch 12:15 - 13:45| AVZ III / A7a| tba+|8| Mittwoch 12:15 - 13:45| AVZ III / A7a| Clemens Rösner
-|9| Donnerstag 8:15 - 9:45| AVZ III / A7a| tba+|9| Donnerstag 8:15 - 9:45| AVZ III / A7a| Philipp Bruckschen
-|10| Donnerstag 10:15 - 11:45|AVZ III / A301| tba+|10| Donnerstag 10:15 - 11:45|AVZ III / A301| Philipp Bruckschen
-|11| Freitag 10:15 - 11:45| AVZ III / A7a| tba+|11| Freitag 10:15 - 11:45| AVZ III / A7a| Sonja Schäfer
-|12| Freitag 12:15 - 13:45| AVZ III / A301| tba|+|12| Freitag 12:15 - 13:45| AVZ III / A301| Sonja Schäfer|
  
-Für den Erhalt des Übungsscheins müssen insgesamt mindestens 50% der zu erreichenden Punkte bei den Übungsaufgaben erreicht werden und Lösungen ​von drei Aufgaben müssen ​im Laufe des Semesters erfolgreich ​in den Tutorien präsentiert werdenEine Abgabe der Übungsaufgaben ​in Gruppen ​bis zu drei Studierenden ​ist möglich+  * [[http://​www.roeglin.org/​teaching/​WS2013/​AlgoI/​Blatt0.pdf|Präsenzblatt]] (Besprechung in KW 43, keine Abgabe) 
-----+  * [[http://​www.roeglin.org/​teaching/​WS2013/​AlgoI/​Blatt1.pdf|Übungsblatt 1]] (Besprechung in KW 44, Abgabe bis 22.10., 12:30 Uhr, im Briefkasten in der Römerstraße) \\ [[http://​www.roeglin.org/​teaching/​WS2013/​AlgoI/​Blatt1_Hinweise.pdf|Hinweise zur Verwendung ​von gnuplot]] 
 +  * [[http://​www.roeglin.org/​teaching/​WS2013/​AlgoI/​Blatt2.pdf|Übungsblatt 2]] (Besprechung in KW 45, Abgabe bis 29.10., 12:30 Uhr, im Briefkasten ​in der Römerstraße) 
 +  *[[http://​www.roeglin.org/​teaching/​WS2013/​AlgoI/​Blatt3.pdf|Übungsblatt 3]] (Besprechung in KW 46, Abgabe ​bis 05.11., 12:30 Uhr, im Briefkasten in der Römerstraße) 
 +  * [[http://​www.roeglin.org/​teaching/​WS2013/​AlgoI/​Blatt4.pdf|Übungsblatt 4]] (Besprechung ​in KW 47, Abgabe ​bis 12.11., 12:30 Uhr, im Briefkasten in der Römerstraße) 
 +  * [[http://​www.roeglin.org/​teaching/​WS2013/​AlgoI/​Blatt5.pdf|Übungsblatt 5]] (Besprechung in KW 48, Abgabe bis 19.11., 12:30 Uhr, im Briefkasten in der Römerstraße) 
 +  * [[http://​www.roeglin.org/​teaching/​WS2013/​AlgoI/​Blatt6.pdf|Übungsblatt 6]] (Besprechung in KW 49, Abgabe bis 26.11., 12:30 Uhr, im Briefkasten in der Römerstraße) 
 +  * [[http://​www.roeglin.org/​teaching/​WS2013/​AlgoI/​Blatt7.pdf|Übungsblatt 7]] (Besprechung in KW 50, Abgabe bis 03.12., 12:30 Uhr, im Briefkasten in der Römerstraße) 
 +  * [[http://​www.roeglin.org/​teaching/​WS2013/​AlgoI/​Blatt8.pdf|Übungsblatt 8]] (Besprechung in KW 51, Abgabe bis 10.12., 12:30 Uhr, im Briefkasten in der Römerstraße) \\ [[http://​www.roeglin.org/​teaching/​WS2013/​AlgoI/​Blatt8_Hinweise.pdf|Hinweise zum Dateiformat]] \\ [[http://​www.roeglin.org/​teaching/​WS2013/​AlgoI/​Ue8_A1a.txt|Ue8_A1a.txt]],​ [[http://​www.roeglin.org/​teaching/​WS2013/​AlgoI/​Ue8_A1b.txt|Ue8_A1b.txt]],​ [[http://​www.roeglin.org/​teaching/​WS2013/​AlgoI/​Ue8_sample.txt|Ue8_sample.txt]],​ [[http://​www.roeglin.org/​teaching/​WS2013/​AlgoI/​Ue8_exercise.txt|Ue8_exercise.txt]] 
 +  * [[http://​www.roeglin.org/​teaching/​WS2013/​AlgoI/​Blatt9.pdf|Übungsblatt 9]] (Besprechung in KW 52, Abgabe bis 17.12., 12:30 Uhr, im Briefkasten in der Römerstraße) \\ [[http://​www.roeglin.org/​teaching/​WS2013/​AlgoI/​Blatt9_Hinweise.pdf|Hinweise zum Dateiformat]] \\ [[http://​www.roeglin.org/​teaching/​WS2013/​AlgoI/​Ue9_small.txt|Ue9_small.txt]],​ [[http://​www.roeglin.org/​teaching/​WS2013/​AlgoI/​Ue9_medium.txt|Ue9_medium.txt]],​ [[http://​www.roeglin.org/​teaching/​WS2013/​AlgoI/​Ue9_large.txt|Ue9_large.txt]] 
 +  * [[http://​www.roeglin.org/​teaching/​WS2013/​AlgoI/​Blatt10.pdf|Übungsblatt 10]] (Besprechung in KW 3, Abgabe bis 07.01., 12:30 Uhr, im Briefkasten in der Römerstraße) \\ [[http://​www.roeglin.org/​teaching/​WS2013/​AlgoI/​Blatt10_Hinweise.pdf|Hinweise zum Dateiformat]] \\ [[http://​www.roeglin.org/​teaching/​WS2013/​AlgoI/​Ue10_small.txt|Ue10_small.txt]],​ [[http://​www.roeglin.org/​teaching/​WS2013/​AlgoI/​Ue10_medium.txt|Ue10_medium.txt]],​ [[http://​www.roeglin.org/​teaching/​WS2013/​AlgoI/​Ue10_large.txt|Ue10_large.txt]] 
 +  * [[http://​www.roeglin.org/​teaching/​WS2013/​AlgoI/​Blatt11.pdf|Übungsblatt 11]] (Besprechung in KW 4, Abgabe bis 14.01., 12:30 Uhr, im Briefkasten in der Römerstraße) \\ [[http://​www.roeglin.org/​teaching/​WS2013/​AlgoI/​Blatt11_Hinweise.pdf|Hinweise zum Dateiformat]] \\ [[http://​www.roeglin.org/​teaching/​WS2013/​AlgoI/​Ue11_small.txt|Ue11_small.txt]],​ [[http://​www.roeglin.org/​teaching/​WS2013/​AlgoI/​Ue10_medium.txt|Ue11_medium.txt]],​ [[http://​www.roeglin.org/​teaching/​WS2013/​AlgoI/​Ue11_large.txt|Ue11_large.txt]] 
 +  * [[http://​www.roeglin.org/​teaching/​WS2013/​AlgoI/​Blatt12.pdf|Übungsblatt 12]] (Besprechung in KW 5, Abgabe bis 21.01., 12:30 Uhr, im Briefkasten in der Römerstraße) \\ [[http://​www.roeglin.org/​teaching/​WS2013/​AlgoI/​Blatt12_Hinweise.pdf|Hinweise zum Dateiformat]] \\ [[http://​www.roeglin.org/​teaching/​WS2013/​AlgoI/​Ue12a.txt|Ue12a.txt]],​ [[http://​www.roeglin.org/​teaching/​WS2013/​AlgoI/​Ue12b.txt|Ue12b.txt]],​ [[http://​www.roeglin.org/​teaching/​WS2013/​AlgoI/​Ue12c.txt|Ue12c.txt]]  
 +  * [[http://​www.roeglin.org/​teaching/​WS2013/​AlgoI/​Blatt13.pdf|Übungsblatt 13]] (Besprechung in KW 6, Abgabe bis 28.01., 12:30 Uhr, im Briefkasten in der Römerstraße) \\ [[http://​www.roeglin.org/​teaching/​WS2013/​AlgoI/​Blatt13_Hinweise.pdf|Hinweise zum Dateiformat]] \\ [[http://​www.roeglin.org/​teaching/​WS2013/​AlgoI/​Ue13.txt|Ue13.txt]] 
 + 
 +=== Anmeldung ​zu den Übungen: === 
 + 
 +Die Anmeldung zu den Übungsgruppen erfolgt über das Tutorienvergabesystem ([[https://​puma.cs.uni-bonn.de/​|TVS]]). Eine einmalige Registrierung ​ist vom Netz der Universität Bonn aus erforderlich. Anschließend können Sie von überall auf das TVS zugreifen und bis einschließlich Freitag, den 18. Oktober, Ihre Wunschtermine angeben
 +===== Klausuren ===== 
 + 
 +Die Klausur findet am 18.2.2014 um 9 Uhr im Hörsaal X im Uni-Hauptgebäude statt. 
 +Die Nachklausur findet am 20.3.2014 um 9 Uhr im Hörsaal X im Uni-Hauptgebäude statt. 
 +Zur Vorbereitung auf die Klausur haben wir eine [[http://​www.roeglin.org/​teaching/​WS2013/​AlgoI/​Probeklausur.pdf|Probeklausur]] online gestellt. 
 + 
 +Nachfolgend finden Sie den Notenspiegel der Klausur. 
 + 
 +{{:​lehre:​ws1314:​klausur_notenspiegel.png?​nolink|}}
 ===== 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 Vorlesung basiert in wesentlichen Teilen auf der folgenden Literatur: ​  Die Vorlesung basiert in wesentlichen Teilen auf der folgenden Literatur: ​
en/lehre/ws1314/algorithmen-und-berechnungskomplexitaeti.txt · Zuletzt geändert: 2014/03/31 12:42 von demir

Benutzer-Werkzeuge