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

Grundlagen: Algorithmen und Datenstrukturen

Dozent:Prof. Dr. Helmut Seidl
Ort/Zeit:MW0001 Gustav-Niemann-Hörsaal, dienstags 14-16 h und mittwochs 13h15-14h15
ModulNummer:IN0007
Beschreibung:    

Inhalt

  • 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

 

Anmeldung zu den Übungsgruppen

Das Matching ist abgeschlossen. Wer sich zum Matching nicht angemeldet hat oder wem keine Übungsgruppe zugewiesen werden konnte, meldet sich bitte direkt in TUMonline zu einem freien Platz an. Ummeldungen sind ebenfalls möglich.

Klausuren

        Informationen zu den Klausuren gibt es nur auf der Übungswebseite https://www.moodle.tum.de/course/view.php?id=26768.

        Termine:

  • Gesamtklausur: 6.8.2016
  • Wiederholungsklausur: 26.9.2016

Allgemeines

Übungswebseite: https://www.moodle.tum.de/course/view.php?id=26768

Fragen und Antworten: https://piazza.com/tum.de/spring2016/in0007

Aufzeichnungen der Vorlesung: http://ttt.in.tum.de/lectures/index_ss16.php#GAD

Die Vorlesungsfolien können Sie hier herunterladen. Bitte beachten Sie, dass diese laufend aktualisiert werden.

Kontakt

Bei Fragen wenden Sie sich bitte zuerst an den Tutor. Viele Antworten finden Sie außerdem auf Piazza.

Alles, was darüber nicht geklärt werden kann, können Sie an gad@in.tum.de schicken.



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