F07_THI < F07_Studium

Sie sind hier: Foswiki>F07_Studium Web>F07_THI (Revision 5) (Quelltext-Ansicht)
<!--
   * Set USERSTYLEURL = %PUBURLPATH%/%WEB%/DokumentFormat/fonts.css
-->
---+!! %FORMFIELD{"TopicClassification"}% %FORMFIELD{"Bezeichnung"}%


%TOC{depth="3"}%
%STARTSECTION{"no_toc"}%
---
*Verantwortlich:* Prof. Dr. Randerath

---++ Lehrveranstaltung
---+++ Befriedigt Modul (MID)
   * aktuelle
      * [[MaTIN2012_THI]]

---+++ Organisation
<sticky>
  <table border="0">
    <tr valign="top">
      <td>
        <table border="1" cellpadding="2" cellspacing="0">
          <th colspan="2">Version</th>
          <tr>
            <td>erstellt</td>
            <td>2013-05-13</td>
          </tr>
          <tr>
            <td>VID</td>
            <td>2</td>
          </tr>
          <tr>
            <td>gültig ab</td>
            <td>SS 2013</td>
          </tr>
          <tr>
            <td>gültig bis</td>
            <td/>
          </tr>
        </table>
      </td>
      <td>         </td>
      <td>
        <table border="1" cellpadding="2" cellspacing="0">
          <th colspan="2">Bezeichnung</th>
          <tr>
            <td>Lang</td>
            <td>%FORMFIELD{"Bezeichnung"}%</td>
          </tr>
          <tr>
            <td>Englisch</td>
            <td>Theoretical Computer Science</td>
          </tr>
          <tr>
            <td>LVID</td>
            <td>F07_THI</td>
          </tr>
          <tr>
            <td>LVPID (Prüfungsnummer)</td>
            <td/>
          </tr>
        </table>
      </td>
    </tr>
  </table>
</sticky><sticky>
  <table border="0">
    <tr valign="top">
      <td>
        <table border="1" cellpadding="2" cellspacing="0">
          <th colspan="2">Semesterplan (SWS)</th>
          <tr>
            <td>Vorlesung</td>
            <td>%FORMFIELD{"VorlesungSWS"}%</td>
          </tr>
          <tr>
            <td>Übung (ganzer Kurs)</td>
            <td>%FORMFIELD{"UebungGanzSWS"}%</td>
          </tr>
          <tr>
            <td>Übung (geteilter Kurs)</td>
            <td>%FORMFIELD{"UebungHalbSWS"}%</td>
          </tr>
          <tr>
            <td>Praktikum</td>
            <td>%FORMFIELD{"PraktikumSWS"}%</td>
          </tr>
          <tr>
            <td>Projekt</td>
            <td>%FORMFIELD{"ProjektSWS"}%</td>
          </tr>
          <tr>
            <td>Seminar</td>
            <td>%FORMFIELD{"SeminarSWS"}%</td>
          </tr>
          <tr>
            <td>Tutorium (freiwillig)</td>
            <td>%FORMFIELD{"TutoriumSWS"}%</td>
          </tr>
        </table>
      </td>
      <td>    </td>
      <td>
        <table border="1" cellpadding="2" cellspacing="0">
          <th colspan="2">Präsenzzeiten</th>
          <tr>
            <td>Vorlesung</td>
            <td>%FORMFIELD{"VorlesungPZ"}%</td>
          </tr>
          <tr>
            <td>Übung (ganzer Kurs)</td>
            <td>%FORMFIELD{"UebungGanzPZ"}%</td>
          </tr>
          <tr>
            <td>Übung (geteilter Kurs)</td>
            <td>%FORMFIELD{"UebungHalbPZ"}%</td>
          </tr>
          <tr>
            <td>Praktikum</td>
            <td>%FORMFIELD{"PraktikumPZ"}%</td>
          </tr>
          <tr>
            <td>Projekt</td>
            <td>%FORMFIELD{"ProjektPZ"}%</td>
          </tr>
          <tr>
            <td>Seminar</td>
            <td>%FORMFIELD{"SeminarPZ"}%</td>
          </tr>
          <tr>
            <td>Tutorium (freiwillig)</td>
            <td>%FORMFIELD{"TutoriumPZ"}%</td>
          </tr>
        </table>
      </td>
      <td>    </td>
      <td>
        <table border="1" cellpadding="2" cellspacing="0">
          <th colspan="2">max. Teilnehmerzahl</th>
          <tr>
            <td>Übung (ganzer Kurs)</td>
            <td>%FORMFIELD{"UebungGanzTeilnehmer"}%</td>
          </tr>
          <tr>
            <td>Übung (geteilter Kurs)</td>
            <td>%FORMFIELD{"UebungHalbTeilnehmer"}%</td>
          </tr>
          <tr>
            <td>Praktikum</td>
            <td>%FORMFIELD{"PraktikumTeilnehmer"}%</td>
          </tr>
          <tr>
            <td>Projekt</td>
            <td>%FORMFIELD{"ProjektTeilnehmer"}%</td>
          </tr>
          <tr>
            <td>Seminar</td>
            <td>%FORMFIELD{"SeminarTeilnehmer"}%</td>
          </tr>
        </table>
      </td>
    </tr>
  </table>
