- Titel: Berechenbarkeit und Komplexität
- Organisation: UNI HAMBURG
- Seitenzahl: 45
Inhalt
- Zielgruppe
- "Ubungsgruppen
- Scheinkriterien
- Skript
- "Agyptische Multiplikation
- "Agyptische Multiplikation (2)
- "Agyptische Multiplikation (3)
- Korrektheit des Verfahrens
- Problemtypen
- Entscheidungsprobleme
- Suchprobleme
- Optimierungsprobleme
- Abz"ahlungsprobleme
- Anzahlprobleme
- Der Begriff des {lue Algorithmus} und die {lue Turing-Maschine}
- Algorithmus
- Algorithmus (2)
- Algorithmus (3)
- Berechenbarkeit
- Beschreibungsformen f"ur Alg.
- Beispiel
- Beispiel (2)
- Beispiel (3)
- Die Gau"ssche Formel
- Beweis der Gau"sschen Formel
- Beweis der Gau"sschen Formel (2)
- Beweis der Gau"sschen Formel (2)
- Probleml"osung
- Die Landau- oder O-Notation
- Anschaulich
- O-Notation
- O-Notation (2)
- Zusammenfassung
- Beispiele zur O-Notation
- Die Funktionsklassen $Omega (g)$
- Funktionsklassen $Theta (g)$
- Beispiel zu $Theta (g)$
- Weitere Funktionsklassen
- Zusammenh"ange
- kanonische Erweiterung
- Absch"atzung
- log-Funktion
- Effizienz
- Ausblick
Vorschau
F3 — Berechenbarkeit und Komplexit¨t a
Matthias Jantzen (nach Vorlage von Berndt Farwer) Fachbereich Informatik AB Theoretische Grundlagen der Informatik“ (TGI) ” Universit¨t Hamburg a jantzen@informatik.uni-hamburg.de
F3’03/04 – p.1/??
ielgruppe
1. Informatik (3. Semester) 2. Wirtschaftsinformatik (3. Semester) 3. Allgemeine Ingenieurswissenschaften, Informatikingenieurwesen und TECMA (5. Semester) Wichtig: Beginn 12:15 Ende 13:45
F3’03/04 – p.2/??
¨ Ubungsgruppen
. . . gibt es nur für Wirtschaftsinformatiker und Studierende der TU-Harburg! Mo 12–13 C-101 Mo 13–14 C-101 Do 14–15 C-101 Do 15–16 C-101 Do 16–17 C-101 Heiko Rölke Heiko Rölke Mathias Jantzen Michael Köhler Michael Köhler
Die Aufgaben sind aber für jede(n) im WEB abrufbar, und sollten (am Besten in AG’s) von allen bearbeitet werden!