Einführung in die Informatik II

Prof. Dr. Andy Schürr

email: Andy.Schuerr@unibw-muenchen.de

Institut für Softwaretechnologie
Fakultät für Informatik
Universität der Bundeswehr München
D-85577 Neubiberg

    Lady Ada, der Welt erste Programmiererin?  - Vorlesung im Wintertrimester an der Universität der Bundeswehr München

Ziele und Inhalte der Vorlesung

Ziel der Vorlesungsreihe "Einführung in die Informatik I bis III" ist es, dem Zuhörer einen Überblick über die Informatik mit Schwerpunkt "Praktische Informatik" zu geben. Im Vordergrund stehen dabei in der Vorlesung "Einführung in die Informatik IIa" (für Informatik-, Informationstechnik- und Wirtschaftsinformatikstudenten) imperative Programmiersprachenkonzepte des sogenannten "Programmierens-im-Kleinen" sowie vor allem Standarddatenstrukturen und -algorithmen der Informatik. In der Vorlesung "Einführung in die Informatik IIb" (für Informatik- und Wirtschaftsinformatikstudenten) werden die in "Informatik IIa" behandelten Themen vertieft und durch verwandte Themen der theoretischen Informatik ergänzt. Beide Vorlesungen werden zeitlich verschränkt gehalten und bilden eine direkte Fortsetzung der Vorlesung "Einführung in die Informatik I". Am Ende beider Lehrveranstaltungen sollten die Zuhörer in der Lage sein, kleine Programme systematisch in verschiedenen Programmiersprachen zu entwickeln und die entwickelten Lösungen hinsichtlich ihrer Effizienz und Korrektheit zu beurteilen; zudem sollten sie ein Verständnis für die zugrundeliegenden (mathematischen) Konzepte erworben haben. Als durchgängiges Beispiel für den Einsatz von Standarddatenstrukturen und -algorithmen werden logistische Probleme einer fiktiven Speditionsfirma "Blitz AG" betrachtet.

Die Vorlesung liefert damit unter anderem die Voraussetzungen für folgende Lehrveranstaltungen:

  • Einführung in die Informatik IIIa/IIIb: behandelt objektorientierte und maschinennahe Programmierung sowie Grundlagen des "Programmierens-im-Großen"
  • Software Engineering I: vertieft die Konzepte des "Programmierens-im-Großen" zur Entwicklung großer Softwaresysteme

Ergänzt wird die Vorlesung unter anderem durch folgende Lehrveranstaltung (und darauf aufbauende Veranstaltungen):

  • Grundlagen der Theoretischen Informatik: hier werden die mathematischen Grundlagen für die Lehrveranstaltungen "Informatik I" und "Informatik II" eingeführt.

Inhalte

  • Kapitel 1 (Suchen und Sortieren) befasst sich mit Standardalgorithmen zum Suchen und Sortieren auf Feldern. Dazu gehören das bereits in Informatik I angesprochene "Suchen und Sortieren durch Einfügen" sowie Quicksort als ein Beispiel für einen rekursiven Sortieralgorithmus (Prinzip: "divide and conquer" bzw. "divide and impera").
  • Kapitel 2 (Komplexität von Algorithmen) widmet sich der Bewertung der Effizienz von Algorithmen hinsichtlich ihres Speicherplatzverbrauches und vor allem ihres Laufzeitverhaltens. Am Beispiel der in Kapitel 1 vorgestellten Algorithmen wird der O-Kalkül zur Bestimmung der Laufzeit im besten/schlechtesten Fall vorgestellt. Zudem wird die Einteilung von Algorithmen in verschiedene Klassen behandelt und das Thema sogenannter "NP-vollständiger Probleme" am Beispiel der Planung optimale LKW-Beladungen der Firma Blitz AG kurz angerissen.
  • Kapitel 3 (Realisierung abstrakter Datentypen) wiederholt und vertieft das Thema "abstrakte Datentypen" und führt die zu ihrer Realisierung benötigten programmiersprachlichen Konstrukte in Ada ein. Dazu gehören das Paketkonzept von Ada sowie die Umsetzung der Überprüfung von Vor-/Nachbedingungen und Invarianten von abstrakten Datentypen mit Hilfe von Ausnahmebehandlungs-Anweisungen.
  • Kapitel 4 (Korrektheit von Algorithmen) diskutiert die Frage, wie man die Korrektheit von Programmen sicherstellen kann (und so den Konkurs der Firma Blitz AGaufgrund fehlerhafter Programme vermeidet). Nach einem kurzen Überblick über systematische Testverfahren wird vor allem skizziert, wie man ausgehend von formalen Programmspezifikationen die Korrektheit der entsprechenden Programmteile beweisen kann.
  • Kapitel 5 (Dynamische Datenstrukturen)  stellt eine Einführung in den Umgang mit dynamischen Datenstrukturen dar. Hier wird gezeigt, wie man in Ada mit Hilfe von Zeigern Listen beliebiger Länge realisieren kann und wie man mit Hilfe von Objekt- und Klassendiagrammen den Aufbau und die Zugriffsoperationen solcher Datenstrukturen vor ihrer Implementierung plant.
  • Kapitel 6 (Streuspeicherverfahren) stellt eine Fortsetzung von Kapitel 1 dar. Hier wird gezeigt, wie man mit Hilfe von Feldern fester Länge und Listen variierender Länge Suchalgorithmen mit (fast) konstantem Laufzeitverhalten (in Bezug auf die Anzahl der gespeicherten Elemente, unter denen ein bestimmtes Element gesucht wird) realisiert. Hierfür werden verschiedene Varianten von sogenannten Streuspeicherverfahren (Hash-Algorithmen) präsentiert und miteinander verglichen.
  • Kapitel 7 (Einfache Binärbäume) befasst sich mit verschiedenen Varianten von Baumdatenstrukturen, die eine herausragende Rolle für die Implementierung von Such- und Sortieralgorithmen auf großen Datenmengen spielen (Kundenkarteien, Auftragsbestände, ... der Firma Blitz AG). Neben einfachen binären Suchbäumen wird auch das Thema höhenbalanzierter Suchbäume kurz angesprochen.
  • Kapitel 8 (Balanzierte Suchbäume)ertieft das Thema Baumdatenstrukturen. Hier werden verschiedene Formen höhenbalanzierter Suchbäume genauer besprochen. Hierzu gehören die oft verwendeten AVL-Bäume (bzw. Rot-Schwarz-Bäume) und die für Datenbanken wichtigen B-Bäume. Für ihren systematischen Entwurf wird der Umgang mit Klassendiagrammen, Objektdiagrammen und Invarianten (Vor- und Nachbedingungen) an verschiedenen Beispielen vorgeführt.
  • Kapitel 9 (Graphalgorithmen) stellt schließlich eine Einführung in das Thema Graphen und Graphalgorithmen dar. Insbesondere in diesem Kapitel werden logistische Probleme der Speditionsfirma Blitz AG wie optimale Routenplanung, Planung eines optimalen hierarchischen Filialnetzes etc. behandelt.
  • Kapitel 10 (Dynamische Programmierung und Verwandte) rundet die Vorlesung mit einer kurzen Behandlung weiterer Konzepte zum Entwurf von Algorithmen für die Lösung "harter" Probleme wie die Berechnung optimaler LKW-Beladungen der Firma Blitz AG ab. Das Prinzip der "dynamischen Programmierung" steht dabei im Vordergrund, der Einsatz sogenannter "Branch-And-Bound-Algorithmen" wird als Spezialfall der Backtracking-Algorithmen aber auch angesprochen.

