Logbuch „Theoretische Informatik 2“ (SoSe17)

Hier finden Sie (nach den Vorlesungen) Informationen zum Inhalt der einzelnen Vorlesungsstunden sowie gelegentlich ergänzende Bemerkungen.

  • Di, 25.04.2017 und Mi, 26.04.2017

    Hopcrofts Algorithmus (Zerlegte Klassen, Checkmenge. Eine zerlegte Mutterklasse X wird in ihre beiden Kinderklassen zerlegt. wenn X nicht in Check liegt, dann wird das kleinere der beiden Kinder zu Check hinzugefügt. Jeder Übergang gehört zu höchstens log(n) Checkmengen. Fast lineare Laufzeit); Nerode-Relation (Minimalität des Äquivalenzklassenautomaten, Entwurf des Nerode-Automaten, Satz von Myhill-Nerode); Pumping-Lemma (die Spielregeln, das Pumpinglemma kann versagen), NFAs (Potenmengenkonstruktion, DFAs benötigen mgl. exponentiell mehr Zustände)

    Material:
  • Di, 18.04.2017 und Mi, 19.04.2017

    Organisatorisches: bitte unbedingt an den Übungen teilnehmen, Übungsbetrieb beginnt in der dritten Vorlesungswoche, das erste Blatt erscheint am Montag der zweiten Vorlesungswoche;

    Alphabete, Worte und Sprachen, Operationen auf Sprachen (Konkatenation, Kleene-Hülle), Beweis von Mengengleichheit, rekursive Definitionen, Komplexitätsklassen;
    DFAs (erweiterte Übergangsfunktion, die Sprache eines DFA, reguläre Sprachen, Verschmelzungsrelation, die Bestimmung aller Paare inäquivalenter Zustände, der Äquivalenzklassenautomat);
    der Algorithmus von Moore, die Verschmelzungsrelation (VR) eingeschränkt auf Worte der Länge höchstens i, die Tiefe eines DFA, wie bestimmt man die VR für Worte der Länge höchstens i+1 aus der VR für Worte der Länge höchstens i? Laufzeitanalyse;
    ein Beispiel für Hopcrofts Algorithmus

    Material: