Die Vorlesungen und Übungen werden in elektronischer Form stattfinden.
Dieses Semester findet die Kommunikation mehr denn je über diese Webseite und E-Mails statt. Bitte schauen Sie regelmäßig hier vorbei und verwenden Sie Ihre Uni-Mailadresse (@stud.uni-frankfurt.de), wenn Sie uns schreiben. Wir haben immer wieder Probleme, dass unsere Antworten in Spamfiltern landen. Verwenden Sie nach Möglichkeit auch keine Weiterleitung auf eine andere Mailadresse.
Denken Sie an die Anmeldung zur Klausur am 23.2.
Sollten Sie bei der Anmeldung einen “Voraussetzungsfehler” angezeigt bekommen, verwenden Sie bitte das Formular “Anmeldung schriftliche Modulabschlussprüfung” und schicken Sie dieses digital ausgefüllt oder als Scan an das Prüfungsamt Informatik.
Am 21.1. findet die Evaluation der Vorlesung statt. Den Link und weitere Informationen finden Sie im Moodle.
Die Übungsgruppen wurden zugeteilt. Inzwischen sollten Sie an Ihre Uni-Mailadresse (@stud.uni-frankfurt.de) eine E-Mail mit einem Abgabelink bekommen haben, über den Sie das ganze Semester die Übungen abgeben und die Korrektur runterladen können. Schauen Sie auch im Spam-Ordner nach. Melden Sie sich frühzeitig, sollten Sie keinen Link bekommen haben, da wir nicht garantieren können kurz vor der Abgabe neue Links verschicken zu können.
Die Übungen beginnen ab Donnerstag dem 12.11. mit der Besprechung von Blatt 0. Nutzen Sie die ersten Termine auch um evtl. vorhandene technische Probleme mit den Onlinediensten in den den Griff zu bekommen.
Die Links zu den Tutorien finden Sie im Moodle.
Am Do. 14.01. um 8:30 findet über Zoom die nächste Fragestunde statt.
Die Veranstaltung wird nicht aufgezeichnet, allerdings werden die Folien hier auf der Webseite veröffentlicht.
Wenn Sie Fragen haben die in der Fragestunde besprochen werden sollen, schicken Sie diese bitte bis 24 Stunden vorher an algo220-fragestunde@ae.cs.uni-frankfurt.de
Den Link und die Zugangsdaten für das Zoom-Meeting finden Sie im Moodle.
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
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) |
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 und 2.1 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 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 |
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.