Theoretische Informatik 1

 

Inhalte sind:

  • fundamentale Algorithmen (Sortierverfahren und untere Schranken für vergleichsbasiertes Sortieren, Suche in Graphen, Kürzeste Wege, Minimale Spannbäume, etc.),
  • allgemeine Methoden für den Entwurf und die Analyse von Algorithmen
    • Greedy Algorithmen: z.B. Algorithmen von Dijkstra und Kruskal, Algorithmen für einfache Scheduling-Probleme, Huffmans Algorithmus
    • Divide & Conquer: z.B. Tiefensuche in Graphen, Mergesort und Quicksort, schnelle Multiplikation von Zahlen und Matritzen
    • Dynamische Programmierung: z.B. All-Pairs-Shortest-Path, gewichtetes Intervall Scheduling, Traveling Salesman Problem, paarweises Alignment
  • NP-Vollständigkeit (die Klassen P und NP, Reduktionsbegriff, Satz von Cook, weitere NP-vollständige Probleme)

Maximal können 8 CP angerechnet werden. Wenn nur Teilinhalte abgedeckt werden, geben Sie bitte im Fragebogen die CP-Zahl anteilig an.

 

Zusätzliche Informationen