WS 2004/2005: Informatik 1, Prof. Dr.-Ing. M. Heiner

Last updated: May 03, 2005

 I N D E X

Zielgruppe
Zusammenfassung
Ziele
Voraussetzungen
Organisatorischer Rahmen
Bewertungskriterien                 - NEU - Termin Wiederholungsprüfung / Scheine - NEU -
Literatur
Inhaltsübersicht
Vorlesungsmaterialien
Übungen und Programmierpraktikum

Zielgruppe

• Studenten der Informatik, Informations- und Medientechnik, e-Business im 1. Fachsemester,
• Mathematik/Wirtschaftsmathematik/Techno-Mathematik/Physik-Studenten u. ä. mit Nebenfach Informatik;
• Wirtschaftsingenieurwesen mit Vertiefung Informatik;
  

Zusammenfassung (aus dem Vorlesungsanzeiger)

• 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 dargelegt.
• Programmierpraxis wird durch begleitende Programmieraufgaben erworben.

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;
• Kenntnisse über die Grundkonzepte von höheren Programmiersprachen;
• Verstehen des Zusammenhangs von Wahl der Datenstruktur und Algorithmenkomplexität;
• Erfahrungen mit einer semi-formalen Spezifikationsmethode für abstrakte Datentypen (ADT);
• sichere Fertigkeiten im Implementieren dieser mit Variantendiskussion in einer lebenden Programmiersprache  (etwa Java);
• grundlegende Kenntnisse im systematischen Entwerfen wiederverwendbarer strukturierter modularer (kurz: fehlerarmer) Programme, d. h.  Kennenlernen einer bestimmten Programmierkultur;

Voraussetzungen

• grundlegende Fertigkeiten im Umgang mit Rechentechnik;
• elementare Programmierkenntnisse (Umgang mit Zuweisungen, E/A, bedingten Anweisungen und Schleifen, primitive und einfache komposite Datentypen).
• Für Neueinsteiger besteht während der Übungen und Praktika genügend Gelegenheit, um diese Kenntnisse vorlesungsbegleitend erwerben zu können.

Organisatorische Rahmen

Hinweis

Ab diesem Semester geht eine neue Rahmenregelung für alle PO in Kraft, nach der sich  Studierende für jeden Modul, den sie belegen wollen, innerhalb der ersten zwei Wochen  schriftlich anmelden müssen. 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. Die Anmeldung erfolgt über LEHVIS. Siehe auch Allgemeine Prüfungsmodalitäten.

Die Lehrveranstaltung Informatik 1 besteht pro Vorlesungswoche aus zwei Blöcken Vorlesungen, einem Block Übung und einem Block des begleitenden Programmierpraktikums (nicht für alle obligatorisch).

Vorlesungen

Übungen/Programmierpraktikum

Gruppeneinteilung und organisatorische Leitung    
Ronny Richter, rrichter(at)informatik.tu-cottbus.de

Die Gruppeneinteilung erfolgt mit dem Einschreiben in die Lehrverantaltung (vgl. oben) über LEHVIS.
Die Übungen und Praktika beginnen in der zweiten Vorlesungswoche (44. KW 2004).

Referenz-Programmiersprache - Java,  Version 1.5.

Bewertungskriterien

Prüfung zur Vorlesung

Die Prüfung besteht aus drei Teilen - zwei während des Semesters angebotenen Testaten sowie einer Abschlussklausur.  Alle Testate sowie Klausuren werden ohne Unterlagen (d.h. auch ohne Handy und ohne Wörterbücher) geschrieben. Die Gesamtnote ergibt sich aus der Summe der erreichten Punktzahl aus den drei Prüfungsteilen. Zum Bestehen der Prüfung sind mindestens 50 % der erreichbaren Maximalpunktzahl erforderlich.

Die Wiederholungsklausur wird über drei Stunden geschrieben und ersetzt alle drei Prüfungsteile aus dem WS 2004/05. Je nach Anzahl der bisherigen Fehlversuche gilt sie als erste bzw. zweite Wiederholung. Achtung: es werden keine mündlichen Prüfungstermine für die zweite Wiederholung angeboten.

Studierende, die an der Abschlussklausur am 21.02.2005 wegen Krankschreibung nicht teilnehmen konnten, können zu diesem Termin ihre Abschlussklausur über 1.5 h schreiben.

Die Scheine zur Vorlesung können ab sofort im Sekretariat EHS 208, nachmittags (14.00 - 16.30) abgeholt werden. Unabhängig davon erfolgt eine direkte Meldung der Ergebnisse an das Prüfungsamt. Die Ergebnisse sind auch über LEHVIS abfragbar.

Klausureinsicht

Mittwoch, den 13.04.2005, 11.00 - 12.00
Donnerstag, den 14.04.2005, 11.00 -12.00

Bitte melden Sie sich zuvor über dsszsekr(at)informatik.tu-cottbus.de an, damit wir Ihre Klausur bereitlegen können.

Übungen

Im Verlaufe des Semesters gibt es sechs Übungsblätter, die individuell zu bearbeiten sind. Die Abgabe/Bewertung ist freiwillig. Jedes Übungsblatt wird nach dem Schema "sehr gut" -  "gut" - "bestanden" - "nicht bestanden" bewertet. Wer alle Übungsblätter mit mindestens "gut" absolviert, bekommt für die beiden Testate volle Punktzahl angerechnet.

Programmierpraktikum

