|
|
AlgoK-AK-B: Algorithmen und Komplexität- Dozentinnen/Dozenten
- Prof. Dr. Isolde Adler, Dr. Jakub Pekárek
- Angaben
- Vorlesung
Rein Präsenz
4,00 SWS, Unterrichtssprache Englisch
Zeit und Ort: Mi 10:00 - 12:00, WE5/04.004
- Voraussetzungen / Organisatorisches
- Prerequisites: Algorithms and data structures, basic knowledge of computability theory, proof techniques. Good English language skills.
- Inhalt
- Algorithms and problem solving lie at the heart of computer science. Given an algorithmic problem, such as the Traveling Salesperson Problem, how can we design an efficient algorithm? Once we found an algorithm that solves the problem correctly, can we be sure that the resources, such as running time, storage space (and related: energy), required by this algorithm are really necessary for solving the problem? Perhaps we can do better? These are the guiding questions that students will explore in this module. We will discuss the design and analysis of algorithms in depth, including algorithm design principles (such as greedy algorithms, divide and conquer algorithms and dynamic programming). We then discuss the classification of computational problems according to their resource complexity. This includes time and space complexity, complexity classes such as P, NP, PSPACE and the relationship between the classes, reductions, NP-completeness, the P versus NP problem, and lower bounds on resource requirements. Decision problems, search problems, and optimisation problems are introduced, and the students will encounter a variety of relevant problems from different fields, such as network flows, satisfiability, numerical problems (Knapsack), matching problems, geometrical problems, graph colouring, sequencing problems, linear programming and scheduling. We then move on to methods for dealing with computationally hard problems, discussing approximation algorithms and randomised algorithms. Further topics such as descriptive complexity, fixed-parameter algorithms and circuit complexity may be discussed if time permits.
- Empfohlene Literatur
- Jon Kleinberg and Éva Tardos: Algorithm Design. Michael Sipser: Introduction to the Theory of Computation. Christos H. Papadimitriou: Computational Complexity. Michael Garey, David S. Johnson: Computers and Intractability: A guide to the theory of NP-completeness. Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani: Algorithms. John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman: Introduction to Automata Theory, Languages, and Computation. Sanjeev Arora, Boaz Barak: Computational Complexity, A modern approach. Jörg Flum, Martin Grohe: Parameterized Complexity Theory.
- Englischsprachige Informationen:
- Title:
- Algorithms and Complexity
- Zusätzliche Informationen
- Erwartete Teilnehmerzahl: 40
- Institution: Lehrstuhl für Algorithmen und Komplexitätstheorie
Hinweis für Web-Redakteure:
Wenn Sie auf Ihren Webseiten einen Link zu dieser Lehrveranstaltung setzen möchten, verwenden Sie bitte einen der folgenden Links:Link zur eigenständigen Verwendung Link zur Verwendung in Typo3
|
 |
|
|
UnivIS ist ein Produkt der Config eG, Buckenhof |
|
|