- Titel: Algorithmen und Datenstrukturen
- Autor: Robert Giegerich und Jens Stoye
- Organisation: UNI BIELEFELD
- Seitenzahl: 10
Inhalt
- Einleitung
- Prolog
- Was ist Informatik
- Überblick
- Was ist Informatik
- Algorithmen und Datenstrukturen
- Robert Giegerich und Jens Stoye
- Lecture U Bielefeld Winter
- Robert Giegerich und Jens Stoye AD Vorlesung Winter
- Wir spielen ein Spiel
- n log n Anzahl Fragen log n
- Noch interessantere Varianten desselben Spiels
- Lügen Lüge leere Menge x in Ja Nein
- x in Ja Nein
- Siehe Text von Kapitel
- Technische und Theoretische Praktische und Angewandte Informatik
Vorschau
Einleitung
Prolog
Was ist Informatik
¨ Uberblick
Algorithmen und Datenstrukturen 1
Robert Giegerich und Jens Stoye
Faculty of Technology Bielefeld University stoye@TechFak.Uni-Bielefeld.DE
Lecture, U. Bielefeld, Winter 2007/2008
Robert Giegerich und Jens Stoye A&D 1 Vorlesung Winter 2007/2008
Bielefeld University
Einleitung
Prolog
Was ist Informatik
¨ Uberblick
Kapitel 1: Einleitung
1.1 Prolog 1.2 Was ist Informatik? 1.3 Technische und Theoretische, Praktische und Angewandte Informatik ¨ 1.4 Uberblick
Robert Giegerich und Jens Stoye A&D 1 Vorlesung Winter 2007/2008
Bielefeld University
Einleitung
Prolog
Was ist Informatik
¨ Uberblick
Wir spielen ein Spiel
Gegeben: Grundmengen an ahlen {1, 2, . . . n} =: S n = 100. Gesucht: Eine bestimmte (geheime) ahl x ∈ S. (1) Erlaubt: Fragen der Art ist x ≤ a“? ” (A) Was ist eine optimale Strategie? → bin¨re Suche a (B) Wie viele Fragen ben¨tigt man maximal, bis die ahl o x eindeutig bestimmt ist? → log2 n (Dies ist die genaue Berechnung. Im Laufe der Vorlesung werden wir sehen, dass man dies auch auf einfachere Weise formulieren kann.)
Robert Giegerich und Jens Stoye A&D 1 Vorlesung Winter 2007/2008 Bielefeld University