Art und Inhalt

Theorie der Zeichenketten

• 1. VL: Formale Grammatiken
  1. Das Konzept der formalen Sprache verstehen
  2. Probleme als formale Sprachen formulieren können
  3. Syntax von kontextfreien und regulären Grammatiken kennen
  4. Ableitungen bilden können und die erzeugte Sprache angeben können
  5. Probleme mittels formalen Grammatiken beschreiben können
• 2. VL: Endliche Automaten
  1. Funktionsweise von endlichen Automaten verstehen
  2. Formale Sprachen mittels endlicher Automaten entscheiden können
  3. Endliche Automaten implementieren können
  4. Einschätzen können, ob eine Sprache regulär ist
• 3. VL: Pattern-Matching
  Leitbild: Suchen und Ersetzen für Fortgeschrittene
  1. Pattern-Matching-Algorithmen kennen und implementieren können.

Theorie der schwierigen Probleme

• 4. VL: Komplexität von Problemen und Algorithmen
  Leitbild: Werden wir die Lösung in einer Sekunde oder in einem Jahr haben?
  1. Wichtige Ressourcemaße verstehen und erklären können
  2. Das Laufzeitverhalten der wichtigsten Algorithmen kennen
  3. Das Laufzeitverhalten einfacher Programme abschätzen können
  4. Die Gruppierung von Problemen nach groben Laufzeitklassen verstehen
• 5. VL: Optimierungsprobleme
  Leitbild: Von »Geht’s?« zu »Wie geht’s am besten?»
  1. Die Konzepte Optimierungsproblem, Lösung und Güte verstehen
  2. Probleme als Optimierungsproblem formulieren können
  3. Schwierige und leichte Optimierungsprobleme kennen
• 6. + 7. VL: Approximationen und Heuristiken
  Leitbild: Wie liefert man eine Pizza in 30 Minuten?
  1. Das Konzept der approximativen Lösung verstehen
  2. Das Konzept der heuristischen Lösung verstehen
  3. Lösungsverfahren für konkrete Probleme kennen

Große Daten- und Rechnernetze

• 8. VL: Funktion und Aufbau von Rechnernetzen
  Leitbild: Sollte mein Projekt Internet- oder LAN-basiert sein?
  1. Arten von Rechnernetzen kennen.
  2. Übertragungsmethoden kennen.
  3. Konzept des Kommunikationsprotokolls kennen und verstehen.
  4. Leistungsfähigkeit von verschiedenen Netzarten beurteilen können.
• 9. +10. VL: Das Internet
  Leitbild: Der Cyberspace – Chancen und Risiken
  1. Aufbau und Funktionsweise des Internet und des WWW kennen.
  2. Vorteile netzbasierter Projekte und Ansätze kennen.
  3. Gefahren (Viren, Würmer, Trojaner) kennen und Gegenmaßnahmen ergreifen können.
• 11. + 12. VL: Datenbanken
  Leitbild: Wie speichert man eine Milliarde Molekülstrukturen – und wie findet man sie wieder?
  1. Das Konzept der Datenbank kennen und verstehen
  2. Das relationale Datenbankmodell kennen
  3. Daten mittels des relationalen Modells modellieren können
  4. Einfache SQL-Ausdrücke kennen und einsetzen können.
• 13. VL: Große Informations- und Datenmengen
  Leitbild: Datenmeer
  1. Verlustbehaftete und -freie Datenkompressionsverfahren kennen, insbesondere für biologische und biochemische Daten
  2. Konzept des Dataminings kennen, insbesondere für biologische und biochemische Daten.

Schluss

• 14. VL: Zusammenfassung, Ausblick, Abschlussevaluation

Die Vorlesung soll sich inhaltlich auf Teile des Buches »Einführung in die Informatik« vom Gumm und Sommer stützen. Dieses Lehrbuch deckt das vorgeschlagene Curriculum weitgehend ab. Bei Themengebieten, die nicht abgedeckt sind, werden entweder Lehrbücher aus dem Bestand der Bibliothek zugrunde gelegt werden oder ein spezielles Skript für diese speziellen Vorlesungen erstellt werden.

Vorlesung

1. Indivduelle Bearbeitung der ein- bis zweiwöchentlichen Übungsblätter. Auf allen bis auf zwei Übungsblättern muss die Hälfte der möglichen Punkte erreicht werden.
2. Bestehen der Prüfung am Semesterende. Die Prüfungsnote ergibt die Note für die Kreditpunkte.
3. Halten eines 5-minütigen Referats in einem Tutorium.

• 02. Vorlesung, 13.04.06 (Druckversion)
• 03. Vorlesung, 20.04.06 (Druckversion)
• 04. Vorlesung, 27.04.06 (Druckversion)
• 05. Vorlesung, 04.05.06 (Druckversion)
• 06. Vorlesung, 11.05.06 (Druckversion)
• 07. Vorlesung, 18.05.06 (Druckversion)
• 08. Vorlesung, 01.06.06 (Druckversion)
• 09. Vorlesung, 08.06.06 (Druckversion)
• 10. Vorlesung, 15.06.06 (Druckversion)
• 11. Vorlesung, 22.06.06 (Druckversion)
• 12. Vorlesung, 06.07.06 (Druckversion)
• 13. Vorlesung, 13.07.06 (Druckversion)

