50 years Univerity of Lübeck

Institute for Theoretical Computer Science

SS 2006 – Informatik B



Type and Content

Title: Informatik B
Host: Tantau
Classification: Bachelor-Studiengang MLS 6. Semester
Conentent:

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
Puffer: 1VL
Literature:

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.


Lecture

Host: Tantau
Hours: 2 SWS, 4 ECTS
Für die Erlangung der 4 Kreditpunkte müssen folgende Leistungen erbracht werden:
  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.
Dates: Do. 10.00h-12.00h, Raum R3
Vorlesungkarte: Vorlesungskarte
Skripte:
Evaluation: 11.05.2006
WS2005/06 und SS 2006

Exercise

Host: Tantau, Nickelsen, Balbach
Hours: 2 SWS
Veranschlagter Zeitaufwand
  1. 50h für die Vor- und Nachbereitung und das Lösen der Übungsaufgaben.
  2. 10h Prüfungsvorbereitung.
Dates: Gruppe 1: Do. 12.00h-14.00h Seminarraum Informatik 2 (Cook)
Gruppe 2: Do. 12.00h-14.00h Seminarraum Informatik 3 (Karp)
Gruppe 3: Do. 12.00h-14.00h R1
Übungsblätter:

Presentation

Themen und Daten

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.


Written test

Klausurergebnisse Einsicht (Zugang nur über Uni-Rechner)
Klausureinsicht: 27.07.06, 11-12 Uhr, Raum 21 (ITCS-Seminarraum)
Nachklausur: Bitte per Email anmelden: tantau_at_tcs.uni-luebeck.de
Musterlösung: Zur Musterlösung