Lehrstuhl Informatik II   
Sprachen und Beschreibungsstrukturen      
   Home Lehre Sommersemester 15 Vorlesungen Grundlagen: Algorithmen und Datenstrukturen login

Grundlagen: Algorithmen und Datenstrukturen

Dozent:Prof. Dr. Helmut Seidl
Ort/Zeit:Di, 13:45-16:15 in MW 0001
ModulNummer:IN0007
Beschreibung:    

  • Grundlagen der Analyse von Effizienz bzw. Komplexität (Begriffe, Maße, Landau-Symbole, Maschinenmodell)
  • Datenstrukturen für Sequenzen (dynamische Arrays, Listen, Stapel, Warteschlangen, jeweils mit Komplexität der Operationen)
  • Hashing (Verkettung, universelles Hashing, Sondierverfahren; optional: perfektes Hashing, hash-basierte Algorithmen, z.B. Mengendurchschnitt)
  • Sortieren (Kurzwdh. einfache Verfahren: InsertionSort, SelectionSort, BubbleSort; Analyse von MergeSort, HeapSort und  QuickSort; optional sortierbasierte Algorithmen, z.B. Mengendurchschnitt; untere Schranke für vergleichsbasiertes Sortieren, Rang-Selektion, RadixSort, externes Sortieren)
  • Prioritätswarteschlangen (binäre Heaps, Binomialheaps)
  • Suchbäume (binäre Suchbäume, AVL-Bäume, (a,b)-Bäume)
  • Graphalgorithmen (Graphrepräsentation, Traversierung per DFS/BFS, Zweifachzusammenhangskomponenten, starke Zusammenhangskomponenten, topologische Sortierung, kürzeste Wege, minimale Spannbäume, optional: TSP)
  • optional: Datenkompression (Huffman, Lempel-Ziv)
  • optional: einfache Algorithmen des Pattern Matchings

 

Download der Vorlesungsfolien

Die Adresse der Übungswebseite lautet (die Anmeldung erfolgt über die Übungsgruppen in TUMonline):

https://www.moodle.tum.de/course/view.php?id=21664

Vorlesungsaufzeichnungen können aus dem TTT-Archiv heruntergeladen werden:

http://ttt.in.tum.de/lectures/index_ss15.php#GAD

 

 

Für Fragen bitte zuerst an den Tutor wenden oder auf Piazza stellen.

Alles, was darüber nicht geklärt werden kann, geht an gad@in.tum.de.



TUM - Lehrstuhl Informatik II (Sprachen und Beschreibungsstrukturen) Thanks: Tango and TinyMCE     Generationszeit: 11 ms