Vorlesungsseite:- http://algo2.iti.uni-karlsruhe.de/AlgorithmenI.php
Mittsemesterklausur voraussichtlich am 8.6.2009, 14.00 Uhr
Hauptklausur voraussichtlich am 3.8.2009, 11.00 Uhr
aus dem Modulhandbuch:
Modul: Algorithmen I Modulschlüssel: [IN1INALG1]
Modulkoordination: Peter Sanders
Leistungspunkte (LP): 6
Erfolgskontrolle
Die Erfolgskontrolle besteht aus einer schriftlichen Prüfung gemäß § 4 Abs. 2 Nr. 1 SPO Bachelor Informatik sowie
dem Bestehen eines unbenoteten Übungscheins (Erfolgskontrolle anderer Art, § 4 Abs. 2 Nr. 3 SPO Bachelor
Informatik).
Die schriftliche Erfolgskontrolle gilt als bestanden, wenn die Zwischenprüfung im Laufe des Semesters (Dauer 90
Minuten) sowie die Abschlussprüfung im Umfang von 120 Minuten bestanden wurden.
Die Modulnote berechnet sich zu 90 % aus der Note der Abschlussklausur und zu 10 % aus der Note der Zwischenprüfung.
Voraussetzungen
Keine.
Bedingungen
Keine.
Lernziele
• Wissen über grundlegende, häufig benötigte Algorithmen, ihren Entwurf, Korrektheits- und Effizienzanalyse,
Implementierung, Dokumentierung und Anwendung. Wichtig ist hier ein Verständnis, das den Studenten ermöglicht,
auch neue algorithmische Fragestellungen anzugehen.
• Anwendung der in “Grundbegriffe der Informatik” und den Mathematikvorlesungen erworbenen mathematischen
Herangehensweise an die Problemlösung. Schwerpunkte sind hier formale Korrektheitsargumente und
eine mathematische Effizienzanalyse.
• Anwendung der in “Programmieren” erworbenen Programmierkenntnisse auf nichttriviale Algorithmen.
Inhalt
Die “Basic Toolbox der Algorithmik”. Im Einzelnen:
• Ergebnisüberprüfung (Checkers) und Zertifizierung
• Asymptotische Algorithmenanalyse: worst case, average case, probabilistisch, amortisiert
• Grundbegriffe des Algorithm Engineering
• Effektive Umsetzung verketteter Listen
• Unbeschränkte Arrays, Stapel, und Warteschlangen
• Hashtabellen: mit Verkettung, linear probing, universelles Hashing
• Sortieren: effiziente Algorithmen (mergesort, quicksort), untere Schranken, radix sort
• Selektion: quickselect
• Prioritätslisten: binäre Heaps, addrssierbare Prioritätslisten
• Sortierte Folgen / Suchbäume: Wie unterstützt man alle wichtigen Operationen in logarithmischer Zeit
• Graphen
* Repräsentation
* Traversierung: Breitensuche, Tiefensuche, Anwendungen (topologisches Sortieren,...)
* Kürzeste Wege: Dijkstra’s Algorithmus, Bellman-Ford Algorithmus
* Minimale Spannbäume: Kruskals Algorithmus, Jarnik-Prim Algorithmus
• Generische Optimierungsalgorithmen
* Greedy
* Dynamische Programmierung
* systematische Suche
* Lokale Suche
• Informationstheorie
* Entropiebegriff
* Datenkompression (Huffman coding, runlength encoding,...)
* fehlerkorrigierende codes
Lehrveranstaltungen im Modul Algorithmen I [IN1INALG1]
Nr. - ALG1
Lehrveranstaltung - Algorithmen I
SWS V/Ü/T - 3/1/2
Sem. - S
LP - 6
Lehrveranstaltungsverantwortliche - Peter Sanders