Organisatorisches Einf¨ uhrung Chomsky-Hierarchie Regul¨ are Sprachen Kontextfreie Sprachen Vorlesung “Automaten und Formale Sprachen” alias “Theoretische Informatik” Sommersemester 2015 Prof. Barbara K¨ onig ¨ Ubungsleitung: Jan St¨ uckrath Barbara K¨ onig Automaten und Formale Sprachen 1 Organisatorisches Einf¨ uhrung Chomsky-Hierarchie Regul¨ are Sprachen Kontextfreie Sprachen Das heutige Programm: Organisatorisches Vorstellung ¨ Ablauf der Vorlesung und der Ubungen Pr¨ ufung & Klausur Literatur & Folien Einf¨ uhrung und Motivation: “Automaten und Formale Sprachen” Inhalt der Vorlesung Barbara K¨ onig Automaten und Formale Sprachen 2 Organisatorisches Einf¨ uhrung Chomsky-Hierarchie Regul¨ are Sprachen Kontextfreie Sprachen Wer sind wir? Dozentin: Prof. Barbara K¨ onig Raum LF 264 E-Mail: barbara [email protected] ¨ Ubungsleitung: Jan St¨ uckrath Raum LF 265 [email protected] Web-Seite: www.ti.inf.uni-due.de/teaching/ss2015/afs/ Barbara K¨ onig Automaten und Formale Sprachen 3 Organisatorisches Einf¨ uhrung Chomsky-Hierarchie Regul¨ are Sprachen Kontextfreie Sprachen Vorlesungstermine Termin: Dienstag, 12:15-13:45 Uhr im Raum LB 131 Barbara K¨ onig Automaten und Formale Sprachen 4 Organisatorisches Einf¨ uhrung Chomsky-Hierarchie Regul¨ are Sprachen Kontextfreie Sprachen ¨ Termine der Ubungsgruppen/Tutorien ¨ Ubungsgruppen: Gruppe ISE BAI-1 BAI-2 BAI-3 BAI-4 Tag Di Di Do Fr Fr Uhrzeit 8:00 - 10:00 16:00 – 18:00 14:00 – 16:00 10:00 – 12:00 12:00 – 14:00 Barbara K¨ onig Raum LE 120 LK061 BC523 LC 137 LK052 Sprache Englisch Deutsch Deutsch Deutsch Deutsch Automaten und Formale Sprachen 5 Organisatorisches Einf¨ uhrung Chomsky-Hierarchie Regul¨ are Sprachen Kontextfreie Sprachen ¨ Hinweise zu den Ubungen ¨ Die Ubungen und Tutorien beginnen in der dritten Vorlesungswoche am Dienstag, den 21. April. Bitte versuchen Sie, sich m¨ oglichst gleichm¨aßig auf die ¨ Ubungen zu verteilen. ¨ Besuchen Sie die Ubungen! Diesen Stoff kann man nur durch ¨ regelm¨aßiges Uben erlernen. Auswendiglernen hilft nicht besonders viel. ¨ Die Ubungsbl¨ atter werden jeweils am Dienstag der Vorwoche ¨ ins Netz gestellt. Das erste Ubungsblatt wird am 14.4. bereitgestellt. Barbara K¨ onig Automaten und Formale Sprachen 6 Organisatorisches Einf¨ uhrung Chomsky-Hierarchie Regul¨ are Sprachen Kontextfreie Sprachen ¨ Hinweise zu den Ubungen Abgabe der gel¨osten Aufgaben bis Montag der folgenden Woche, 16:00 Uhr. Einwurf in den Briefkasten neben dem Raum LF 259 oder Abgabe per Moodle. Bitte geben Sie auf Ihrer L¨ osung deutlich die Vorlesung, Ihren Namen, Ihre Matrikelnummer und Ihre Gruppennummer an. Elektronische Abgaben sind nur als PDF zul¨assig! Bitte benennen Sie Dateien nach folgendem Schema (um eine eindeutige Namenswahl zu gew¨ahrleisten): <vorname>-<nachname>-<blattnr>.pdf Es sind keine Gruppenabgaben erlaubt, nur Einzelabgaben. Barbara K¨ onig Automaten und Formale Sprachen 7 Organisatorisches Einf¨ uhrung Chomsky-Hierarchie Regul¨ are Sprachen Kontextfreie Sprachen ¨ Hinweise zu den Ubungen Wir verwenden Moodle, um: die Aufgabenbl¨atter zur Verf¨ ugung zu stellen, die Hausaufgaben elektronisch (nur PDF!) abzugeben und um Diskussionsforen bereitzustellen. Moodle-2-Plattform an der Universit¨at Duisburg-Essen: http://moodle2.uni-due.de/ (siehe auch Link auf der Webseite) Bitte legen Sie dort einen Zugang an (falls noch nicht vorhanden) und tragen Sie sich in den Kurs “Automaten und Formale Sprachen 2015” (Sommersemester 2015 → Ingenieurwissenschaften → Informatik und Angewandte Kognitionswissenschaft) ein. Bitte mit Uni-Kennung anmelden! Zugangsschl¨ ussel: . . . Barbara K¨ onig Automaten und Formale Sprachen 8 Organisatorisches Einf¨ uhrung Chomsky-Hierarchie Regul¨ are Sprachen Kontextfreie Sprachen Pr¨ufung Es gibt mehrere M¨oglichkeiten, die Vorlesung pr¨ ufen zu lassen . . . Klausur (f¨ ur BAI & ISE & Nebenfach-Studierende). Voraussichtlicher Termin: 14. August 2015 M¨ undliche Pr¨ ufung (f¨ ur BAIs, die diese Vorlesung m¨ undlich pr¨ ufen lassen; Alternative: m¨ undliche Pr¨ ufung in “Rechnernetze und Sicherheit”) Voraussichtlicher Termin: 10.-14. August 2015 Im Allgemeinen findet diese m¨ undliche Pr¨ ufung als Kombipr¨ ufung/Modulpr¨ ufung gemeinsam mit “Berechenbarkeit und Komplexit¨at” statt. Es gibt Ausnahmen f¨ ur Studierende, die im Sommersemester beginnen und beide Vorlesungen in gr¨ oßerem Abstand h¨ oren. Anmeldung u ufungsamt ¨ber das Pr¨ Barbara K¨ onig Automaten und Formale Sprachen 9 Organisatorisches Einf¨ uhrung Chomsky-Hierarchie Regul¨ are Sprachen Kontextfreie Sprachen Pr¨ufung Hinweise: F¨ ur BAIs, Studierende im Nebenfach, etc. heißt die Vorlesung “Automaten und Formale Sprachen”. Das Modul, das “Automaten und Formale Sprachen” & “Berechenbarkeit und Komplexit¨at” umfasst, heißt “Theoretische Informatik”. Bei ISE tr¨agt die Vorlesung alleine den Namen “Theoretische Informatik”. Barbara K¨ onig Automaten und Formale Sprachen 10 Organisatorisches Einf¨ uhrung Chomsky-Hierarchie Regul¨ are Sprachen Kontextfreie Sprachen Pr¨ufung ¨ Wenn Sie 50% der Ubungspunkte erzielt haben, so erhalten Sie ¨ einen Bonus f¨ ur die Pr¨ ufung. (F¨ ur das Vorrechnen in der Ubung gibt es 10 Extrapunkte.) Auswirkung: Verbesserung um eine Notenstufe; z.B. von 2,3 auf 2,0 Bonuspunkte aus dem SS 2015 (oder fr¨ uher) gelten nicht mehr! F¨ ur die m¨ undliche Modulpr¨ ufung “Theoretische Informatik” (Kombipr¨ ufung) ist es erforderlich, den Bonus f¨ ur jede der beiden Vorlesungen (“Automaten und Formale Sprachen” & “Berechenbarkeit & Komplexit¨at”) zu erzielen. Barbara K¨ onig Automaten und Formale Sprachen 11 Organisatorisches Einf¨ uhrung Chomsky-Hierarchie Regul¨ are Sprachen Kontextfreie Sprachen Literatur Die Vorlesung basiert im wesentlichen auf folgendem Buch: Uwe Sch¨oning: Theoretische Informatik – kurzgefaßt. Spektrum, 2008. (5. Auflage) Weitere relevante B¨ ucher: Neuauflage eines alten Klassikers: Hopcroft, Motwani, Ullman: Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 2001. Auf Deutsch: Hopcroft, Motwani, Ullman: Einf¨ uhrung in die Automatentheorie, Formale Sprachen und Komplexit¨atstheorie, Pearson, 2002. Vossen, Witt: Grundkurs Theoretische Informatik, vieweg, 2006. Asteroth, Baier: Theoretische Informatik, Pearson, 2003. Barbara K¨ onig Automaten und Formale Sprachen 12 Organisatorisches Einf¨ uhrung Chomsky-Hierarchie Regul¨ are Sprachen Kontextfreie Sprachen Literatur Barbara K¨ onig Automaten und Formale Sprachen 13 Organisatorisches Einf¨ uhrung Chomsky-Hierarchie Regul¨ are Sprachen Kontextfreie Sprachen Literatur Barbara K¨ onig Automaten und Formale Sprachen 14 Organisatorisches Einf¨ uhrung Chomsky-Hierarchie Regul¨ are Sprachen Kontextfreie Sprachen Literatur Barbara K¨ onig Automaten und Formale Sprachen 15 Organisatorisches Einf¨ uhrung Chomsky-Hierarchie Regul¨ are Sprachen Kontextfreie Sprachen Folien Folien werden auf der Webseite bereitgestellt regelm¨aßig aktualisiert Die Folien werden sich gegen¨ uber dem letzten Jahr ver¨andern. Trotzdem macht es Sinn, sich die Folien des Vorjahrs bereits anzusehen (www.ti.inf.uni-due.de/teaching/ss2014/afs/downloads/). ¨ Dort gibt es auch eine englische Ubersetzung der Folien des Vorjahrs. Barbara K¨ onig Automaten und Formale Sprachen 16
© Copyright 2024 ExpyDoc