</sticky>

*Gesamtaufwand:* %FORMFIELD{"Gesamtaufwand"}%

---++++ Unterrichtssprache
   * Deutsch

---++++ Niveau
   * %FORMFIELD{"Niveau"}%
---++++ Notwendige Voraussetzungen
   * Grundlagen der Automatentheorie und der Formalen Sprachen

---++++ Literatur
   * Theoretische Informatik, J. Hromkovic, Teubner-Verlag
   * Theoretische Informatik - kurzgefasst, U. Schöning, Spektrum-Verlag
   * Theoretische Grundlagen der Informatik, R. Solcher, Hanser-Verlag

---++++ Dozenten



---++++ Wissenschaftliche Mitarbeiter
   * tba

---++++ Zeugnistext
Theoretische Informatik

---+++ Kompetenznachweis
<sticky>
  <table border="1" cellpadding="2" cellspacing="0">
    <th colspan="2">Form</th>
    <tr>
      <td>sMP</td>
      <td>100% (mündliche Prüfung)</td>
    </tr>
  </table>
</sticky>

<sticky>
  <table border="1" cellpadding="2" cellspacing="0">
    <th colspan="2">Aufwand [h]</th>
    <tr>
      <td>sMP</td>
      <td>10</td>
    </tr>
  </table>
</sticky>

*Intervall:* 3/Jahr

-----
---++ Lehrveranstaltungselemente

%STARTSECTION{"Vorlesung / Übung"}%
---+++ <u>Vorlesung / Übung</u>

---++++ Lernziele 
---+++++ Lerninhalte (Kenntnisse)
   * Mathematische Grundlagen der Theoretischen Informatik: Mengen undSprachen, Elementare Aussagen- und Prädikatenlogik, ElementareGraphentheorie, Asymptotische Analyse, Laufzeitanalysen
   * Einführung Theoretische Informatik mittels Endlicher Automaten: Berechnungen,Konfigurationen, Akzeptierte Sprache, Determinismus und Nichtdeterminismus,Grammatik, reguläre Grammatik, reguläre Ausdrücke, Äquivalenz der Konzepte
   * Typ2-,Typ1-, Typ0-Sprachen: kontextfreie, kontextsensitive, rekursiv-aufzählbare Sprachen, Chomsky-Hierarchie, das Wortproblem
   * Turingmaschinen: Varianten von Turingmaschinen und deren Äquivalenz, Äquivalenz von linear beschränkten Automaten und Typ1-Grammatika,   Äquivalenz von Turingmaschinen und Typ0-Grammatika
   * Berechenbarkeit: Turing-, While- und Loop-Berechenbarkeit, ChurchscheThese, Ackermannfunktion, universelle Turingmaschinen, Gödelnummereiner Turingmaschine
   * Entscheidbarkeit: entscheidbare und semi-entscheidbare Probleme,Aufzählbarkeit, Reduktion von Problemen, das Halteproblem,unentscheidbare Probleme, das Theorem von Rice 
   * Komplexitätstheorie und Algorithmik hartnäckiger Probleme: Komplexität vonAlgorithmen, Komplexitätsklassen, P=NP Problem, NP-vollständige Probleme,Approximationsalgorithmen, Lokale Suche

---+++++ Fertigkeiten
   * Die Studierenden beherrschen den Umgang mit Typ2-, Typ1- und Typ0-Sprachen sowie die zugehörigen  Maschinenmodelle
   * Sie können mit formalen Modellen der Infomatik arbeiten
   * Sie können die Kenntnisse der Berechenbarkeits-, Entscheidbarkeits- und Komplexitätstheorie auf praktische Probleme anwenden
   * Sie sind in der Lage den Algorithmenbegriff zu präzisieren, die Tragweite von Algorithmen zu beschreiben und die Komplexität von Algorithmen zu bestimmen  
   * Sie sind in der Lage die prinzipielle Lösbarkeit algorithmischer Probleme zu untersuchen


---++++ Begleitmaterial 
   * elektronische Vortragsfolien zur Vorlesung
   * elektronische Übungsaufgabensammlung


---++++ Besondere Voraussetzungen 
   * keine


---++++ Besondere Literatur 
   * keine


---++++ Besonderer Kompetenznachweis 
<sticky>
  <table border="1" cellpadding="2" cellspacing="0">
    <th colspan="2">Form</th>
    <tr>
      <td>bÜA</td>
      <td>Präsenzübung</td>
    </tr>
  </table>
</sticky>

<sticky>
  <table border="1" cellpadding="2" cellspacing="0">
    <th colspan="2">Beitrag zum LV-Ergebnis</th>
    <tr>
      <td>bÜA</td>
      <td>unbenotet</td>
    </tr>
  </table>
</sticky>

*Intervall:* 1/Jahr

%ENDSECTION{"Vorlesung / Übung"}%




%ENDSECTION{"no_toc"}%
Topic-Revision: r5 - 11 Jan 2016, GeneratedContent
F07_Studium
Einloggen oder Registrieren
Webs
F07_Studium
System
Das Urheberrecht © liegt bei den mitwirkenden Autoren. Alle Inhalte dieser Kollaborations-Plattform sind Eigentum der Autoren.
Ideen, Anfragen oder Probleme bezüglich Foswiki? Feedback senden