Algorithmen und Komplexität 2020

Inhalte

Algorithmen sind eindeutig beschriebene Vorgehensweisen zum Lösen von bestimmten, wohldefinierten Problemen. Algorithmik beschäftigt sich mit den Eigenschaften, der Analyse, und dem Design von Algorithmen. Sie ist der Kern der Informatik.

In dieser Vorlesung beschäftigen wir uns mit dem Entwurf und der Evaluierung von Algorithmen. Wir untersuchen, wie man Stärken und Schwächen von bestimmten Algorithmen charakterisieren kann, und lernen verschiedenen praktisch relevante Algorithmen und Datenstukturen kennen.

Fragestellungen sind z.B.

• Wie kann ich in großen Datenmengen effizient suchen?
• Wie finde ich den Weg von A nach B?
• Warum ist Quicksort schneller als Sortieren durch Auswahl?
• Wie kann ich die Laufzeit eines Algorithmus quantifizieren?
• Wie wähle ich einen geeigneten Algorithmus?

Im begleitenden Labor werden viele der vorgestellten Algorithmen und Datenstrukturen in C umgesetzt.

Unterlagen zur Vorlesung

• Folienskript (Stand 2020-07-14 - hoffentlich komplett, aber Kleinigkeiten werden sich ändern)
  • Vollversion
  • Handout (ohne Anmimationen)
• Übungsaufgaben im Klausurstil
• Die selben mit einigen Lösungen
• Übungsklausur 2015
• Übungsklausur 2015 mit Lösungen
• Übungsklausur 2016
• Übungsklausur 2016 mit Lösungen
• Übungsklausur 2018
• Übungsklausur 2018 mit Lösungen
• Übungsklausur 2019
• Übungsklausur 2019 mit Lösungen
• Übungsklausur 2020 mit Lösungen
• Beispielcode
  • Von n zu eins (4 Varianten, Python)
  • Von n zu eins (4 Varianten, Python, mit Aufwandszählung)
  • Binäre Suche (2 Varianten, Python)
  • AVL-Bäume (Einfügen, Ausgabe auch als Graph in GraphViz/Dot-Format, Python)
  • graphmaker.py: Zufällige (aber meist schöne) Graphen (für Prim, Dijkstra, ...). Ausgabe auch hier in in GraphViz/Dot-Format

Unterlagen zum Labor AI

• Foliensammlung (Stand 2020-06-24)
  • Vollversion
  • Handout
• Musterlösungen und Material
  • Standard-Rahmen für C-Programme
  • Beispiel für Argumentverarbeitung
  • Woche 1 (Zufallszahlen, Verdopplung, Listenumkehr mit bis zu MAXITEMS Elementen) als .tgz und als .zip
  • Woche 2 (Datentyp lineare Liste, Listenumkehr ohne hartes Limit) (auch als .zip)
  • Woche 3 (Diverse Listenfunktionen, Duplikate entfernen, ...) (auch als .zip, aber lernen Sie mal tar! ;-)
  • Woche 4 (Sortieren, Duplikate zählen)
  • Woche 5: Navigieren im Labyrinth
    • Datentyp zum Einstieg: labsolve_defs.c
    • Beispiel-Labyrinthe
      • testlab.txt
      • testlab2.txt
      • testlab3.txt
      • testlab4.txt
      • testlabtheseus.txt
      • Spende von Jahrgang 17 (Braucht MAXCOLS, MAXROWS = 2048)
    • Musterlösung: Woche 5
  • Woche 6: Navigieren mit Terrain
    • Beispiel-Labyrinthe
      • testlab_t1.txt
      • testlab_t2.txt
    • Lösungen:
      • Nur rechtwinklig
      • Diagonal erlaubt
    • Musterlösung: Woche 6
  • Woche 7&8: Sortierolympiade
    • Testdateien
      • Zufällige Reihenfolge
        • 10 Elemente
        • 100 Elemente
        • 1000 Elemente
        • 10000 Elemente
        • 100000 Elemente
      • Bereits sortiert
        • 10 Elemente
        • 100 Elemente
        • 1000 Elemente
        • 10000 Elemente
        • 100000 Elemente
      • Absteigend sortiert
        • 10 Elemente
        • 100 Elemente
        • 1000 Elemente
        • 10000 Elemente
        • 100000 Elemente
      • Spezialfall: Nur einsen (davon aber 100000)
    • Musterlösung: Woche 7+8
  • Woche 9: Binäre Suchbäume
    • Testrahmen
    • Kleines Testskript