INFORMATIK
TECHNISCHE
INFORMATIK
Prozessoren
Robotik
Schaltkreise
Peripherie
Maus
Bildschirm
Drucker
Tastatur
Netzwerkkarte
Netzwerke
Internet
Funk
Bluetooth
Wirless LAN
Kabel
Telefon
ISDN
DSL
THEORETISCHE
INFORMATIK
Typtheorie
Maschinenmodelle
K
¨
unstliche
Intelligenz
Automatentheorie
NFAs
DFAs
Theorie
formaler Sprachen
Spachen
Grammatiken
regul
¨
ar
kontextfrei
regul
¨
are
Ausdr
¨
ucke
Komplexit
¨
ats-
theorie
Ressourcen
Klassen
PRAKTISCHE
INFORMATIK
Algorithmen
Graph-
algorithmen
geometrische
algorithmische
Methoden
Dynamische
Programme
Rekursion
Greedy-
Heuristiken
Back-
tracking
Approxi-
mation
Sortieren
Suchen
Optimierung
Datenstrukturen
zusammen-
gesetzte
Graphen
B
¨
aume
Hashing
Arrays
Listen
einfache
Strings
Zahlen
Programmier-
sprachen
imperativ
C
Assembler
Pascal
objektorientiert
Java
C++
Smalltalk
funktional
ML
Scheme
logisch
Prolog
Softwaretechnik
Modellierung
Strukturierung
Modulari-
sierung
Planung
ANGEWANDTE
INFORMATIK
Datenbanken
Theorie
ER-
Diagramme
Relationen-
Algebren
Datenbank-
Sprachen
SQL
Datenbank-
Systeme
DB2
MySQL
Anwendung
Mail
SPSS
Matlab
Word
Betriebssysteme
Windows
Unix
Shells
WWW
ELEKTROTECHN I K
MASCHINENBAU
LINUGISTIK
MATHEMATIK
WIRTSCHAFT
Vorlesungskarte zu den Vorlesungen
Informatik A f
¨
ur Molecular Life Sciences 2006
Informatik B f
¨
ur Molecular Life Sciences 2007
Veranstaltungsziele
– Informationsverarbeitende Systeme theoretisch verstehen
– Informationsverarbeitende Systeme in Forschungs- und
Entwicklungsprojekten benutzen k
¨
onnen
– Algorithmen und Datenstrukturen verschiedenen Projektbed
¨
urfnissen
anpassen k
¨
onnen
– Vorbereitung auf vertiefende Informatikveranstaltungen
D
P
∞
i=1
1
n
2
=
π
2
6
Satz
Subjekt
Das
Sein
ist.
A1 Information und Daten
– Die bin
¨
are Speicherform verschiedener Daten
kennen und verstehen
– Wichtige Einheiten von Information kennen und
die Speichergr
¨
oße von Daten absch
¨
atzen
k
¨
onnen
– Beliebige Daten kodieren k
¨
onnen
– Das Konzept der Datenkompression kennen und
verstehen
A2 Computer-Hardware
– Grundlegende Rechnerarchitekturen kennen
– Klassen von Computern kennen und ihre
Leistungsf
¨
ahigkeit absch
¨
atzen k
¨
onnen
– Den prinzipiellen Aufbau von Computern
beschreiben k
¨
onnen
– Die wichtigsten Hardwarekomponenten kennen
und ihre Leistungsf
¨
ahigkeit absch
¨
atzen k
¨
onnen
A3 Computer-Software
– Ein-Prozess-Systeme und das EVA-Prinzip
verstehen
– Mehr-Prozess-Systeme verstehen
– Programme als Instruktionsfolgen begreifen
– Verschiedene Arten von Software benennen und
unterscheiden k
¨
onnen
A5 Shells
– Unix- und Programm-Shells benutzen k
¨
onnen
– Wichtige Unix-Kommandos kennen
– Einfache Shell-Skripte erstellen k
¨
onnen
A4 Betriebssysteme
– Aufgaben von Betriebssystemen kennen
– Konzepte der Benutzer-, Prozess-, und
Dateiverwaltung kennen
– Mit Datein und Dateirechten umgehen k
¨
onnen
– Begriff der Shell kennen
A6 Der Algorithmusbegriff
– Den Begriff des Algorithmus verstehen
– Einfache L
¨
osungsideen als Algorithmen
formulieren k
¨
onnen
– Probleme spezifizieren k
¨
onnen
– Programmiersprachen als Kommunikationsmittel
f
¨
ur Algorithmen begreifen
– Das Konzept des
¨
Ubersetzers verstehen
A7 Imperative Programmierung
– Zuweisungen verstehen und benutzen k
¨
onnen
– Grundlegende Kontrollstrukturen verstehen und
benutzen k
¨
onnen
– Algorithmen als imperative Java-Programme
formulieren k
¨
onnen
A8 Die Programmiersprache Java
– Syntax des imperativen Kerns von Java
beherrschen
– Java-Programme selbstst
¨
andig erstellen k
¨
onnen
– Java-Programme
¨
ubersetzen und testen k
¨
onnen
A9 Elementare Datentypen
– Variablendeklarationen verstehen und benutzen
k
¨
onnen
– Elementare Datentypen von Java kennen
– Typkorrektheit und Typefehler verstehen
A10 Zeichenketten
– Zeichenketten (Strings) als Datentypen kennen
– Einfache Stringalgorithmen kennen und
implementieren k
¨
onnen
– Fortgeschrittene Stringalgorithmen kennen und
implementieren k
¨
onnen
A11 Arrays (Felder)
– Konzept des Arrays verstehen
– Java-Syntax von Arrays beherrschen
– Java-Programme mit Array-Nutzung
implementieren k
¨
onnen
A12 Scoping
– Scoping verstehen und anwenden k
¨
onnen
– Die Speicherung von Variablen verstehen
A13 Modularisierung im Kleinen
– Das Konzept des Unterprogramms/Methode
verstehen und anwenden k
¨
onnen
– Java-Syntax der Modularisierung auf
Methodenebene beherrschen
A14 Suchalgorithmen
– Lineare Suche verstehen und implementieren
k
¨
onnen
– Bin
¨
are Suche verstehen und implementieren
k
¨
onnen
– Laufzeit der Verfahren vergleichen k
¨
onnen
– Absch
¨
atzen k
¨
onnen, wann sich Vorsortierung
lohnt
A15 Sortieralgorithmen
– Arten von Sortierproblemen kennen
– Bubble-Sort, Insertion-Sort, Selection-Sort
verstehen und implementieren k
¨
onnen
A16 Laufzeit von Algorithmen
– Wichtige Ressourcemaße verstehen und erkl
¨
aren
k
¨
onnen
– Das Laufzeitverhalten der wichtigsten
Algorithmen kennen
– Das Laufzeitverhalten einfacher Programme
absch
¨
atzen k
¨
onnen
– Die Gruppierung von Problemen nach groben
Laufzeitklassen verstehen
A17 Einf
¨
uhrung zur Rekursion
– Das Konzept der Rekursion verstehen
– Rekursive Methoden implementieren k
¨
onnen f
¨
ur
einfache Probleme
A18 Rekursion und schnelles Sortieren
– Merge-Sort verstehen und implementieren
k
¨
onnen
– Quick-Sort verstehen und implementieren k
¨
onnen
A19 Modularisierung im Großen
– Das Konzept des Top-Down-Entwurf verstehen
und anwenden k
¨
onnen
– Das Konzept der Klassen- und Modulbildung
verstehen
A20 Klassen und Modellierung
– Konzept der Klasse verstehen
– Modellierung als Methodik kennen
– Statische Klassenmodelle von
Anwendungsszenarien erstellen k
¨
onnen
A21 Klassen und Objekte
– Lebenszyklus von Objekten kennen
– Neue Datentypen deklarieren und benutzen
k
¨
onnen
– Nichtstatische Methoden kennen und benutzen
k
¨
onnen
– Java-Syntax f
¨
ur Objekte kennen
A22 Listen als Datenstruktur
– Das Konzept der komplexen Datenstruktur
verstehen
– Die Liste als Datenstruktur verstehen und in Java
implementieren k
¨
onnen
– Den Unterschied zwischen Listen und Arrays
erkl
¨
aren k
¨
onnen
A23 Angewandte Listen
– Fortgeschrittene Arten von Listen kennen
– Vor- und Nachteile von Listen und Arrays
benennen k
¨
onnen
– Das Konzept der abstrakten Datenstuktur kennen
A24 B
¨
aume
– Das Konzept des (Such)Baumes verstehen
– (Such)B
¨
aume in Java implementieren k
¨
onnen
– Baumtraversierung kennen und implementieren
k
¨
onnen
A25 Suchb
¨
aume
– Suchb
¨
aume in Java implementieren k
¨
onnen
– 2-3-Suchb
¨
aumen kennen und verstehen
– Vor- und Nachteile von Arrays, Listen, einfachen
B
¨
aumen und fortgeschrittenen Suchb
¨
aumen
beurteilen k
¨
onnen
A26 Graphen
– Graphen als mathematische Objekte verstehen
– Daten und ihre Struktur mittels Graphen
modellieren k
¨
onnen
– Die Datenstruktur des Graphen verstehen und
implementieren k
¨
onnen
A27 Graphalgorithmen
– Einige einfache und schwierige Graphprobleme
kennen
– Arten der Graphtraversierung kennen
– Einen K
¨
urzeste-Wege-Algorithmus kennen
B1 Datenbanken
– Das Konzept der Datenbank kennen und
verstehen
– Das relationale Datenbankmodell kennen
– Daten mittels des relationalen Modells
modellieren k
¨
onnen
B2 Relationenalgebren
– Konzept der Relation-Algebra kennen
– Anfragen mittels Operationen formulieren
k
¨
onnen
– Joins verstehen und anwenden k
¨
onnen
B3 SQL
– Syntax von SQL beherrschen
– SQL-Queries erstellen k
¨
onnen
– Mit Datenbanken mittels einer SQL-Shell
kommunizieren k
¨
onnen
B4 Das World-Wide-Web
– Aufbau des WWW kennen
– Aufbau von HTML kennen
– Unterschied zwischen Web-Clients und
Web-Servern kennen
– Eigene Webseiten erstellen k
¨
onnen
B5 Rechnernetze und das Internet
– Konzept des Kommunikationsprotokolls kennen.
– OSI-Schichtenmodell kennen.
– Unterschied zwischen LAN und Internet kennen.
– Vor- und Nachteile netzbasierter Projekte und
Ans
¨
atze beurteilen k
¨
onnen.
B6 IT-Sicherheit
– Bedrohungsszenarien der Sicherheit von
IT-Systemen kennen und einsch
¨
atzen k
¨
onnen
– Schutzmaßnahmen f
¨
ur die Sicherheit von
IT-Systemen kennen und ergreifen k
¨
onnen
B7 Formale Grammatiken
– Das Konzept der formalen Sprache verstehen
– Probleme als formale Sprachen formulieren
k
¨
onnen
– Syntax von kontextfreien und regul
¨
aren
Grammatiken kennen
– Ableitungen bilden k
¨
onnen und die erzeugte
Sprache angeben k
¨
onnen
– Probleme mittels formalen Grammatiken
beschreiben k
¨
onnen
B8 Endliche Automaten
– Funktionsweise von endlichen Automaten
verstehen
– Formale Sprachen mittels endlicher Automaten
entscheiden k
¨
onnen
– Endliche Automaten implementieren k
¨
onnen
– Einsch
¨
atzen k
¨
onnen, ob eine Sprache regul
¨
ar ist
B9 Regul
¨
are Ausdr
¨
ucke
– Konzept des regul
¨
aren Ausdrucks verstehen
– Probleme als regul
¨
are Ausdr
¨
ucke beschreiben
k
¨
onnen
– Verh
¨
altnis von regul
¨
aren Ausdr
¨
ucken und
endlichen Automaten kennen
B10 Optimierungsprobleme
– Probleme als Entscheidungsprobleme,
Funktionsprobleme und Optimierungsprobleme
formulieren k
¨
onnen
– Die Konzepte Optimierungsproblem, L
¨
osung und
Maße verstehen
– Schwierige und leichte Optimierungsprobleme
kennen
B11 Greedy-Heuristiken
– Das Konzept der heuristischen L
¨
osung verstehen
– Die Idee von Greedy-Heuristiken kennen
– Beispiele von Greedy-Heuristiken kennen
– Greedy-Heuristiken entwerfen k
¨
onnen
B12 Backtracking-Algorithmen
– Die Idee des Backtracking verstehen
– Backtracking-Algorithmen implementieren
k
¨
onnen
B13 Approximationsalgorithmen
– Das Konzept der approximativen L
¨
osung
verstehen
– L
¨
osungsverfahren f
¨
ur konkrete Probleme kennen
Oktober 2006November 2006Dezember 2006Januar 2007Februar 2007
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
23
24
25
26
27
30
31
21
22
28
29
1
2
3
6
7
8
9
10
13
14
15
16
17
20
21
22
23
24
27
28
29
30
4
5
11
12
18
19
25
26
1
4
5
6
7
8
11
12
13
14
15
18
19
20
21
22
2
3
9
10
16
17
23
24
25
26
27
28
29
30
31
8
9
10
11
12
15
16
17
18
19
22
23
24
25
26
29
30
31
13
14
20
21
27
28
1
2
3
4
5
6
7
1
2
5
6
7
8
9
3
4
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
Informatik-Einf
¨
uhrung
Java-Einf
¨
uhrung
Algorithmik
Modellierung
Datenstrukturen
Einf
¨
uhrung, Erwartungsabfrage
Information und Daten
Computer-Hardware
Computer-Software
Betriebssyteme
Shells
Der Algorithmus-Begriff
Imperative Programmierung
Programmiersprache Java
Elementare Datentypen
Zeichenketten
Arrays
Scoping
Modularisierung im Kleinen
Suchalgorithmen
Sortieralgorithmen
Laufzeit von Algorithmen
Einf
¨
uhrung Rekursion
Rekursives Sortieren
Modularisierung im Großen
Klassen und Modellierung
Klassen und Objekte
Listen I
Listen II
B
¨
aume I
B
¨
aume II
Graphen I
Graphen II
Zusammenfassung, Evaluation
April 2007 Mai 2007 Juni 2007 Juli 2007
1
2
3
4
5
6
9
10
11
12
13
16
17
18
19
20
23
24
25
26
27
30
7
8
14
15
21
22
28
29
1
2
3
4
7
8
9
10
11
14
15
16
17
18
21
22
23
24
25
28
29
30
31
5
6
12
13
19
20
26
27
1
4
5
6
7
8
11
12
13
14
15
18
19
20
21
22
25
26
27
28
29
2
3
9
10
16
17
23
24
30
2
3
4
5
6
9
10
11
12
13
16
17
18
19
20
1
7
8
14
15
21
22
23
24
25
26
27
28
29
30
31
Datenbanken
Internet und WWW
Theorie der Zeichenketten
Theorie schwieriger Probleme
Einf
¨
uhrung
Datenbanken
Relationen-Algebren
SQL
WWW
Internet
IT-Sicherheit
Grammatiken
Endliche Automaten
Regul
¨
are Ausdr
¨
ucke
Optimierung
Greedy-Heuristiken
Backtracking
Approximation
Zusammenfassung, Evaluation
Stand vom 8. Oktober 2006
www.tcs.uni-luebeck.de/pages/tantau/teaching.html – Lehre von Till Tantau
U
N
I
V
E
R
S
I
T
¨
A
T
Z
U
L
¨
U
B
E
C
K
I
N
S
T
I
T
U
T
F
¨
U
R
T
H
E
O
R
E
T
I
S
C
H
E
I
N
F
O
R
M
A
T
I
K
Theoretical
Computer
Science
1
LOGIK
BEWEISE
Kalk
¨
ule
Hilbertkalk
¨
ul
Resolutions-
kalk
¨
ul
Sequenzen-
kalk
¨
ule
nat
¨
urliches
Schließen
Axiomensysteme
Arten
Zermelo-
Fraenkel
Neumann-
Bernay-
G
¨
odel
Frege
Eigenschaften
Vollst
¨
andig-
keit
Korrektheit
Ableitungen
Modus ponens
Substitution
Erstellung
von Menschen
f
¨
ur Menschen
von Menschen
f
¨
ur Maschinen
von Maschinen
f
¨
ur Maschinen
LOGISCHE
SYSTEME
Aussagenlogik
Pr
¨
adikatenlogik
erster Stufe
zweiter Stufe
higher-
order logic
Intuitionistische
Logik
Gleichungslogik
Temporallogik
Modallogik
SYNTAX
Variablen
Aussagen-
variablen
Individuen-
variablen
Normalformen
disjunktive
Normalform
konjunktive
Normalform
Signaturen
Formeln
Junktoren
Quantoren
freie und
gebundene
Variablen
Terme
Konstanten-
symbole
Funktions-
symbole
Klammerung
Formale Sprachen
Grammatiken
Sprachen
Alphabete
und Strings
SEMANTIK
Modelle
Belegung
Auswertung
Modellrelation
Theorie
logische
Strukturen
Universum
Konstanten
Funktionen
Relationen
G
¨
ultigkeit
Wahrheitstafel
Belegung
logische
Folgerung
Implikation
¨
Aquivalenz
Tautologie
Kontradiktion
K
¨
UNSTLICHE
INTELLIGENZ
THEORETISCHE
INFORMATIK
FUNKTIONALE
PROGRAM-
MIERUNG
MENGENLEHRE
DATENBANKEN
TECHNISCHE
INFORMATIK
MODEL-CHECKING
IT-SICHERHEIT
Vorlesungskarte zur Vorlesung
Logik f
¨
ur Informatiker 2006
Veranstaltungsziele
– Verst
¨
andnis der Konzepte Syntax und Semantik an den Beispielen
Aussagen- und Pr
¨
adikatenlogik erwerben
– Formale Systeme und Beweissysteme anwenden k
¨
onnen
– Methoden der Logik in praktischen Anwendungen einsetzen k
¨
onnen
– Diskrete Problemstellungen formalisieren k
¨
onnen
Oktober 2006November 2006Dezember 2006Januar 2007Februar 2007
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
23
24
25
26
27
30
31
21
22
28
29
1
2
3
6
7
8
9
10
13
14
15
16
17
20
21
22
23
24
27
28
29
30
4
5
11
12
18
19
25
26
1
4
5
6
7
8
11
12
13
14
15
18
19
20
21
22
2
3
9
10
16
17
23
24
25
26
27
28
29
30
31
8
9
10
11
12
15
16
17
18
19
22
23
24
25
26
29
30
31
13
14
20
21
27
28
1
2
3
4
5
6
7
1
2
5
6
7
8
9
3
4
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
Einf
¨
uhrung
Aussagenlogik
Modellierung
Pr
¨
adikatenlogik
Einf
¨
uhrung, Erwartungsabfrage
Syntax versus Semantik
Grammatiken
Syntax
Semantik
Folgerungsbegriff
Kalk
¨
ule
Vollst
¨
andigkeit
E/R-Modelle
Syntax I
Semantik I
Syntax und Semantik II
Kalk
¨
ule
Zusammenfassung, Evaluation
1 Syntax versus Semantik
– Die Begriffe Syntax und Semantik erkl
¨
aren
k
¨
onnen
– Syntaktische und semantische Elemente
nat
¨
urlicher Sprachen und von
Programmiersprachen benennen k
¨
onnen
– Die Begriffe Alphabet und Wort kennen
– Objekte als Worte kodieren k
¨
onnen
2 Grammatiken
– Konzepte der formalen Sprache und der
formalen Grammatiken kennen
– Konzepte der Regel und der Ableitung
anwenden k
¨
onnen
– Syntax mittels formaler Grammatiken
beschreiben k
¨
onnen
3 Aussagenlogik: Syntax
– Konzepte der formalen Variable und formalen
Formel verstehen
– Die wichtigsten Junktoren kennen
– Sicherheitstechnische nat
¨
urlichsprachliche
Problemstellungen aussagenlogisch formalisieren
k
¨
onnen
4 Aussagenlogik: Semantik
– Konzept der Variablenbelegung kennen und
anwenden k
¨
onnen
– Die Begriffe der Erf
¨
ullbarkeit, Tautologie und
Kontradiktion kennen
– Aussagenlogische Formeln auf Eigenschaften
wie Erf
¨
ullbarkeit
¨
uberpr
¨
ufen k
¨
onnen
– Eigenschaften sicherheitstechnischer Systeme
belegen k
¨
onnen
5 Aussagenlogik: Folgerung
– Die Begriffe der logischen Folgerung und
¨
Aquivalenz kennen
– Formeln auf
¨
Aquivalenz und
Folgerungsbeziehungen untersuchen k
¨
onnen
– Normalformen kennen
– Formeln in Normalformen umwandeln k
¨
onnen
6 Aussagenlogik: Kalk
¨
ule
– Unterschied zwischen formalen und normalen
Beweisen kennen
– Resolutionskalk
¨
ul f
¨
ur die Aussagenlogik kennen
– Hilbertkalk
¨
ul f
¨
ur die Aussagenlogik kennen und
anwenden k
¨
onnen
7 Aussagenlogik: Vollst
¨
andigkeit
– Das Axiomensystem von Frege kennen
– Die Begriffe der Korrektheit und der
Vollst
¨
andigkeit kennen
– Vollst
¨
andigkeit und Korrektheit von
Axiomensystemen beweisen k
¨
onnen
8 E/R-Modelle
– Das E/R-Modell kennen
– Daten mittels des E/R-Modells modellieren
k
¨
onnen
– Konzept der Relationen-Algebra kennen
– Anfragen mittels Operationen formulieren
k
¨
onnen
– Joins verstehen und anwenden k
¨
onnen
9 Pr
¨
adikatenlogik: Syntax I
– Die ge
¨
anderte Bedeutung von Variablen
verstehen
– Die Begriffe Relationssymbol, Quantor und
Formel kennen und anwenden k
¨
onnen
– Den Unterschied zwischen freien und
gebundenen Variablen kennen
– Nat
¨
urlichsprachliche Problemstellungen
pr
¨
adikatenlogisch formulieren k
¨
onnen
10 Pr
¨
adikatenlogik: Semantik I
– Das Konzept der relationalen logischen Struktur
verstehen
– Den Begriff des Modells verstehen
– Den Begriff der Theorie kennen
– Den Folgerungs- und
¨
Aquivalenzbegriff der
Pr
¨
adikatenlogik verstehen
11 Pr
¨
adikatenlogik: Syntax und
Semantik II
– Die Begriffe Konstante, Funktion und Term
kennen und anwenden k
¨
onnen
– Das Konzept der logischen Signatur kennen und
anwenden k
¨
onnen
– Das Konzept der Substitution kennen und
anwenden k
¨
onnen
12 Pr
¨
adikatenlogik: Kalk
¨
ule
– Hilbertkalk
¨
ul f
¨
ur die Pr
¨
adikatenlogik kennen
– Aussage des G
¨
odel’schen Vollst
¨
andigkeitssatzes
verstehen
– Bedeutung des Satzes f
¨
ur die Mathematik und
die Informatik einsch
¨
atzen k
¨
onnen
Stand vom 9. Oktober 2006
www.tcs.uni-luebeck.de/pages/tantau/teaching.html – Lehre von Till Tantau
U
N
I
V
E
R
S
I
T
¨
A
T
Z
U
L
¨
U
B
E
C
K
I
N
S
T
I
T
U
T
F
¨
U
R
T
H
E
O
R
E
T
I
S
C
H
E
I
N
F
O
R
M
A
T
I
K
Theoretical
Computer
Science
1