| Semester | |
| Studiengang | Informatik Bachelor |
| IBR Gruppe | ALG (Prof. Fekete) |
| Art | Vorlesung & Übung |
| Dozent | |
| LP | 5 |
| SWS | 3+1+1 |
| Ort & Zeit | Vorlesung / Gr. Übung: Montags und Dienstags, 13:15 Uhr - 14:45 Uhr (UP 3.007)
Kl. Übung: TBA | Gruppe | Termin (14-täglich) | Tutor | Raum | | 01 | Mittwoch, 11:30 - 13:00 | Youssef Naimi | IZ 305 | | 02 | Donnerstag, 09:45 - 11:15 | Max Bierwagen | IZ 305 | | 03 | Donnerstag, 15:00 - 16:30 | Erik Stahlmann | IZ 305 | | 04 | Donnerstag, 16:45 - 18:15 | Erik Stahlmann | IZ 305 | | 05 | Freitag, 09:45 - 11:15 | Jan Wasserscheidt | IZ 161 | | 06 | Freitag, 09:45 - 11:15 | Elias Kaiser | IZ 305 | | 07 | Freitag, 15:00 - 16:30 | Elias Kaiser | IZ 305 | |
| Beginn | Erste Vorlesung / große Übung: 13.04.
Erste kleine Übung: 13.05. |
| Voraussetzungen | keine |
| Sprache | Deutsch |
| Scheinerwerb | Studienleistung: Erfolgreiche Bearbeitung der Hausaufgaben
Prüfungsleistung: Klausur am Ende des Semesters |
| Anmeldung | |
| Inhalt | Die Vorlesung deckt folgende Inhalte ab. - Turing Maschinen
- Chomsky-Hierarchie
- Entscheidbarkeit
- Berechenbarkeit
- Komplexitätstheorie
- NP-Vollständigkeit
|
| Material | Vorlesungen und Übungen Hausaufgaben - Blatt 1: [pdf] (Abgabe bis 04.05., 13 Uhr)
- Blatt 2: [pdf] (Abgabe bis 18.05., 13 Uhr)
- Blatt 3: [pdf] (Abgabe bis 08.06., 13 Uhr)
|
| Literatur/Links | - U. Schöning: Theoretische Informatik - kurzgefasst. Springer, 2008.
- J. E. Hopcroft, R. Motwani, J. D. Ullman: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie. Addison-Wesley Longman, 2002.
- M. Nebel: Formale Grundlagen der Programmierung. Vieweg+Teubner, 2012.
- M. Sipser: Introduction to the Theory of Computation. Cengage Learning, 2012.
- I. Wegener: Complexity Theory. Springer, 2005.
- D. Kozen: Automata and Computability. Springer, 1977.
- O. Goldreich: Computational Complexity. Cambridge University Press, 2008.
- A. M. Turing: On Computable Numbers, with an application to the Entscheidungsproblem.
|
Neuigkeiten - Die kleinen Übungen am Donnerstag, den 14.05., verschieben sich aufgrund des Feiertags um eine Woche nach hinten auf den 21.05.
- Bitte meldet euch auf der [Mailingliste] an.
- Die Einteilung in die Übungsgruppen wurde per Mail versandt. Solltet ihr keine Mail erhalten haben, sende bitte eine Mail an Arne Schmidt. Ein Gruppentausch ist in der Regel nur mit einem Tausch einer anderen Person möglich.
Klausur Die Klausur findet am 25.08. um 10:30 Uhr statt. Die Raumaufteilung wird 1-2 Tage vorher an dieser Stelle bekanntgegeben. Bitte seid 15 Minuten vorher anwesend. Mitzubringen sind: - Studierendenausweis
- Dokumentenechter Stift (u.a. kein Bleistift, Füller oder Rotstifte)
- Ein handschriftlich (nicht elektronisch oder über Tablet, o.Ä.), beidseitig beschriebenes Blatt DIN-A4.
- Wörterbuch (falls nötig) auf Papier ohne Notizen
Andere Hilfmittel sind nicht zugelassen. Papier wird von uns gestellt. Eine "Muster"-Klausur mit ausgewähltem Aufgabenpool ist verfügbar: [pdf] Hinweise zur Klausur Die Klausur geht insgesamt 120 Minuten und es sind 100 Punkte erreichbar. Sie ist allerdings als Überhangsklausur konzipiert, das heißt, man muss nicht jede Aufgabe lösen, um eine gute Note zu erhalten! Mit 40 Punkten hat man sicher bestanden. Bearbeitet die Klausur nicht einfach von vorn nach hinten, sondern schaut, welche Aufgaben einem am besten liegen und bearbeitet diese zuerst. Die Klausur wird 5 Teilgebiete mit jeweils 20 Punkten beinhalten, die ggf auf verschiedene Aufgaben aufgeteilt werden können. Die 5 Teilgebiete sind die folgenden: - Turing-Maschinen und Grammatiken (z.B. Modellieren, Analysieren)
- (Un-)Entscheidbarkeit (z.B. Reduktionen, PCP, SvR, ...)
- Komplexität 1 (L/NL oder P/NP) (z.B. Analyse, Reduktionen, Membership, Hardness, ...)
- Komplexität 2 (P/NP oder PSPACE/NPSPACE) (z.B. Analyse, Reduktionen, Membership, Hardness, ...)
- Weiterführendes (z.B. Einordnung neuer Komplexitätsklassen, Simulation von Turing Maschinen, ...)
Da ein Cheat-Sheet in die Klausur genommen werden darf, werden wenige bis gar keine Wissensfragen in der Klausur vorkommen. Der Fokus liegt auf Verständnisfragen, dem Anwenden von Theoremen und Algorithmen, sowie Transferwissen. Mailingliste Es gibt eine Mailingliste zur Veranstaltung. Bitte registriert euch dort. Wir versenden darüber Informationen. Es werden nur tubs-Adressen freigegeben. Bei Problemen wendet euch per Mail an Arne Schmidt. Hier geht es zur [Mailingliste]. |
