Formale Sprachen und Komplexität
- Aktuelles
- Beschreibung
Inhalt
Das Modul vermittelt Grundkenntnisse in den Gebieten Formale Sprachen, Berechenbarkeit und Komplexitätstheorie. Im einzelnen werden vermittelt:
- Automatentheorie und Formale Sprachen: Chomsky-Hierarchie, reguläre Sprachen und endliche Automaten, kontextfreie Sprachen und Kellerautomaten, kontextsensitive Sprachen,
- Berechenbarkeit: Turingmaschinen und andere Berechnungsmodelle, Unentscheidbarkeit, Halteproblem, rekursiv aufzählbare Probleme,
- Komplexitätstheorie, insbesondere die Klassen P und NP, Definition und Beweise für NP-Vollständigkeit, Beispiele NP-vollständiger Probleme.
Literaturhinweise:
- Theoretische Informatik kurzgefasst, Uwe Schöning, Spektrum Hochschultaschenbuch, ISBN 978-3-8274-1824-1
Das Modul besteht aus einer Vorlesung sowie Übungen in kleinen Gruppen. Die in der Vorlesung besprochenen Inhalte werden im Übungsteil anhand von praktischen Anwendungen eingeübt.
Ein Grossteil der Online-Lehre findet im Moodle statt.
Einschreibeschlüssel: fsk2020Links zu Veranstaltungen aus frühreren Semestern:
Videoaufzeichnung aus früheren Semestern:
- Institut
- Institut für Informatik
- Dozent:in
- Assistent:innen
- Tutor:innen
- Korrektor:innen
- Externe Homepage
- https://moodle.lmu.de/course/view.php?id=8541
- Kursteilnehmer:innen
- 712
- Anmeldung
Mi 01 Apr 2020 00:00 – Mi 30 Sep 2020 23:59
Abmeldung nur bis Mi 30 Sep 2020 23:59
- Material
Das Kursmaterial ist nur für Mitglieder des Kurses einsehbar, also z.B. für Teilnehmer:innen, Tutor:innen, Korrektor:innen und Verwalter:innen.
- Prüfungen
Name Anmeldung ab Anmeldung bis Termin Prüfungsanmeldung Do 09 Jul 2020 00:00Fr 31 Jul 2020 23:59Di 11 Aug 2020 08:00 – 14:00Nicht zur Prüfung angemeldetMo 07 Sep 2020 00:00Fr 02 Okt 2020 20:00Di 06 Okt 2020 14:00 – 20:00Nicht zur Prüfung angemeldet- Termine
Art Zeit Regulärer Raum Notiz Besprechung OrganisatorischesDFNconf VideokonferenzVorlesungVideoaufzeichnungOnline-SprechstundeMoodle Forum- Tutorien
- 12 passende Einträge insgesamt
Art Bezeichnung Tutoren Regulärer Raum Zeit Anmeldungen ab Anmeldungen bis Abmeldungen bis Freie Plätze EinsichtEinsicht 10:00Oettingenstraße, Raum 061 (Hauptgang zwischen Flügel F und G)Fr 18 Sep 2020 00:000EinsichtEinsicht 10:30Oettingenstraße, Raum 061 (Hauptgang zwischen Flügel F und G)Fr 18 Sep 2020 00:001EinsichtEinsicht 11:00Oettingenstraße, Raum 061 (Hauptgang zwischen Flügel F und G)Fr 18 Sep 2020 00:006EinsichtEinsicht 11:30Oettingenstraße, Raum 061 (Hauptgang zwischen Flügel F und G)Fr 18 Sep 2020 00:0025EinsichtEinsicht 15:00Oettingenstraße, Raum 061 (Hauptgang zwischen Flügel F und G)Fr 18 Sep 2020 00:003EinsichtEinsicht 15:30Oettingenstraße, Raum 061 (Hauptgang zwischen Flügel F und G)Fr 18 Sep 2020 00:003EinsichtEinsicht 16:00Oettingenstraße, Raum 061 (Hauptgang zwischen Flügel F und G)Fr 18 Sep 2020 00:009EinsichtEinsicht Zweitklausur 10:00Oettingenstraße, Raum 057 (Hauptgang zwischen Flügel F und G)Di 24 Nov 2020 00:00Fr 04 Dez 2020 00:005EinsichtEinsicht Zweitklausur 10:30Oettingenstraße, Raum 057 (Hauptgang zwischen Flügel F und G)Di 24 Nov 2020 00:00Fr 04 Dez 2020 00:00310EinsichtEinsicht Zweitklausur 13:00Oettingenstraße, Raum 057 (Hauptgang zwischen Flügel F und G)Di 24 Nov 2020 00:00Fr 04 Dez 2020 00:006EinsichtEinsicht Zweitklausur 13:30Oettingenstraße, Raum 057 (Hauptgang zwischen Flügel F und G)Di 24 Nov 2020 00:00Fr 04 Dez 2020 00:001TutoriumLive-SessionVideokonferenz (DFNconf)Fr 17 Apr 2020 00:00