Logo

teaching

data structures and software dependability

computer science department

brandenburg university of technology cottbus - senftenberg

Informatik 2 - Algorithmieren und Programmieren

Vorlesung, Prof. Dr.-Ing. M. Heiner, SS 2013

latest update: February 27, 2017, at 08:37 PM

I N D E X

Ab sofort (07.06.2013) findet die Vorlesung freitags im HS C statt.

Zielgruppe

Studierende der folgenden Bachelor-Studiengänge, jeweils im 2. Semester nach dem Regelstudienplan

  • eBusiness
  • Informatik
  • Wirtschaftsmathematik
  • Informations- und Medientechnik
  • Wirtschaftsingenieurwesen (SR Informatik)
  • Mathematik

Zusammenfassung

siehe auch Modulkatalog Modul 12101

  • Aufbauend auf einem intuitiven Algorithmenbegriff werden Grundprinzipien des Entwurfs und der Analyse von Algorithmen behandelt. Insbesondere werden Maße für die Effizienz von Algorithmen sowie Methoden für Aufwandsabschätzungen dargelegt.
  • Ein wichtiger Aspekt ist dabei der Zusammenhang zwischen Algorithmen und geeigneten Datenstrukturen.
  • Die Betrachtungen erfolgen anhand von grundlegenden Datenstrukturen bzw. Algorithmen, etwa Sortieren, Speichern und Wiederauffinden, spezielle Algorithmen in Graphen.
  • Am Beispiel einer höheren Programmiersprache werden die Grundkonzepte von Programmiersprachen und deren Nutzung vertieft.
  • Programmierpraxis wird durch begleitende Programmieraufgaben vertieft.

Ziele

  • Allgemein: fundierte Kenntnisse in grundlegenden Datenstrukturen bzw. Algorithmen und deren Implementierung, speziell:
  • Grundverständnis des Konzeptes "Komplexität von Algorithmen"; Fähigkeit, einfache Algorithmen hinsichtlich ihrer Laufzeiteffizienz zu bewerten;
  • vertiefte Kenntnisse über die Grundkonzepte von höheren Programmiersprachen;
  • Verstehen des Zusammenhangs zwischen Wahl der Datenstruktur und Algorithmenkomplexität;
  • Erfahrungen mit einer semi-formalen Spezifikationsmethode für abstrakte Datentypen (ADT);
  • sichere Fertigkeiten im Implementieren von ADT mit Variantendiskussion in einer lebenden Programmiersprache (etwa Java);
  • vertiefte Kenntnisse im systematischen Entwerfen wiederverwendbarer, strukturierter, modularer (kurz: fehlerarmer) Programme, d. h. Kennenlernen einer bestimmten Programmierkultur;

Voraussetzungen

  • LV "Informatik 1"
  • LV "Programmierpraktikum", bzw.
  • grundlegende Kenntnisse in der Programmierung mit einer imperativen Programmiersprache, zum Beispiel Java, verbunden mit grundlegende Fertigkeiten im Umgang mit Rechentechnik;

Organisatorische Rahmen

Hinweis

Nach der Rahmenregelung für alle PO haben sich alle Studierende für jeden Modul, den sie belegen wollen, innerhalb der ersten drei Wochen selbständig und verbindlich beim Prüfungsamt anzumelden. Studierende in modularisierten Studiengängen können sich typischerweise online anmelden. Von dieser Anmeldung kann man innerhalb der ersten sieben Wochen zurücktreten. Mit der Anmeldung zu einer Lehrveranstaltung ist man für die zugehörige Prüfung angemeldet.

Ausserdem bitten wir zur Organisation des Übungsbetriebes um eine Anmeldung über LEHVIS.

Die Lehrveranstaltung besteht pro Woche aus

  • zwei Blöcken Vorlesung
  • einem Block Übung und
  • einem Block Laborarbeit

Vorlesungen

dienstags und freitags, 4. Block (13.45 - 15.15)

  • dienstags: GH
  • freitags: ab sofort (07.06.2013) findet die Vorlesung im HS C statt.

Beginn: 09.04.2013

Übungen und Laborarbeit