Übung

1. 50h für die Vor- und Nachbereitung und das Lösen der Übungsaufgaben.
2. 10h Prüfungsvorbereitung.

• 1. Übung, Abgabetermin 04.05.06
  Musterlösung für den Automaten
• 2. Übung, Abgabetermin 11.05.06
  Java-Methode compute_max_distance zum Herunterladen
  Java-Programm HammingTest zum Herunterladen
• 3. Übung, Abgabetermin 01.06.06
• 4. Übung, Abgabetermin 22.06.06
• 5. Übung, Abgabetermin 29.06.06
  Das Programm zz.java zum Herunterladen
• 6. Übung, Abgabetermin 13.07.06
• 7. Übung, Hinweise für das 7. Übungsblatt: A9.java, Automat_UE7_A6 , UE7_A5

Referate

Jeder Student muss im Semester einmal ein Kurzreferat halten. Die Referate können alleine gehalten werden (5 Minuten) oder zu zweit (10 Minuten), wobei die Zeitobergrenze bitte einzuhalten ist. Die Themen werden mindestens eine Woche vorher verteilt.

• 20. April 2006
  

  Thema: Eine Grammatik zu einer einfachen Sprache.

  Inhalt: Das Alphabet sei {A,C,G,U}. Die Sprache enthält alle Worte folgender Gestalt: Sie beginnen mit beliebigen Folge von Symbolen aus dem Alphabet, dann kommen die drei Symbole AUG, dann kommen beliebige Symbole, dann kommt eines der Worte UAA, UGA oder UAG, dann kommen wieder beliebige Symbole. Im Vortrag soll eine Grammatik für diese Sprache vorgestellt und erklärt werden.

• 27. April 2006
  

  Thema: Einführung zur Syntax von HTML.

  Inhalt: HTML ist die Standardsprache des WWW. Im Vortrag soll anhand von Beispielen gezeigt werden, wie der Quelltext von HTML-Seiten aufgebaut ist. Der Vortrag dient als Vorbereitung für das Tutorium, in dem in Gruppen eine Grammatik für HTML erstellt werden soll.

• 04. Mai 2006
  

  Thema: Laufzeitanalyse eines Sortieralgorithmus

  Inhalt: Für einen beliebigen Sortieralgorithmus (z.B. Selectionsort oder Mergesort) soll eine kurze Laufzeitanalyse vorgestellt werden. Dazu könnte man den Algorithmus nochmal kurz wiederholen und dann erklären, wie sich die Laufzeit abschätzen lässt.

• 11. Mai 2006
  

  Thema: Der Dijkstra-Algorithmus

  Inhalt: Wie arbeitet der Algorithmus, der entscheidet, ob es in einem Graphen G einen Pfad von s nach t gibt. An diesem Beispiel kann man den Unterschied diskutieren, ob ein Algorithmus nur ein Entscheidungsproblem löst oder auch die Lösung eines Optimierungsproblems liefert.

• 18. Mai 2006
  

  Thema: DNA-Teilstücke puzzeln

  Inhalt: Es geht darum, DNA-Teilstücke überlappend zu einem längeren DNA-Strang zusammenzusetzen. Wie kann man die Fragestellung formalisieren? Wie kann man es algorithmisch lösen?

• 1. Juni 2006
  

  Thema: Die Graphik-Beschreibungssprache SVG

  Inhalt: Eine kurze Einführung zu SVG (Scalable Vector Graphics). So wie man HTML benutzt, um Text zu beschreiben, kann man SVG benutzen, um Graphiken zu beschreiben. Einen Überblick bietet zum Beispiel die deutsche Wikipedia-Seite.

• 8. Juni 2006
  

  Thema: Digital Divide

  Inhalt: Eine kurzer Überblick über das Phänomen des Digital Divide. Es sollen Fakten dazu vorgestellt werden, also die Anzahl der Internetanschlüsse in verschiedenen Ländern, die Anzahl der Webseiten, die Menge des E-Mail Verkehrs, etc.

• 15. Juni 2006
  

  Thema: Denial-of-Service-Angriffe im Internet

  Inhalt: Die Angriffsmethode "Denial of Service (DoS)" soll vorgestellt werden. Bei dieser Methode wird versucht, einen Server davon abzuhalten, seiner Aufgabe (Service) nachzukommen. Eine Methode ist eine verteilte DoS-Attacke, bei der viele von Hackern übernommene Rechner einen Server durch Überflutung mit Anfragen zum Erliegen bringen. Bekannte Beispiele solcher Attacken sollen genannt werden.

• 22. Juni 2006
  

  Thema: ssh

  Inhalt: Überblick des Programmes ssh, seiner Optionen und seiner Einsatzmöglichkeiten.

• 27. Juni 2006
  

  Thema: Tabellen in der Ensemble Datenbank

  Inhalt: Eine Übersicht über die Tabellen, die in der Ensemble Datenbank vorhanden sind und wie diese zusammenhängen.

• 13. Juli 2006
  

  Thema: Typen in SQL

  Inhalt: Attribute in SQL-Datenbanken können verschiedene Typen haben wie "integer" oder "char". Im Vortrag werden die zur Verfügung stehenden Typen vorgestellt.

Klausur