htw saar Piktogramm
Zurück zur Hauptseite

Version des Moduls auswählen:

flag

Algorithms and Complexity

Modulbezeichnung: Algorithms and Complexity
Modulbezeichnung (engl.): Algorithms and Complexity
Studiengang: Kommunikationsinformatik, Master, ASPO 01.04.2016
Code: KI745
SWS/Lehrform: 4V (4 Semesterwochenstunden)
ECTS-Punkte: 5
Studiensemester: 1
Pflichtfach: nein
Arbeitssprache:
Englisch
Prüfungsart:
Klausur
Zuordnung zum Curriculum:
KI745 Kommunikationsinformatik, Master, ASPO 01.04.2016, 1. Semester, Wahlpflichtfach
PIM-WI10 Praktische Informatik, Master, ASPO 01.10.2011, 1. Semester, Wahlpflichtfach, Modul inaktiv seit 29.07.2015
Arbeitsaufwand:
Die Präsenzzeit dieses Moduls umfasst bei 15 Semesterwochen 60 Veranstaltungsstunden (= 45 Zeitstunden). Der Gesamtumfang des Moduls beträgt bei 5 Creditpoints 150 Stunden (30 Std/ECTS). Daher stehen für die Vor- und Nachbereitung der Veranstaltung zusammen mit der Prüfungsvorbereitung 105 Stunden zur Verfügung.
Empfohlene Voraussetzungen (Module):
Keine.
Als Vorkenntnis empfohlen für Module:
Modulverantwortung:
Prof. Dave Swayne
Dozent:
Prof. Dave Swayne


[letzte Änderung 10.07.2007]
Lernziele:
The students are capable of classifying algorithmic problems with respect to  time and space complexity. The algorithmic tools of this course enable the student to find effective approaches to many problems. Consequently, they are able to propose efficient solutions - these may be approximative if the problem is NP-hard.

[letzte Änderung 24.11.2007]
Inhalt:
1. Mathematical Tools
 - order calculus,
 - difference equations,
 - logarithms
 
2. Brute Force
 
3. Divide and Conquer
 - large integer and Strassen algorithm,
 - fundamental theorem of divide and conquer
 - convex hull and closest pair case studies.
 
4. Decrease and Conquer, Transform and Conquer.
 
5. Auxiliary Techniques
 - Precomputation,
 - Time and Space Tradeoffs,
 - String Processing Algorithms
 
6. Hierarchies of Computational Complexity
 
7. Approximation Algorithms
 
8. Case Studies in Approximation algorithms
 - branch and bound,
 - routing,
 - pipe flow and its applications


[letzte Änderung 24.11.2007]
Literatur:
to be announced

[letzte Änderung 24.11.2007]
Modul angeboten in Semester:
WS 2007/08
[Thu Oct 22 16:20:19 CEST 2020, CKEY=kaac, BKEY=kim, CID=KI745, LANGUAGE=de, DATE=22.10.2020]