Organisation: Peter Sauer, peter (dot) sauer (at) tu-cottbus.de,
für weitere Informationen siehe Übungsseite

Beginn: 2. Vorlesungswoche

Erfolgreiche Übungsteilnahme ist eine binäre Prüfungskomponente.

Zwischenklausur

  • wann: Dienstag, 7. Mai 2013
  • Uhrzeit: in der Vorlesungszeit, Einlaß 13.15
  • wo: GH
  • Umfang: ein Drittel der insgesamt erreichbaren Punktzahl

Endklausur

  • wann: 18. September 2013
  • Uhrzeit: tba
  • wo: tba
  • Umfang zwei Drittel der insgesamt erreichbaren Punkte

Aus der Summe der in beiden Klausuren erreichten Punktzahlen errechnet sich die Prüfungsnote. Die Bewertung erfolgt nach dem üblichen Notenspiegel.

Zum Übungsablauf

  • Die Übungen dienen zur Klärung von Fragen zum Vorlesungsstoff und vor allem zur Diskussion der Aufgaben bzw. Präsentation von Lösungen der Übungsblätter.
  • Im Verlaufe des Semesters wird es ACHT Übungsblätter geben, drei davon sind von jedem Studenten individuell zu bearbeiten, die restlichen in Zweiergruppen.
  • Alle Lösungen sind in einer für Informatiker angemessenen Form einzureichen, alle Programme sind gemäß den Vorgaben zu dokumentieren.

    ACHTUNG: Massive Verstöße führen zur Ablehnung der Lösung, d.h. die Lösung gilt als nicht abgegeben. Die Entscheidung hierzu liegt beim Übungsbetreuer.
  • Weitere Hinweise und die genauen Regelungen zur Abgabe der Lösungen finden Sie auf der Übungsseite.

Bewertungskriterien

Die Prüfung zur Lehrveranstaltung setzt sich aus den folgenden zwei Bestandteilen zusammen:
(1) Übungsteilnahme UND
(2) Klausur (in zwei Teilen).

Es müssen beide Kriterien erfolgreich absolviert werden.

(1) Übungsteilnahme

Im Verlaufe des Semesters wird es ACHT Übungsblätter geben. Alle Übungsblätter werden nach folgendem Schema bewertet:

CodeSchlagwortKommentar
0ungenügendnicht abgegebene oder nicht fristgerecht abgegebene oder unvollständige Lösungen werden automatisch mit "ungenügend" bewertet; dasselbe gilt für eingereichte Programme, die sich nicht erfolgreich übersetzen lassen.
1nachbesserungsfähiges gibt bei Bedarf eine ZWEIWÖCHIGE Frist zur Nachbearbeitung, um evtl. "bestanden"zu erreichen; wird diese Frist nicht eingehalten, wird das Blatt mit "ungenügend"bewertet. Falls auch die Nachbearbeitung mit "nachbesserungsfähig" bewertet wird, kann es im Ausnahmefall eine zweite Nachbearbeitung bis zum 23. August geben.
2bestandendas sollte der Regelfall sein

Ein Übungsblatt wird als "bestanden" bewertet, wenn ca 75% der erwarteten Leistung erbracht werden. Die Übungsteilnahme wird mit erfolgreich bewertet, wenn mindesten SIEBEN Übungsblätter als "bestanden" bewertet werden.

ACHTUNG: Nicht erfolgreich bearbeitete Übungsblätter können bis zu zweimal nachbearbeitet werden, einmal innerhalb der nächsten zwei Wochen, ein zweites Mal bis zum 23. August 2013. Als Nachbearbeitung eingereichte Lösungen von Übungsblättern sind in einem Gespräch zu verteidigen.

Gegenstand der Bewertung der Übungsteilnahme ist die über das Semester gesammelte Dokumentation der Lösungen aller Übungsblätter. Gespräche im August beziehen sich damit automatisch auf die gesammelte Dokumentation.

(2) Klausur

Die Klausur besteht aus zwei Teilen: einer Zwischenklausur und einer Abschlußklausur. Die Klausur wird mit erfolgreich bewertet, wenn in der Summe mindestens 50 % der maximalen Punktzahl erreicht werden. Die Benotung erfolgt nach dem üblichen Notenspiegel.