Folien zur Vorlesung

Alle (bereits existierenden) Folien der Vorlesung sind in der folgenden Datei

  • INF2.pdf :          pdf-Fassung (Stand  21.03.02)
  • INF2.pdf.gz :    mit gzip komprimierte pdf-Fassung
  • INF2.pdf.zip :  mit zip komprimierte pdf-Fassung

im pdf-Format abgespeichert. Sie benötigen zur Darstellung den Acrobat-Reader als Zusatzprogramm zum Web-Browser.  Den neusten Acrobat-Reader für die verschiedenen Rechner gibt es kostenlos bei Adobe  (Achtung: beim Drucken mit Acrobat-Reader bitte die Druckoption "Paper = A4" im Print Setup einstellen).

Zudem können die Folien auch zu den einzelnen Kapiteln als PostScript-Folien (2 Folien und 4 Folien auf einer Seite) heruntergeladen werden, die mit dem Programm zip komprimiert hier zur Verfügung stehen:

Titelblatt und Gliederung der Vorlesung
[ INF2-0.2.ps.zip , INF2-0.4.ps.zip ]

    1. Suchen und Sortieren (Inf. IIa)

 

    1. [ INF2-1.2.ps.zip , INF2-1.4.ps.zip ]
    2. Komplexität von Algorithmen (Inf. IIb)

 

    1. [ INF2-2.2.ps.zip  , INF2-2.4.ps.zip  ]
    2. Realisierung abstrakter Datentypen (Inf. IIa)

 

    1. [ INF2-3.2.ps.zip , INF2-3.4.ps.zip ]
    2. Korrektheit von Algorithmen (Inf. IIb)

 

    1. [ INF2-4.2.ps.zip , INF2-4.4.ps.zip ]
    2. Dynamische Datenstrukturen (Inf. IIa)

 

    1. [ INF2-5.2.ps.zip , INF2-5.4.ps.zip ]
    2. Streuspeicherverfahren (Inf. IIb)

 

    1. [ INF2-6.2.ps.zip , INF2-6.4.ps.zip]
    2. Bäume und Suchalgorithmen(Inf. IIa)

 

    1. [ INF2-7.2.ps.zip , INF2-7.4.ps.zip ]
    2. Balanzierte Suchbäume (Inf. IIb)

 

    1. [ INF2-8.2.ps.zip , INF2-8.4.ps.zip ]
    2. Graphalgorithmen (Inf. IIa)

 

    1. [ INF2-9.2.ps.zip , INF2-9.4.ps.zip ]
    2. Dynamische Programmierung und Verwandte (Inf. IIb)

 

  1. [ INF2-10.2.ps.zip , INF2-10.4.ps.zip ]

Achtung:

Die Folien wurden mit dem Textverarbeitungssystem Framemaker (von Adobe) erstellt und enthalten - in grau dargestellte - ausblendbare Textpassagen (Lückentexte), die interaktiv in der Vorlesung erarbeitet wurden.

Termin- und Raumänderungen

  Datum Vorlesung/Übung + Raum
(Do) 10.01.2002 letzter Vorlesungstermin von Informatik I statt Informatik IIa
(Do) immer IIb in Raum 33 / 0101
(Mi) 23.01.2002 Ersatztermin für "kaputten Overheadprojektor" in 33 / 3131

Übungsbetrieb

... ist auf folgender Seite zu finden ...