Menu
SS 2021
WS 2020/2021
SS 2020
WS 2019/2020
SS 2019
WS 2018/2019
SS 2018
WS 2017/2018
SS 2017
WS 2016/2017
Current projects
Previous projects
Faculty
Postdocs
PhD Students
Student Assistants
Administrative Staff
Alumni
Die Klausurergebnisse der Klausur vom 30.03 (Lösungsskizze). sowie die Hinweise zur Klausureinsicht sind online.
Frohe Ostern!
Die Klausurergebnisse der Klausur vom 23.2. (Lösungsskizze) sowie die Hinweise zur Klausureinsicht finden Sie hier. Die Klausurergebnisse werden jetzt mit mehr Details angezeigt.
Dienstag 08:00 - 10:00
Donnerstag 08:00 - 10:00
Alle anderen Termine werden rechtzeitig hier angekündigt.
Elizaveta Kovalevskaya
Alex Schickedanz
Fragen rund um die Vorlesung bitte an algo220@ae.cs.uni-frankfurt.de.
Hinweis: In der Vergangenheit kam es immer wieder zu Zustellungsproblemen bei externen E-Mail Providern. Wenn Sie eine Antwort auf Ihre E-Mail erwarten, verwenden Sie bitte Ihre Uni-Mailadresse.
Fragen zu Vorlesungsinhalten oder Übungsaufgaben stellen Sie bitte in den Tutorien oder beim Lernzentrum.
Das Lösen von Übungsaufgaben geschieht auf freiwilliger Basis. Dennoch ist die Teilnahme am Übungsbetrieb unbedingt zu empfehlen. Es werden weiterführende Inhalte vermittelt und es gibt die Möglichkeit Bonuspunkte zu sammeln. Eine Beobachtung unsererseits ist: Je höher die Bonuspunkte, desto höher die Wahrscheinlichkeit, eine gute Note zu erhalten. Weiterhin gilt aber, dass leider in der Vergangenheit immer wieder Betrugsversuche bei Übungsabgaben vorkamen. Deshalb bitten wir Sie darum, von solchen Täuschungsversuchen Abstand zu nehmen. Es lohnt sich nicht! Eine Zuwiderhandlung kann dazu führen, dass wir Ihnen alle Bonuspunkte aberkennen (genaue Regelung: siehe “Hinweise zu den Übungsabgaben”).
Es gibt wöchentlich Übungsblätter. Die Abgabe der Lösungen erfolgt dieses Semester ausschließlich über unseren Online-Briefkasten. Den genauen Ablauf erfahren Sie rechtzeitig hier auf der Webseite.
Sie können durch die Teilnahme an den Übungen bis zu 10% Bonuspunkte in der Klausur erhalten. Diese werden auf die Note einer bestanden Klausur angerechnet.
| Gruppe 01 | Mo | 10 - 12 |
| Gruppe 02 | Mo | 12 - 14 |
| Gruppe 03 | Mo | 16 - 18 |
| Gruppe 04 | Di | 10 - 12 |
| Gruppe 05 | Di | 16 - 18 |
| Gruppe 06 | Mi | 10 - 12 |
| Gruppe 07 | Mi | 14 - 16 |
| Gruppe 08 | Mi | 16 - 18 |
| Gruppe 09 | Do | 10 - 12 |
| Gruppe 10 | Do | 10 - 12 |
| Gruppe 11 | Do | 14 - 16 |
| Gruppe 12 | Fr | 10 - 12 |
| Gruppe 13 | Fr | 14 - 16 |
Aus gegebenem Anlass sehen wir uns verpflichtet auf folgendes hinzuweisen:
Onlineabgabe:
Plagiate und Betrugsversuche:
Sie sollen anhand der Übungsaufgaben den Stoff der Vorlesung besser verstehen. Ein wichtiger Teil davon sind die Kommentare der Tutoren auf den korrigierten Abgaben. Hier finden Sie die Gründe, wenn nicht die vollen Übungspunkte erreicht wurden.
Das Modul GL-1 wird nicht mehr angeboten. Studenten die noch GL-1 benötigen müssen Algo1b und Algo2 belegen.
Die Vorlesung behandelt fundamentale Algorithmen, und allgemeine Methoden für den Entwurf und die Analyse von Algorithmen, sowie die NP-Vollständigkeit und die Grenzen der Berechenbarkeit. Algorithmen für Ordnungsprobleme wie Sortieren und Mischen werden beschrieben und analysiert. Algorithmentypen bzw. Entwurfsmethoden wie Greedy-Algorithmen, Teile-und-Beherrsche und dynamisches Programmieren werden eingeführt und angewandt. Das Konzept der NP-Vollständigkeit erlaubt die Untersuchung der algorithmischen Komplexität von Problemen. Die NP-Vollständigkeit des Erfüllbarkeitsproblems und weiterer Berechnungsprobleme wird gezeigt. Abschließend wird ein Ausblick auf die Behandlung komplexer algorithmischer Probleme unter Betonung der Approximationsalgorithmen gegeben. Der Begriff der Berechenbarkeit wird eingeführt und ausführlich diskutiert. Es werden Beispiele für nicht entscheidbare Sprachen angeführt, und mit dem Satz von Rice wird nachgewiesen, dass fast alle interessanten Fragen über das Verhalten eines Programms unentscheidbar sind.
Wissen und Verstehen: Die Kenntnis fundamentaler Algorithmen; die Fähigkeit, den Prozess des Entwurfs und der Analyse von Algorithmen eigenständig durchführen zu können; sowie das Wissen um die Grenzen der (effizienten) Berechenbarkeit.
Können: Neben der Wissensaneignung lernen die Studierenden, die nichteffiziente Lösbarkeit algorithmischer Probleme einzuschätzen. Dafür werden die Konzepte der NP-Vollständigkeit und der Entscheidbarkeit eingeübt (instrumentale Kompetenz). Die Kraft, aber auch die prinzipiellen Grenzen algorithmischer Lösungsansätze werden ausgelotet: ähnliche Fragestellungen im Berufsleben werden dadurch jenseits kurzlebiger Trends beantwortbar. Kommunikative Kompetenzen werden durch Arbeiten in Gruppenübungen und die dortige Vorstellung und Diskussion von Übungsaufgaben erworben.
Hauptklausur: 23.02.2021, 09:00 - 12:00
Nachklausur: 30.03.2021, 14:00 - 17:00
Die Anmeldung über QIS ist ab sofort möglich.
Details zum genauen Ablauf werden rechtzeitig bekannt gegeben.
Die Klausur ist bestanden, wenn mindestens 50% aller erreichbaren Punkte erzielt wurden. Zur Benotung werden neben dem Klausurergebnis Bonuspunkte aus den Übungen mit einem Maximalgewicht von 10% eingehen.
Hier finden Sie die aktuellen Freiversuchsregelungen der Informatik.
Auch für das Wintersemester 2020/21 gilt eine universitätsweite Freiversuchsregelung für nichtbestandene Prüfungsleistungen (Abschlussarbeiten ausgenommen). Diese Regelung gilt nur einmalig pro Prüfung und nur für Prüfungsleistungen, für welche nicht bereits im Sommersemester 2020 ein Freiversuch in Anspruch genommen wurde.
Dazu wird klargestellt: Es gibt nur einen “Corona-Freiversuch” pro Modul inkl. äquivalenten Modulen.
D.h. für Algo2: Wenn Ihnen bereits ein universitärer Freiversuch für die GL-1 Nachklausur im Sommersemester 2020 gegeben wurde, können Sie keinen Freiversuch mehr für die ALGO-2-Klausuren erhalten.
Videos zur Vorlesung stehen hier zur Verfügung.
Hinweis: Das erste Video wird am 5.11. veröffentlicht.
Es handelt sich dabei um Aufzeichnungen der Vorlesungen Theoretische Informatik 1 aus den vergangen Semestern. Teilweise werden die Videos neu geschnitten oder durch neue Videos ergänzt um den Inhalt der aktuellen Vorlesung gerecht zu werden.
Hinweis: Die Videos werden von studiumdigitale gehostet. Sie benötigen dafür evtl. einen HRZ-Account.
Video V01: Einführung, Bubble- und Selection Sort
Video V02: Selection-, Insertion-, Heap- und Quicksort
Video V03: Laufzeit Quicksort und Mergesort
Video V04: Joulesort-Challenge, Externspeichersortieren und vergleichsorientierte Sortierverfahren
Video V05: Distribution Counting, Radixsort, Sample Sort, MPI, Parralleles Sortieren
Video V06.1: Sample Sort, Graphen und Datenstrukturen
Video V06.2: NP-Vollständigkeit und schwierige Probleme
Video V07: Turingmaschinen, Klasse P, Klasse NP und polynomielle Reduktion
Video V08: polynomielle Reduktion, NP-Vollständigkeit, KNF-SAT, 3-SAT, 2-SAT und Clique
Video V09: Independent Set-, Set Cover-, Vertex Cover ist NP-vollständig, Schwierige Wegeprobleme in Graphen
Video V10: Satz von Cook, Optimierungsprobleme, Approximationsprobleme und Last-Verteilung
Video V11: Last-Verteilung, On-line und Off-line Heuristik, Rucksackproblem
Video V12: ungewichtetes Vertex Cover Problem, Matching Heuristik, gewichtetes Vertex Cover Problem
Video V13: Entscheid- und Berechenbarkeit, Church-Turing These, PSPACE, QBF
Video V14: PSPACE, Church-Turing These, Unentscheidbarkeit, Gödelnummer, Diagonalsprache, Reduktion
Video V15: Universelle Sprache, das (spezielle) Halteproblem, Satz von Rice
Video V16: Satz von Rice, Rekursive Aufzählbarkeit, Gödelsche Unvollständigkeitssatz
Video V17: Lokale Suche, Minimum Balanced Cut, Metropolis Algorithmus
Video V18: Minimum Balanced Cut, Metropolis Algorithmus, Simulated Annealing, Evolutionäre Algorithmen, Mutationsoperatoren, Crossover Operatoren
Video V19: Exakte Algorithmen, Backtracking, Branch Operator
Altklausuren finden Sie hier.
Die Bearbeitung der Übungsblätter in Gruppen ist erlaubt, jedoch müssen Sie Ihre Lösungen eigenständig aufschreiben.
Die Übungsblätter werden so entworfen, dass ihre Bearbeitung mit den Kenntnissen aus der Vorlesung und aus vorangegangenen Übungsblättern möglich ist. Sollten Sie in Ihrer Lösung dennoch andere Quellen (Bücher, Skripte, Internetforen, soziale Netzwerke, Lösungen anderer Studenten, etc.) verwenden, so müssen Sie die entsprechenden Stellen als direkte oder indirekte Zitate kennzeichnen. Orientieren Sie sich hierfür einfach an den Hinweisen zum Zitieren in schriftlichen Arbeiten am Institut für Informatik. Darüber hinaus muss Ihre persönliche Leistung stets deutlich erkennbar sein. Bei direkten Zitaten oder fast unverändert übernommenen Passagen liegt keine persönliche Leistung vor.
Beachten Sie auch die Hinweise zu Plagiaten und Betrugsversuchen.
| Download | Ausgabe | Abgabe |
|---|---|---|
| Übung 0 | 03.11. | keine |
| Übung 1 | 17.11. | 24.11. 08:00 (morgens) |
| Übung 2 | 24.11. | 01.12. 08:00 (morgens) |
| Übung 3 | 01.12. | 08.12. 08:00 (morgens) |
| Übung 4 | 08.12. | 15.12. 08:00 (morgens) |
| Übung 5 | 15.12. | 12.01. 08:00 (morgens) |
| Übung 6 | 12.01. | 19.01. 08:00 (morgens) |
| Übung 7 | 19.01. | 26.01. 08:00 (morgens) |
| Übung 8 | 26.01. | 02.02. 08:00 (morgens) |
| Übung 9 | 02.02. | 09.02. 08:00 (morgens) |
Update: In Aufgabe 1.4 wurde der Begriff “Wartezeit” klargestellt.
Dieses Semester bieten wir Videos an, in denen die Übungsaufgaben vorgerechnet werden. Die gezeigten Lösungen sind nicht als Musterlösung zu verstehen, sondern als einer von evtl. mehreren Lösungswegen.
Die Videos finden Sie hier.
Hinweis: Die Videos werden von studiumdigitale gehostet. Sie benötigen dafür evtl. einen HRZ-Account.
Selbststests sind ein zusätzliches Übungsangebot. Hier finden Sie Aufgaben und Lösungen mit denen Sie Ihren Wissensstand selbst überprüfen können.
Hinweis: Die Lösungen zu den den Selbsttests 2.0 ff befinden sich am Ende des Dokuments.
| Selbsttest 0.0: O-Notation | mit JS | ohne JS | Lösung |
| Selbsttest 0.1: Pseudocodeanalyse | mit JS | ohne JS | Lösung |
| Selbsttest 0.2: Rekursionsgleichungen | mit JS | ohne JS | Lösung |
| Selbsttest 0.3: O-Notation mit Logarithmen | mit JS | ohne JS | Lösung |
| Selbsttest 0.3a: O-Notation mit Logarithmen (28.01.21) | ohne JS | ||
| Selbsttest 1.0: Laufzeiten Sortieralgorithmen | mit JS | ohne JS | Lösung |
| Selbsttest 1.1: Bubble Sort | mit JS | ohne JS | Lösung |
| Selbsttest 1.2: Insertion Sort | mit JS | ohne JS | Lösung |
| Selbsttest 1.3: Mergesort | mit JS | ohne JS | Lösung |
| Selbsttest 1.4: Partition | mit JS | ohne JS | Lösung |
| Selbsttest 1.5: Radixsort | mit JS | ohne JS | Lösung |
| Selbsttest 1.6: Distribution Counting | mit JS | ohne JS | Lösung |
| Selbsttest 2.0: Entscheidungsprobleme | ohne JS | ||
| Selbsttest 2.1: Schwere und leichte Probleme | ohne JS | ||
| Selbsttest 2.2: Scheduling | ohne JS | ||
| Selbsttest 2.3: 2-KNF-Formeln | ohne JS | ||
| Selbsttest 2.4: Lineare Programmierung | ohne JS | ||
| Selbsttest 2.5: Entscheidbarkeit (aktualisiert: 2.2.2021, Anmerkung (siehe unten)) | ohne JS | ||
| Selbsttest 2.6: Lokale Optima | ohne JS |
Anmerkung zu Selbsttest 2.5, Aufgabe 2.1: In der Vorlesung haben wir definiert, wann eine Turingmaschine eine Eingabe „akzeptiert“ und wann sie „hält“. Den Begriff des „Verwerfens“ haben wir zwar häufig benutzt, aber nicht exakt definiert. Meistens meinten wir damit, dass die Turingmaschine in einem nicht akzeptierenden Zustand hält. Diese Sichtweise wird auch in Definition 12.2 zur rekursiven Aufzählbarkeit verwendet. Die zur Aufgabe 2.1 im Selbsttest präsentierte Lösung verwendet eine andere Sichtweise, die man ebenfalls in der Literatur findet: Verwerfen bedeutet dort, dass die Turingmaschine für die gegebene Eingabe in einem nicht akzeptierenden Zustand hält oder dass sie nicht hält.
Es stehen Skripte von Herrn Prof. Dr. G. Schnitger zu Theoretische Informatik 1 (GL1) zur Verfügung.
Hinweis: Mit der Zeit soll das Skript für Algo2 neu zusammengestellt werden. Bis dahin haben wir leider erstmal nur das Skript zu GL1.