Technische Universität Ilmenau

Theoretical Computer Science - Modultafeln der TU Ilmenau

Die Modultafeln sind ein Informationsangebot zu unseren Studiengängen. Rechtlich verbindliche Angaben zum Verlauf des Studiums entnehmen Sie bitte dem jeweiligen Studienplan (Anlage zur Studienordnung). Bitte beachten Sie diesen rechtlichen Hinweis.
Angaben zum Raum und Zeitpunkt von geplanten Lehrveranstaltungen entnehmen Sie bitte dem e-Veranstaltungskalender. Lehrveranstaltungen und Prüfungen, die nicht im e-Veranstaltungskalender abgebildet sind, werden "nach Vereinbarung" geplant. Eine Auflistung der betroffenen Veranstaltungen finden Sie hier: Lehrveranstaltungen, Prüfungen.

Fachinformationen zu Theoretical Computer Science im Studiengang Master Research in Computer & Systems Engineering 2012
Fachnummer100089
Prüfungsnummer2200315
FakultätFakultät für Informatik und Automatisierung
Fachgebietsnummer 2242 (Komplexitätstheorie und Effiziente Algorithmen)
Fachverantwortliche(r)Prof. Dr. Martin Dietzfelbinger
TurnusWintersemester
SpracheEnglisch
Leistungspunkte5
Präsenzstudium (h)34
Selbststudium (h)116
VerpflichtungPflicht
Abschlussschriftliche Prüfungsleistung, 90 Minuten
Details zum Abschluss
Anmeldemodalitäten für alternative PL oder SL
max. Teilnehmerzahl
Vorkenntnisse

Basic Data Structures, Calculus, Discrete Structures

Lernergebnisse

*** This course has ben replaced by "ALGORITHMS" (number 101720) ***

Fachkompetenz: The students know the basic principles of the design and the analysis of algorithms: correctness and running time. They know the o notation and their use for analyzing running times. They know basic number theoretical algorithms (addition, multiplication, division, modular multiplication, modular exponentiation, greatest common divisor), they know basic primality tests and the RSA scheme. The students know the divide-and-conquer paradigm with the master theorem (and its proof) and the most important examples like Karatsuba’s algorithm, Strassen’s algorithm, Mergesort, Quicksort, and the Fast Fourier Transform. They know basic techniques for orienting oneself in graphs and digraphs: BFS, DFS, Kosaraju’s algorithm for strongly connected components. They know Dijkstra’s algorithm for calculating shortest paths in graphs, and the data type priority queue with its most important implementation techniques “binary heap” and “d-ary heap”. Out of the family of greedy algorithms they know Kruskal’s algorithm and Prim’s algorithm for the problem of a mimimum spanning tree, including the correctness proof and the runtime analysis including the use of the union find data structure. As another greedy algorithm they know Huffman’s algorithm for an optimal binary code. In the context of the dynamic programming paradigm the students know the principal approach as well as the specific algorithms for Edit distance, all-pairs shortest paths (Floyd-Warshall), single-source shortest paths with edge lengths (Bellman-Ford), knapsack problems and matrix chain multiplication. They know the basic definitions and facts from NP-completeness theory, in particular the implications one gets (if P <> NP) from  the fact that a search problem is NP-complete as well as central examples of NP-complete problems. 

Methodenkompetenz: The students  can formulate the relevant problems and can describe the algorithms that solve the problems.  They are able to carry out the algorithms for example inputs, to prove correctness and analyze the running time. They are able to apply algorithm paradigms to create algorithms in situations similar to those treated in the course. They can explain the significance of the concept of NP-completeness and identify some selected NP-complete problems.

Inhalt

Fibonacci numbers and their algorithms, Big-O notation, multiplication, division, modular addition and multiplication, fast exponentiation, 8extended) Euclidean algorithm, primality testing by Fermat’s test (with proof) and by Miller-Rabin (without proof), generating primes, cryptography and the RSA system (with correctness proof and runtime analysis). The divide-and-conquer scheme,  Karatsuba multiplication, the master theorem (with proof), Mergesort, Quicksort, polynomial multiplication and Fast Fourier Transform. Graph representation.  Exploring graphs and digraphs by BFS and (detailed) DFS. Acyclicity test (with proof), topological ordering.  Strongly connected components by Kosaraju’s algorithm (with proof). Shortest paths by Dijkstra’s algorithm (with proof),  priority queues as auxiliary data structure. The greedy paradigm. Minimum spanning trees by Kruskal’s algorithm (with union-find data structure) and the Prim/Jarnik algorithm (with correctness proof).  Huffman encoding, with priority queue, correctness proof. The dynamic programming paradigm. Examples: edit distance, chain matrix multiplication, knapsack with and without repetition, shortest paths (Floyd-Warshall and Bellman-Ford). Polynomial search problems, class NP, NP-complete problems. Significance of the notion. Central examples: Satisfiability, Clique, vertex cover, traveling salesperson, graph coloring.

Medienformen

Blackboard, slide projection, exercise sheets, Moodle platform for communication.

Literatur

*  S. Dasgupta, C. H. Papadimitriou, U. V. Vazirani, Algorithms, McGraw Hill, 2006  (Prime textbook) 

*  T. Cormen, C. Leiserson, R. Rivest, C. Stein, Introduction to Algorithms, Second Edition, MIT Press 2001.

* Sedgewick, Algorithms, Addison Wesley. (Any edition will do, with or without specific programming language.)

Lehrevaluation

Pflichtevaluation:

WS 2015/16 (Fach)


Freiwillige Evaluation:

WS 2010/11 (Vorlesung)

WS 2011/12 (Vorlesung, Übung)

WS 2012/13 (Vorlesung)

WS 2013/2014 (Vorlesung, Übung)

WS 2014/15 (Vorlesung, Übung)


Hospitation:

Informationen und Handreichungen zur Pflege von Modul- und Fachbeschreibungen durch den Modul- oder Fachverantwortlichen finden Sie auf den Infoseiten zum Modulkatalog.