Im Verlaufe des Semesters gibt es sieben Aufgabenblätter, die individuell zu bearbeiten sind. zum Bestehen des Programierpraktikums  sind mindestens 70 % der erreichbaren Maximalpunktzahl erforderlich. Bei Bedarf gibt es in der Semesterpause zwei Wiederholungsblätter (die dann aber dem aktuellen Wissenstand entsprechend deutlich schwerer ausfallen).

Die Praktikumsscheine können ab sofort im Sekretariat EHS 208, nachmittags (14.00 - 16.30) abgeholt werden. Unabhängig davon erfolgt eine direkte Meldung der Ergebnisse an das Prüfungsamt. Die Ergebnisse sind auch über LEHVIS abfragbar.

Allgemeines

Ein Credit entspricht 30 Arbeitstunden (Bachelorstudienordnung, §7). Somit gilt

• Vorlesung: 10 Credits = 300 Arbeitsstunden;
  bei 15 Wochen  macht das 20 Arbeitstunden pro Woche!
  Davon sind 4.5 h sogenannte Kontaktstunden, womit 15.5 Stunden pro Woche zur Vor-/Nachbereitung der Vorlesung bzw. Bearbeitung der Übungsaufgaben verbleiben.
• Praktikum:  4 Credits = 120 Arbeitsstunden;
  bei einer Kernlaufzeit des Programmierpraktikums von 10 Wochen macht das 12 Arbeitsstunden pro Woche!

Diese Aufwandskalkulation ist beim Verfassen der Aufgabenblätter berücksichtigt worden.

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;
  Originalausgabe erschien 1992 unter dem Titel "Foundations of ComputerScience"), 1042 p.;
  
• Güting, R. H.:
  Datenstrukturen und Algorithmen;
  Teubner 1992, 308p.;
• Ottman; Widmayer:
  Algorithmen und Datenstrukturen;
  BI Wiss. Verlag 1993;

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, 465p.;

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.
• Java-CD/DSSZ:
  eine von uns zusammengestellte CD mit sehr umfangreichem Material zu Java; Verteilung erfolgt über die Übungsgruppen.

Inhaltsübersicht

0. Einführung

Organisationsform dieser LV, die Spielregeln zum Bestehen der LV; Literatur; Kurzüberblick zu Mini-Java;

1. Einleitung

1.1 Vom Problem zum Programm

Grundprinzipien des Programmierens: abstrahieren, modellieren, transformieren, implementieren;
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: souveräner Umgang mit Prozeduren und Pointern;
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 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;
Anwendungsbeispiel: Formelauswertung (mit Formelbäumen und Keller);

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 vollständig binäre Bäume (vgl. 5.3, ADT heap);

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;

5. Sortierverfahren

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

5.1 Elementare Sortierverfahren - O(n2)

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

5.2 Spezielle Sortierverfahren - O(n)

bucket sort [, radix sort]

5.3 Höhere Sortierverfahren - O(nlogn)

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

--------------- ENDE -------------ENDE -------------  ENDE ----------------

6. Ausgewählte Themen / Was man sonst noch hätte machen können

6.1 Alphabetische Suchbäume (Tries)

Tries für die Organisation von ZK; binäre Tries

6.2 Mehrdimensionale Suchbäume

zur Organisation von geometrischen Objekten:
(1) Punkte in der Ebene, (2) Pixelgraphiken (die Katze im Viererbaum);

 Vorlesungsmaterialien

zu 0. Einführung

intro_unix1.pdf (6 p.)  intro_unix2.pdf  (4 p.)

das Wichtigste in Kürze (4 p.)
Skript Mini-Java (14 p.)
Übungsaufgaben "Einführung in die Programmierung" (12 p.)

zu 1.1  Vom Problem zum Programm

euler.pdf (11 p.)

zu 1.2  Konzepte der PS

Demo-Lösung zum Euler-Problem:

(1) NodeT.java                  (2) GraphT.java                        (3) Euler.java
(4) GraphMatrixT.java      (5) GraphAdjListT.java
(6) EulerMain.java            (7) EulerMain1.java

zu 1.3  Komplexität von Algorithmen

komplexitaet.pdf (5 p.)

zu 2.1  Listen

ADT_Lists.pdf   (10 p.)
ElemT.java     ListT.java       IteratorT.java      ListOperations.java
Implementierung von  Listen.pdf  (8 p.)

zu 2.2 Keller (Stacks)

ADT_Stack.pdf   (2 p.)   
StackT.java

zu 2.3 Warteschlangen (Queues) 

ADT_Queue.pdf   (2 p.)
QueueT.java

zu 2.4 Mengen (Sets)

ADT_Set.pdf   (6 p.)

zu 2.5 Abbildungen (Maps)

ADT_Map.pdf   (2 p.)

zu 2.6 Graphen

Anwendungen der transitiven_Huelle.pdf  (7 p.)
Demo-Implementierung des Warshall-Algorithmus' :
(1) TransitiveClosure.java    (2) MatrixOperations.java
(3) OpT.java    (4) Or.java    (5) And.java    (6) Min.java    (7) Plus.java

zu 3. Bäume

Wirbeltraversierung.pdf

zu 4.4. Hash-Methoden

Vergleich internes/externes Hashing.pdf ( 1 p.)

zu 5. Sortierverfahren

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

sortDemo1.jar    sortDemo2.jar

. . . T H E  E N D . . .

sachdienliche Hinweise zu dieser Seite bitte an: