Zur Seitennavigation oder mit Tastenkombination für den accesskey-Taste und Taste 1 
Zum Seiteninhalt oder mit Tastenkombination für den accesskey und Taste 2 
  1. Semester: WS 2017/18
  2. Hilfe
  3. Sitemap
  4. FAQ
Switch to english language
Startseite    Anmelden     
Logout in [min] [minutetext]

Strukturbaum
Keine Einordnung ins Vorlesungsverzeichnis vorhanden. Veranstaltung ist aus dem Semester SS 2006 , Aktuelles Semester: WS 2017/18
  • Funktionen:
  • Druckversion
Theoretische Grundlagen der Informatik    Sprache: deutsch    Keine Belegung möglich
Pflichtvorl./Pflichtüb.     SS 2006     6 SWS     jedes 2. Semester     ECTS-Punkte: 9     http://www.inf.uni-konstanz.de/algo/lehre/ss06/ti/
   Fachbereich: FB Informatik und Informationswissenschaft    
   Teilnehmer/-in  erwartet : 70 
 
   Studiengang   Information Engineering, BSc,
   Dozent/in:   Brandes
 
   Gruppe:
Vorlesung   
 
   Termin: Fr   12:00  -  13:30    wöchentl.
Beginn : 03.05.2006    Ende : 28.07.2006
      Raum :   A 703   A  
  am 5.5. verlegt nach R711
 
  Mi   08:30  -  10:00    wöchentl.       Raum :   A 703   A  
 
 
 
   Termin: Mo   14:00  -  16:00    Einzel
Beginn : 31.07.2006    Ende : 31.07.2006
      Raum :   A 703   A  
  KLAUSUR, Ersttermin
 
 
   Gruppe:
Übung   
 
   Termin: Mo   10:15  -  11:45    wöchentl.       Raum :   H 305   H  
  Mo   14:15  -  15:45    wöchentl.       Raum :   D 433   D  
 
 
   Kommentar: Formale Sprachen und Automatentheorie
- Chomsky-Hierarchie (reguläre, kontextfreie, Typ0-Sprachen, reguläre Ausdrücke)
- Grammatiken (Typen, Eindeutigkeit, Abgeschlossenheit)
- Automatenmodelle (endliche Automaten, Kellerautomaten, Turingmaschinen)
Entscheidbarkeit und Berechenbarkeit
- Entscheidbarkeit, Aufzählbarkeit
- Universelle Turingmaschine, Diagonalisierung, Halteproblem
- Berechenbarkeit, $\mu$-rekursive Funktionen, Church/Turing-These
Komplexitätstheorie
- Optimierungs- und Entscheidungsprobleme
- Codierung
- Klassen P und NP, NP-Vollständigkeit
- Parametrisierte Komplexität
 
   Literatur: I. Wegener: "Theoretische Informatik - eine algorithmenorientierte Einführung", B. G. Teubner Verlag, 2. Aufl. 1999

U. Schöning: "Theoretische Informatik - kurzgefasst", Spektrum Akademischer Verlag, 4. Aufl. 2001

J. E. Hopcroft, R. Motwani, J. D. Ullman: "Einführung in die Automatentheorie, formale Sprachen und Komplexitätstheorie", Pearson Studium, 2. Aufl. 2002

M. R. Garey, D. S. Johnson: "Computers and Intractability: A Guide to the Theory of NP-Completeness", Freeman, 1979
 
   Bemerkung: Daten für den Leistungsnachweis (s.a. 'Räume und Termine'):

Klausur "Theoretische Grundlagen der Informatik"
1. Termin: Mo., 31.07., 14.00-16.00 Uhr, A 703
2. Termin: Di., 17.10., 10.00-12.00 Uhr, F 429

DAS EIGENTLICHE FELD "LEISTUNGSNACHWEIS" IST IRREPARABEL DEFEKT - BITTE IGNORIEREN. MASSGEBEND IST DIESER EINTRAG.
 
   Leistungsnachweis: Klausur (120min)
 
 
STUDIS    Anzahl aktueller Nutzer/-innen: 71 Haben Sie Anregungen, Fragen, Lob oder Kritik zum LSF?
Dann schreiben Sie uns!
Impressum
Datenschutzerklärung