Main Page: Difference between revisions
From Alda
Jump to navigationJump to search
| (12 intermediate revisions by the same user not shown) | |||
| Line 2: | Line 2: | ||
Dr. Ullrich Köthe, Universität Heidelberg, Sommersemester | apl. Prof. Dr. Ullrich Köthe, Universität Heidelberg, Sommersemester 2020 | ||
Die Vorlesung findet '''dienstags''' und '''donnerstags''' | Die Vorlesung findet '''dienstags''' um 14:15 Uhr und '''donnerstags''' um 16:15 Uhr online auf Discord und Twitch statt. Die Links haben in Müsli angemeldete Teilnehmer per Email erhalten. | ||
=== Klausur und Nachprüfung === | === Klausur und Nachprüfung === | ||
Der Termin der '''Abschlussklausur''' steht noch nicht fest. | |||
Die ''' | <!--Die '''Klausur 1''' findet am Donnerstag, dem 20.7.2017 von 13:00 bis 14:30 Uhr im Großen Hörsaal Chemie (INF 252) statt. <b>Bitte melden Sie sich in [https://muesli.mathi.uni-heidelberg.de/lecture/view/707 MÜSLI] für die Klausur an.</b> Zur Klausur wird zugelassen, wer mindestens 50% der Übungspunkte erreicht und eine Aufgabe in der Übungsgruppe vorgerechnet hat. (Hinweis: Sie benötigen einen Lichtbildausweis, um sich bei der Klausur zu indentifizieren!)--> | ||
--> | |||
<!--- | <!--- | ||
* '''[[Media:2014-Klausur-1.pdf|Ergebnis der Klausur 1 vom 29.7.2014]]''' (anonymisiert) | |||
Die '''Klausur 2''' findet am Mittwoch, dem 8.10.2014 von 10:00 bis 12:00 Uhr im Seminarraum des [http://hci.iwr.uni-heidelberg.de/contact.php HCI, Speyerer Str. 6], statt. Teilnahmeberechtigt sind diejenigen, die Klausur 1 nicht bestanden haben (bitte unbedingt per Email <b>anmelden!</b>) sowie diejenigen, die mich vorab informiert haben (Sie brauchen sich nicht nochmals anzumelden). | |||
* '''[[Media:2014-Klausur-2.pdf|Ergebnis der Klausur 2 vom 8.10.2014]]''' (anonymisiert) | |||
* '''[[Media:Prüfungsteilnehmer.pdf|Liste der Studenten]], die sich verbindlich zur Klausur angemeldet und die notwendige Übungspunktzahl erreicht haben.''' | * '''[[Media:Prüfungsteilnehmer.pdf|Liste der Studenten]], die sich verbindlich zur Klausur angemeldet und die notwendige Übungspunktzahl erreicht haben.''' | ||
* '''Scheine''' können ab 1.9.2008 im Sekretariat Informatik bei Frau Tenschert abgeholt werden. | * '''Scheine''' können ab 1.9.2008 im Sekretariat Informatik bei Frau Tenschert abgeholt werden. | ||
| Line 20: | Line 19: | ||
* '''[[Media:Ergebnis-Klausur-01-10-2008.pdf|Ergebnis der Wiederholungsklausur vom 1.10.2008]]''' (anonymisiert) | * '''[[Media:Ergebnis-Klausur-01-10-2008.pdf|Ergebnis der Wiederholungsklausur vom 1.10.2008]]''' (anonymisiert) | ||
---> | ---> | ||
<!------- | |||
=== Leistungsnachweise === | === Leistungsnachweise === | ||
Für alle Leistungsnachweise ist die erfolgreiche Teilnahme an den Übungen erforderlich. Für Leistungspunkte bzw. den Klausurschein muss außerdem die schriftliche Prüfung bestanden werden. Einzelheiten werden noch bekanntgegeben. | Für alle Leistungsnachweise ist die erfolgreiche Teilnahme an den Übungen erforderlich. Für Leistungspunkte bzw. den Klausurschein muss außerdem die schriftliche Prüfung bestanden werden. Einzelheiten werden noch bekanntgegeben. | ||
Im einzelnen können erworben werden: | Im einzelnen können erworben werden: | ||
* ein unbenoteter Übungsschein, falls jemand nicht an der Klausur teilnimmt bzw. die Klausur nicht bestanden wurde. | * ein unbenoteter Übungsschein, falls jemand nicht an der Klausur teilnimmt bzw. die Klausur nicht bestanden wurde. | ||
| Line 34: | Line 32: | ||
=== Übungsbetrieb === | === Übungsbetrieb === | ||
<!--- | |||
* Wegen der großen Nachfrage haben wir zusätzliche Tutoren/Korrektoren eingestellt und die Gruppengröße auf 32 Teilnehmer erhöht. Bitte melden Sie sich im [https://www.mathi.uni-heidelberg.de/muesli/lecture/view/355 MÜSLI] an. | * Wegen der großen Nachfrage haben wir zusätzliche Tutoren/Korrektoren eingestellt und die Gruppengröße auf 32 Teilnehmer erhöht. Bitte melden Sie sich im [https://www.mathi.uni-heidelberg.de/muesli/lecture/view/355 MÜSLI] an. | ||
* Termine und Räume: | * Termine und Räume: | ||
| Line 42: | Line 41: | ||
** Mi 14:00 - 16:00 Uhr, INF 294, R-113 (Tutor: Axel Wagner, Korrektor: Philipp Schubert [mailto:phil.jo.schubert@gmail.com phil.jo.schubert AT gmail.com]) | ** Mi 14:00 - 16:00 Uhr, INF 294, R-113 (Tutor: Axel Wagner, Korrektor: Philipp Schubert [mailto:phil.jo.schubert@gmail.com phil.jo.schubert AT gmail.com]) | ||
** Mi 16:00 - 18:00 Uhr, INF 294, R-113 (Tutor und Korrektor: Axel Wagner: [mailto:axel.wagner@stud.uni-heidelberg.de axel.wagner AT stud.uni-heidelberg.de]) | ** Mi 16:00 - 18:00 Uhr, INF 294, R-113 (Tutor und Korrektor: Axel Wagner: [mailto:axel.wagner@stud.uni-heidelberg.de axel.wagner AT stud.uni-heidelberg.de]) | ||
* Die Übungsgruppen werden über <b>[https:// | ---> | ||
* Die Übungsgruppen werden über <b>[https://muesli.mathi.uni-heidelberg.de/lecture/view/1171 MÜSLI]</b> verwaltet. | |||
* Übungsblätter werden auf [https://moodle.uni-heidelberg.de/course/view.php?id=2239 Moodle] veröffentlicht. | |||
<!------ | <!------ | ||
* [[Media:Punktestand.pdf|aktueller Punktestand]] (PDF, anonymisiert, so aktuell, wie von den Tutoren an mich übermittelt -- UK) | * [[Media:Punktestand.pdf|aktueller Punktestand]] (PDF, anonymisiert, so aktuell, wie von den Tutoren an mich übermittelt -- UK) | ||
* <b>[[Main Page#Übungsaufgaben|Übungsaufgaben]]</b> (Übungszettel mit Abgabetermin, Musterlösungen). Lösungen bitte per Email an den jeweiligen Korrektor. | * <b>[[Main Page#Übungsaufgaben|Übungsaufgaben]]</b> (Übungszettel mit Abgabetermin, Musterlösungen). Lösungen bitte per Email an den jeweiligen Korrektor. | ||
* Zur Klausur wird zugelassen, wer mindestens 50% der Übungspunkte erreicht. Außerdem muss jeder Teilnehmer eine Lösung (bzw. einen Teil davon) in der Übungsgruppe vorrechnen. | * Zur Klausur wird zugelassen, wer mindestens 50% der Übungspunkte erreicht. Außerdem muss jeder Teilnehmer eine Lösung (bzw. einen Teil davon) in der Übungsgruppe vorrechnen. | ||
| Line 53: | Line 53: | ||
Zur Hilfe bei der Prüfungsvorbereitung hat Andreas Fay [http://de.neemoy.com/quizcategories/31/ Quizfragen] erstellt. | Zur Hilfe bei der Prüfungsvorbereitung hat Andreas Fay [http://de.neemoy.com/quizcategories/31/ Quizfragen] erstellt. | ||
-------> | |||
=== Literatur === | === Literatur === | ||
| Line 62: | Line 62: | ||
=== Gliederung der Vorlesung === | === Gliederung der Vorlesung === | ||
(Termine werden nach und nach aktualisiert) | |||
<!-------------> | <!-------------> | ||
# [[Einführung]] ( | # [[Einführung]] (21. und 23.4.2020) | ||
#* Definition von Algorithmen und Datenstrukturen, Geschichte | #* Definition von Algorithmen und Datenstrukturen, Geschichte | ||
#* Fundamentale Algorithmen: | #* Fundamentale Algorithmen: Konstruktoren, Kopierfunktionen, swap. | ||
#* Fundamentale Datenstrukturen: Zahlen, Container, Handles | #* Fundamentale Datenstrukturen: Zahlen, Container, Handles | ||
#* Python-Grundlagen | #* Python-Grundlagen | ||
<!-------------> | <!-------------> | ||
# [[Container]] ( | # [[Container]] (28.4.2020) | ||
#* | #* Abstrakte Datentypen und algebraische Spezifikation | ||
#* Grundlegende Container: Array, Stack, Queue, assoziatives Array | |||
#* Grundlegende Container: Array, | |||
<!-------------> | <!-------------> | ||
# [[Sortieren]] ( | # [[Sortieren]] (some day in 2020) | ||
#* 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 | ||
#* | #* Anzahl der benötigten Vergleiche | ||
<!-------------> | <!-------------> | ||
# [[Korrektheit]] (29.4. und 6.5.2014) | # [[Korrektheit]] (29.4. und 6.5.2014 -- ab hier altes Datum) | ||
#* Definition von Korrektheit, Algorithmen-Spezifikation | #* Definition von Korrektheit, Algorithmen-Spezifikation | ||
#* Korrektheitsbeweise versus Testen | #* Korrektheitsbeweise versus Testen | ||
| Line 138: | Line 136: | ||
#* Operator overloading in Python | #* Operator overloading in Python | ||
<!-------------> | <!-------------> | ||
# [[Graphen und Graphenalgorithmen]] (24.6. bis | # [[Graphen und Graphenalgorithmen]] (24.6. bis 10.7.2014) | ||
#* Einführung | #* Einführung | ||
#* Graphendatenstrukturen, Adjazenzlisten und Adjazenzmatrizen | #* Graphendatenstrukturen, Adjazenzlisten und Adjazenzmatrizen | ||
| Line 188: | Line 186: | ||
== Übungsaufgaben == | == Übungsaufgaben == | ||
(im PDF Format). Die Abgabe erfolgt am angegebenen Tag bis 14:00 Uhr per Email an den jeweiligen Übungsgruppenleiter. Bei verspäteter Abgabe bis zu drei Tagen werden noch 50% der erreichten Punkte angerechnet. Danach wird die Musterlösung freigeschaltet. | (im PDF Format). Die Abgabe erfolgt am angegebenen Tag bis 14:00 Uhr per Email an den jeweiligen Übungsgruppenleiter. Bei verspäteter Abgabe bis zu drei Tagen werden noch 50% der erreichten Punkte angerechnet. Danach wird die Musterlösung freigeschaltet. | ||
<i>Die Übungsaufgaben sind zur Zeit nicht freigeschaltet.</i> | |||
<!------ | |||
# [[Media:Uebung-1.pdf|Übung]] (Abgabe 29.4.2014) und [[Media:muster_blatt1.pdf|Musterlösung]] | # [[Media:Uebung-1.pdf|Übung]] (Abgabe 29.4.2014) und [[Media:muster_blatt1.pdf|Musterlösung]] | ||
#* Python-Tutorial | #* Python-Tutorial | ||
| Line 218: | Line 219: | ||
#* Absichtliche Konstruktion von Kollisionen für eine Hashfunktion | #* Absichtliche Konstruktion von Kollisionen für eine Hashfunktion | ||
#* Übungen zum Assoziativen Array und zum JSON-Format: Cocktail-Datenbank (Dazu benötigen Sie das File [http://hci.iwr.uni-heidelberg.de/Staff/ukoethe/download/cocktails.json cocktails.json]. Die Zeichenkodierung in diesem File ist UTF-8.) | #* Übungen zum Assoziativen Array und zum JSON-Format: Cocktail-Datenbank (Dazu benötigen Sie das File [http://hci.iwr.uni-heidelberg.de/Staff/ukoethe/download/cocktails.json cocktails.json]. Die Zeichenkodierung in diesem File ist UTF-8.) | ||
# [[Media:Uebung-8.pdf|Übung]] (Abgabe 19.6.2014) | # [[Media:Uebung-8.pdf|Übung]] (Abgabe 19.6.2014) und [[Media:muster_blatt8.pdf|Musterlösung]] | ||
#* Übungen zu Rekursion und Iteration: Fibonaccizahlen, Koch-Schneeflocke, Komplexität rekursiver Algorithmen, Umwandlung von Rekursion in Iteration | #* Übungen zu Rekursion und Iteration: Fibonaccizahlen, Koch-Schneeflocke, Komplexität rekursiver Algorithmen, Umwandlung von Rekursion in Iteration | ||
# [[Media:Uebung-9.pdf|Übung]] (Abgabe '''Dienstag''' 1.7.2014) | # [[Media:Uebung-9.pdf|Übung]] (Abgabe '''Dienstag''' 1.7.2014) und Musterlösung für [[Media:muster_blatt9-1+3.pdf|Aufgaben 1 und 3]] sowie für [[Media:muster_blatt9-2.pdf|Aufgabe 2]] | ||
#* Übungen zur Generizität: Sortieren mit veränderter Ordnung, Iterator für Tiefensuche | #* Übungen zur Generizität: Sortieren mit veränderter Ordnung, Iterator für Tiefensuche | ||
#* Graphenaufgaben: Weg aus einem Labyrinth, Erzeugen einer perfekten Hashfunktion (Dazu benötigen Sie den Artikel [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.51.5566 <i>"An optimal algorithm for generating minimal perfect hash functions"</i>] sowie das File [http://hci.iwr.uni-heidelberg.de/Staff/ukoethe/download/entfernungen.json entfernungen.json]. Die Zeichenkodierung in diesem File ist UTF-8.) | #* Graphenaufgaben: Weg aus einem Labyrinth, Erzeugen einer perfekten Hashfunktion (Dazu benötigen Sie den Artikel [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.51.5566 <i>"An optimal algorithm for generating minimal perfect hash functions"</i>] sowie das File [http://hci.iwr.uni-heidelberg.de/Staff/ukoethe/download/entfernungen.json entfernungen.json]. Die Zeichenkodierung in diesem File ist UTF-8.) | ||
# [[Media:Uebung-10.pdf|Übung]] (Abgabe 8.7.2014) | # [[Media:Uebung-10.pdf|Übung]] (Abgabe 8.7.2014) und Musterlösung für [[Media:muster_blatt10-1.pdf|Aufgabe 1]] sowie für [[Media:muster_blatt10-2.pdf|Aufgabe 2]] | ||
#* Fortgeschrittene Graphenaufgaben: Routenplaner (Dazu benötigen Sie wieder das File [http://hci.iwr.uni-heidelberg.de/Staff/ukoethe/download/entfernungen.json entfernungen.json]. Die Zeichenkodierung in diesem File ist UTF-8.) und Bildverarbeitung (Dazu benötigen Sie die Files [http://hci.iwr.uni-heidelberg.de/Staff/ukoethe/download/cells.pgm cells.pgm] und [http://hci.iwr.uni-heidelberg.de/Staff/ukoethe/download/pgm.py pgm.py].) | #* Fortgeschrittene Graphenaufgaben: Routenplaner (Dazu benötigen Sie wieder das File [http://hci.iwr.uni-heidelberg.de/Staff/ukoethe/download/entfernungen.json entfernungen.json]. Die Zeichenkodierung in diesem File ist UTF-8.) und Bildverarbeitung (Dazu benötigen Sie die Files [http://hci.iwr.uni-heidelberg.de/Staff/ukoethe/download/cells.pgm cells.pgm] und [http://hci.iwr.uni-heidelberg.de/Staff/ukoethe/download/pgm.py pgm.py].) | ||
# [[Media:Uebung-11.pdf|Übung]] (Abgabe 15.7.2014) | # [[Media:Uebung-11.pdf|Übung]] (Abgabe 15.7.2014) | ||
und [[Media:muster_blatt11.pdf|Musterlösung]] sowie schöne [[Media:ballungsgebiete.pdf|Visualisierung der Ballungsgebiete]] von Thorben Kröger | und [[Media:muster_blatt11.pdf|Musterlösung]] sowie schöne [[Media:ballungsgebiete.pdf|Visualisierung der Ballungsgebiete]] von Thorben Kröger | ||
#* Fortgeschrittene Graphenaufgaben 2: Clusterung mittels minimaler Spannbäume, Seam Carving (Dazu benötigen Sie wieder die Files [http://hci.iwr.uni-heidelberg.de/Staff/ukoethe/download/entfernungen.json entfernungen.json] und [http://hci.iwr.uni-heidelberg.de/Staff/ukoethe/download/pgm.py pgm.py] aowie das Bild [http://hci.iwr.uni-heidelberg.de/Staff/ukoethe/download/coast.pgm coast.pgm].) | #* Fortgeschrittene Graphenaufgaben 2: Clusterung mittels minimaler Spannbäume, Seam Carving (Dazu benötigen Sie wieder die Files [http://hci.iwr.uni-heidelberg.de/Staff/ukoethe/download/entfernungen.json entfernungen.json] und [http://hci.iwr.uni-heidelberg.de/Staff/ukoethe/download/pgm.py pgm.py] aowie das Bild [http://hci.iwr.uni-heidelberg.de/Staff/ukoethe/download/coast.pgm coast.pgm].) | ||
# [[Media:Uebung-12.pdf|Übung]] (Abgabe 22.7.2014) | |||
# [[Media:Uebung-12.pdf|Übung]] (Abgabe | #* Randomisierte Algorithmen: RANSAC für Kreise (Dazu benötigen sie das File [http://hci.iwr.uni-heidelberg.de/Staff/ukoethe/download/noisy-circles.txt noisy-circles.txt].) | ||
#* Bonusaufgaben: indirektes Sortieren und Prüfungswiederholung | |||
#* Erfüllbarkeitsproblem, Anwendung: Heim- und Auswärtsspiele im Fussball (Dazu benötigen sie das File [http://hci.iwr.uni-heidelberg.de/Staff/ukoethe/download/bundesliga-paarungen-12-13.json bundesliga-paarungen-12-13.json].) | #* Erfüllbarkeitsproblem, Anwendung: Heim- und Auswärtsspiele im Fussball (Dazu benötigen sie das File [http://hci.iwr.uni-heidelberg.de/Staff/ukoethe/download/bundesliga-paarungen-12-13.json bundesliga-paarungen-12-13.json].) | ||
# [[Media:Bonusuebung.pdf|Übung (Bonus)]] (<font color=red>Achtung: Abgabe bereits am Dienstag, 24.7.2014</font>) | # [[Media:Bonusuebung.pdf|Übung (Bonus)]] (<font color=red>Achtung: Abgabe bereits am Dienstag, 24.7.2014</font>) | ||
#* Greedy-Algorithmus | #* Greedy-Algorithmus | ||
#* Weg durch einen Graphen | #* Weg durch einen Graphen | ||
#* Wiederholungsaufgaben für die Klausur | #* Wiederholungsaufgaben für die Klausur | ||
--- | ---> | ||
== Sonstiges == | == Sonstiges == | ||
Latest revision as of 12:21, 23 October 2020
Vorlesung Algorithmen und Datenstrukturen
apl. Prof. Dr. Ullrich Köthe, Universität Heidelberg, Sommersemester 2020
Die Vorlesung findet dienstags um 14:15 Uhr und donnerstags um 16:15 Uhr online auf Discord und Twitch statt. Die Links haben in Müsli angemeldete Teilnehmer per Email erhalten.
Klausur und Nachprüfung
Der Termin der Abschlussklausur steht noch nicht fest.
Übungsbetrieb
Literatur
- R. Sedgewick: Algorithmen (empfohlen für den ersten Teil, bis einschließlich Graphenalgorithmen)
- J. Kleinberg, E.Tardos: Algorithm Design (empfohlen für den zweiten Teil, einschließlich Graphenalgorithmen)
- T. Cormen, C. Leiserson, R.Rivest: Algorithmen - eine Einführung (empfohlen zum Thema Komplexität)
- Wikipedia und andere Internetseiten (sehr gute Seiten über viele Algorithmen und Datenstrukturen)
Gliederung der Vorlesung
(Termine werden nach und nach aktualisiert)
- Einführung (21. und 23.4.2020)
- Definition von Algorithmen und Datenstrukturen, Geschichte
- Fundamentale Algorithmen: Konstruktoren, Kopierfunktionen, swap.
- Fundamentale Datenstrukturen: Zahlen, Container, Handles
- Python-Grundlagen
- Container (28.4.2020)
- Abstrakte Datentypen und algebraische Spezifikation
- Grundlegende Container: Array, Stack, Queue, assoziatives Array
- Sortieren (some day in 2020)
- Spezifikation des Sortierproblems
- Selection Sort und Insertion Sort
- Merge Sort
- Quick Sort und seine Varianten
- Anzahl der benötigten Vergleiche
- Korrektheit (29.4. und 6.5.2014 -- ab hier altes Datum)
- 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 (8. und 13.5.2014)
- 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 (15. und 20.5.2014)
- Sequentielle Suche
- Binäre Suche in sortierten Arrays, Medianproblem
- Suchbäume, balancierte Bäume
- selbst-balancierende Bäume, Rotationen
- Komplexität der Suche
- Sortieren in linearer Zeit (22.5.2014)
- Permutationen
- Sortieren als Suchproblem
- Bucket Prinzip, Bucket Sort
- Prioritätswarteschlangen (27.5.2014)
- Heap-Datenstruktur
- Einfüge- und Löschoperationen
- Heapsort
- Komplexität des Heaps
- Assoziative Arrays (3.6.2014)
- Datenstruktur-Dreieck für assoziative Arrays
- Definition des abstrakten Datentyps
- JSON-Datenformat
- Realisierung durch sequentielle Suche und durch Suchbäume
- Hashing und Hashtabellen (5. und 10.6.2014)
- 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.2014)
- Typen der Rekursion und ihre Umwandlung in Iteration
- Auflösung rekursiver Formeln mittels Master-Methode und Substitutionsmethode
- Generizität (17.6.2014)
- Abstrakte Datentypen, Typspezifikation
- Required Interface versus Offered Interface
- Adapter und Typattribute, Funktoren
- Beispiel: Algebraische Konzepte und Zahlendatentypen
- Operator overloading in Python
- Graphen und Graphenalgorithmen (24.6. bis 10.7.2014)
- 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 (10. und 15.7.2014)
- 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 (17.7.2014)
- 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 (22.7.2014)
- die Klassen P und NP
- NP-Vollständigkeit und Problemreduktion
- Wiederholung (24.7.2014)
Übungsaufgaben
(im PDF Format). Die Abgabe erfolgt am angegebenen Tag bis 14:00 Uhr per Email an den jeweiligen Übungsgruppenleiter. Bei verspäteter Abgabe bis zu drei Tagen werden noch 50% der erreichten Punkte angerechnet. Danach wird die Musterlösung freigeschaltet.
Die Übungsaufgaben sind zur Zeit nicht freigeschaltet.