Klausuren werden ohne Unterlagen (d.h. auch ohne Handy und ohne Wörterbücher) geschrieben.

Allgemeines

Ein Credit entspricht 25-30 Arbeitstunden (Bachelorstudienordnung, §7). Somit gilt bei Annahme eines mittleren Wertes von 27:

  • Lehrveranstaltung: 10 Credits = 270 Arbeitsstunden;
  • bei 15 Wochen Vorlesungszeit sind davon 15x6h = 90h sogenannte Kontaktstunden;
  • es verbleiben 180h für das Selbststudium, vgl. Modul12101;
  • Annahme: es werden 30h (etwa 5 Tage mit je 6h) zur Vorbereitung auf die Abschlußklausur benötigt;
  • es verbleiben 10h pro Woche zur Vor-/Nachbereitung der Vorlesung bzw. Bearbeitung der Übungsaufgaben;

Diese Aufwandskalkulation ist bei der Stoffauswahl und dem Verfassen der Aufgabenblätter berücksichtigt worden.

Literaturhinweise

eine sehr kleine Auswahl nützlicher Literatur

Datenstrukturen und Algorithmen, allgemein

  • Aho, A. A.; Hopcroft, J. E.; Ullman, J. D.:
    Data Structures and Algorithms;
    Addison-Wesley 1983, 427 p.
  • Aho, A. A.; Ullman, J. D.:
    Informatik, Datenstrukturen und Konzepte der Abstraktion;
    Int. Thomson Publ. 1996; , 1042 p.
    Originalausgabe erschien 1992 unter dem Titel "Foundations of ComputerScience"
  • TH Corman, CE Leiserson, RL Rivest;
    Introduction to Algorithms;
    MIT Press 1998, 1028 p. (3rd edition, July 2009, 1312 p)
  • Güting, R. H.:
    Datenstrukturen und Algorithmen;
    Teubner 1992, 308 p.
  • Ottman; Widmayer:
    Algorithmen und Datenstrukturen;
    BI Wiss. Verlag 1993
  • R Sedgewick, K Wayne:
    Algorithms;
    Addison-Wesley Professional; 4th edition, 2011, 976 p.

Datenstrukturen und Algorithmen anhand von Java

  • Weiss, M. A.:
    Data Structures & Algorithm Analysis in Java;
    Addison-Wesley 1999, 542 p.
  • Grand, M.:
    Patterns in Java, Volume 1;
    John Wiley & Sons, 1998, 465 p.

Hinweis: (fast) jedes Fachbuch mit den Wörtern "Datenstrukturen" und/oder "Algorithmen" im Titel (in beliebiger Reihenfolge) tut es auch.

Einführung in die Programmierung anhand Java

  • Rauh, O.:
    Objektorientierte Programmierung in Java, eine leicht verständlicheEinführung;
    Vieweg Verlag 2000, 2. Auflage, 254 S.
  • Bishop. J.:
    Java Gently, Third Edition; Java 2 featuring Swing;
    Addison-Wesley 2001, 664 p.
  • Bishop, J.:
    Java Lernen; Anfangen, Anwenden, Verstehen; Java Gently in dt. Übersetzung;
    Addison-Wesley 2001, 2. Auflage, 752 S. mit CD.
  • Bishop, J.; Bishop, N.:
    Java Gently for Engineers & Scientists;
    Addison-Wesley 2000, 436 p.

Inhaltsübersicht

-> Prüfungsschwerpunkte

0. Einführung

Organisationsform dieser LV, die Spielregeln zum Bestehen der LV; Literatur; Kurzüberblick zur Konzeption dieser LV;

1. Einleitung

1.1 Vom Problem zum Programm

Grundprinzipien des Programmierens: abstrahieren, modellieren, transformieren, implementieren;
informeller Algorithmus -> Psuedokode-Algorithmus -> Programm;
Beispiele: (1) Königsberger Brückenproblem, (2) Färbung von Graphen/Ampelsteuerung;
die Rolle von ADTn im Softwareentwicklungsprozeß;

1.2 Ausgewählte Aspekte von Programmiersprachen

Zum Programmieren im Kleinen:
Grundlegende Begriffe: Daten/Datentyp/abstrakter Datentyp, Konstante/Variable/Pointer, strukturierte Datentypen; souveräner Umgang mit Pointern und Prozeduren;

Zum Programmieren im Großen:
Modularisierung von Programmen, Implementierung von ADT;

1.3 Analyse von Programmen

Effizienz von Programmen, Laufzeitabschätzungen von nichtrekursiven und rekursiven Programmen; die Groß-Oh-Notation;

2. Grundlegende Abstrakte Datentypen (ADT)

2.1 Listen

Anwendungsbeispiele: siehe weitere Abschnitte in diesem Kapitel;
Definition als ADT;
Implementierung durch Arrays + vier Varianten von Zeigerstrukturen;
Vergleich der Implementierungsvarianten bzgl. der Zeitkomplexität der Operationen;

2.2 Keller (Stacks)

Anwendungsbeispiele: Umkehren einer ZK, Überprüfen wohlgeformter Klammerausdrücke;
Definition als ADT;
Implementierung über Listen bzw. direkt durch Arrays + Zeigerstrukturen;

2.3 Warteschlangen (Queues)

Anwendungsbeispiele: Zwischenspeicher in BS;
Definition als ADT;
Implementierung über Listen bzw. direkt durch zirkuläre Arrays + Zeigerstrukturen;

2.4 Mengen (Sets)

Anwendungsbeispiele: mathematischer Grundbegriff;
Definition als ADT;
Implementierung durch Bitvektoren + Zeigerstrukturen; weitere Implementierungen (siehe Kap. 4, Verzeichnisse);
Vergleich der Implementierungsvarianten bzgl. der Zeitkomplexität der Operationen;

2.5 Abbildungen (Maps)

Anwendungsbeispiele: mathematischer Grundbegriff;
Definition als ADT;
Implementierung über Mengen bzw. direkt durch Arrays + Zeigerstrukturen; weitere Implementierungen (siehe Kap. 4, Verzeichnisse);

2.6 Graphen

Anwendungsbeispiele: mathematischer Grundbegriff (vgl. Abschnitt 1.1);
Definition als ADT (vgl. Abschnitt 1.1);
Implementierung durch Adjazenz-Matrizen/Listen + verschiedene Zeigerstrukturen;
ein Spezialfall: bipartite Graphen, z. Bsp. Petrinetze;
ein ausgewählter Basisalgorithmus: die Transitive Hülle mit verschiedenen Anwendungen;

3. Bäume

3.1 Grundlagen

grundlegende Begriffe, rekursive Definitionen durch Komposition/Zerlegung; Pre/In/Post-Order-Durchlaufverfahren, Formelbäume; Anwendungsbeispiele: Formelauswertung (mit Formelbäumen und Keller), Suchbäume, Spannbäume, Pixelgraphiken (die Katze im Viererbaum) ;

3.2 Bäume als ADT

typische Operationen auf Bäumen; Durchlaufverfahren: rekursiv und nichtrekursiv, Wirbeltraversierung;

3.3 Implementierungen

in vier allg. Varianten und einer sehr speziellen für links-vollständig binäre Bäume; ADT heap, Einfügen und Löschen am heap (vgl. 7.3, heap sort);

4. Verzeichnisse/Wörterbücher

4.1 Grundlagen

Anwendungen; Definition als ADT; einfache Implementierungen: ungeordnete/geordnete Arrays + Zeigerstrukturen;

4.2 Suchbäume

allgemeine und binäre Suchbäume; Suche, Löschen und Einfügen;

4.3 Ausgeglichene Suchbäume

vollständig ausgeglichene und ausgeglichen Suchbäume; Klassen ausgeglichener Suchbäume: [AVL-Bäume, ]

2/3-Bäume, B-Bäume;

4.4 Hash-Methoden

Hash-Funktionen, Kollissionen, Wahrscheinlichkeit von Kollisionen; Behandlung von Kollissionen: geschlossenes/offenes Hashing; Sondiermethoden: lineares Sondieren, Doppelhash-Verfahren;

