15  Schluß und Ausblick

Inhalt R"uckblick ·Was wurde nicht behandelt ·Programmentwicklung

Literatur: Keine spezielle Literatur zum abschlie"senden Kapitel, ein wenig aus [Ski97].

1. "Uberblick "uber Datenstrukturen und ihre Algorithmen
   • grundlegende Datenstrukturen
   • Sortieren
   • Graphen und Graphsuche, ...
2. Grundlegende Probleml"osungsstrategien
   • Divide & Conquer,
   • dyn. Programmierung
   • greedy-Strategien
   • Analyse (bzw. zumindest Absch"atzung) der Laufzeit

• Von den ``klassischen'' algorithmischen Fragestellungen: von jeder Problemklasse ein paar Instanzen behandelt, aber bei weitem nat"urlich nicht alles
• weitere wichtige (im Kurs unbehandelte) Gebiete der Algorithmik (u. a.)
  1. numerische, arithmetische Algorithmen, Kryptographie
  2. Matrixberechnungen, numerische Mathematik
  3. Geometrische Probleme (computational geometry) (f"ur Computergraphik, VLSI-Design, und vieles mehr)
  4. lineare Programmierung
• Algorithmen in bestimmten Programmiersprachen und bestimmten Maschinemodellen
• parallele Algorithmen: L"osung von algorithmischen Problemen mittels paralleler Rechner
• verteilte Programmierung: keine Algorithmen im engeren Sinne (mit Berechnung von Output aus Input)
• Programmentwicklung/Softwareentwurf

• abstrakte Datentypen: Trennung von Implementierung und Schnittstellen. Beispiele
  • Priority queue: stellt Einf"ugen, Lesenden und Extrahierenden Zugriff auf das maximale Element zur Verf"ugung, implementierbar z.B. mittels (verschiedener Arten von) Heaps, Arrays
  • W"orterbuch: Wahlfreier Zugriff "uber Schl"ussel, implementierbar mittels Hashtabelle, verschiedene B"aumen, etc.
• Þ Erh"ohte Wartbarkeit der Software
• allgemein: ``Modularisierung'' der Programmentwicklung, Teamarbeit, Wiederverwendbarkeit, Versionenverwaltung
• Vom Problem zum korrekten Programm:
  • Spezifikation,
  • Testen
  • Verifizieren
• ...