AUSGEWÄHLTE ALGORITHMEN & DATENSTRUKTUREN

5. Prinzipien zur Erzeugung von (Pseudo)Zufallszahlen und ihre Anwendung in heuristischen Verfahren

  • Begriffe Zufall, Zufallsgröße, Zufallszahl, Zufallszahlenfolge
  • Gleichverteilung und Autokorrelation (Maß für die Unabhängigkeit) in Zufallszahlenfolgen
  • Generatoren für echte Zufallszahlen - Rauschgrößenmessung - Laufzähler mit Stoppereignis - Ziffernfolgen transzendenter Zahlen
  • Pseudozufallszahlengeneratoren - allgemeines Prinzip und Periodizität - multiplikativer Kongruenzgenerator - gemischt linearer Kongruenzgenerator - mehrfach rekursiver Kongruenzgenerator - x^2-mod-n-Generator nach Blum/Shub - linear rückgekoppelte Schieberegister
  • Heuristik - Begriff und Idee
  • Beispiel künstliche Evolution

6. Fortgeschrittene Programmierkonzepte in Java

Assertions, Generics - Einführung, Foreach-Schleife, Generic-Methods, Varargs;

7. Sortierverfahren

allgemeines: interne/externe Sortierverfahren, Kriterien für den Vergleich von Sortierverfahren; zur Visualisierung der Sortierverfahren;

7.1 Elementare Sortierverfahren - O(n2)

insertion sort, selection sort, bubble sort, shell sort;

7.2 Spezielle Sortierverfahren - O(n)

bucket sort, radix sort

7.3 Höhere Sortierverfahren - O(nlogn)

merge sort, quick sort, tree sort, heap sort: ADT heap, Einfügen und Löschen am heap;

8. Binäre Entscheidungsdiagramme

  • vom binären Entscheidungsbaum zum binären Entscheidungsdiagramm: zwei Reduktionsregeln;
  • zwei Verfahren zur Konstruktion von binären Entscheidungsdiagrammen: on-the fly top-down (build-bdd), bottom-up (apply);
  • Darstellung von Zustandsmengen in binären Entscheidungsdiagrammen, Mengenoperationen als Operationen über Entscheidungsdiagrammen;
  • Verallgemeinerung auf Interval-Entscheidungsdiagramme (IDD);

9. Stark-zusammenhängende Komponenten

  • Stark-zusammenhängende Komponenten in einem gerichteten Graphen, Komponenten-Graph;
  • O(m+n)-Algorithmen von Tarjan und Kosaraju;

---------------------Vorlesungsstand---------------------Vorlesungsstand---------------------

Materialien zur Vorlesung

Materialien zur Vorlesung (Folien als pdf, Demo-Lösungen als Java-Quellen).

zu 1.1 Vom Problem zum Programm

zu 1.2 Ausgewählte Aspekte von Programmiersprachen

Zum Programmieren im Kleinen:

Zum Programmieren im Großen:

EULER:

zu 1.3 Analyse von Programmen

zu 2.1 Listen

zu 2.2 Keller (Stacks)

zu 2.3 Warteschlangen (Queues)

zu 2.4 Mengen (Sets)

zu 2.5 Abbildungen (Maps)

zu 2.6 Graphen

eine spezielle Klasse bipartiter Graphen:

ein typischer Algorithmus auf Graphen:

zu 3. Bäume

zu 4.4. Hash-Methoden

Kollisionen und Vergleich internes/externes Hashing.pdf

zu 7. Sortierverfahren

  • eine txt-Datei mit dem Java-Programmkode einiger der in der Vorlesung angesprochenen Algorithmen;
  • zwei Programme zur Visualisierung ausgewählter Algorithmen als jar-Dateien (Aufruf: java -jar <file name>.jar)
    sortDemo1.jar - sortDemo2.jar

zu 8. Binäre Entscheidungsdiagramme

ergänzendes Material:

zu 9. Stark-zusammenhängende Komponenten

---------------------Vorlesungsstand---------------------Vorlesungsstand---------------------

… the end …

Any comments or questions are welcome. Please direct them to monika [period] heiner [snail] b-tu [period] de Privacy Policy