50 years Univerity of Lübeck

Institute for Theoretical Computer Science

Informatik A für MLS


Type and Content
Title: Informatik A
Host: Tantau, Reischuk, Balbach
Classification: Bachelor- Studiengang Molecular Life Science 5. Semester, Pflichtmodul
Conentent:

Lehrinhalte

  • Einleitung, Algorithmusbegriff
  • Einführung in die Programmierung am Beispiel von JAVA: Grundlagen, grundlegende Datenstrukturen der Informatik, Rekursion, Klassenbegriff
  • Grundlagen von Algorithmen

Qualifikationsziele:

  • Grundlegendes Verständnis des Algorithmenbegriffs
  • Fähigkeit zur Programmierung am Beispiel von JAVA einschließlich rekursiver Methoden und Klassen
  • Kenntnis der elementaren Datenstrukturen der Informatik wie Felder, Listen, Bäume, Graphen sowie deren grundlegende Algorithmen

Lernziele (ausführlich)

Hauptlernziele

  1. Die Studierenden sollen nach Besuch der Veranstaltungen informationsverarbeitende Systeme theoretisch verstehen, in Forschungs- und Entwicklungsprojekten benutzen können und Algorithmen und Datenstrukturen verschiedenen Projektbedürfnissen anpassen können.
  2. Die Studierenden sollen auf vertiefende Informatikveranstaltungen, insbesondere Veranstaltungen der Bioinformatik, vorbereitet werden.

Geplante Themenkomplexe:

  • 1. Einführung, Organisatorisches, Erwartungsabfrage

Einführung zu Computern und Algorithmen

  • 2. Information und Daten. Leitbild: Wie kommt das Video auf die DVD?
    • Die binäre Speicherform verschiedener Daten durch Computer kennen und verstehen.
    • Wichtige Einheiten von Information kennen und die Speichergröße von Daten abschätzen können.
    • Beliebige Daten kodieren können.
    • Das Konzept der Datenkompression kennen und verstehen.
  • 3. Computer-Hardware Leitbild: Was ist in der Kiste?
    • Grundlegende Rechnerarchitekturen kennen.
    • Klassen von Computern und ihre Leistungsfähigkeit kennen und abschätzen können.
    • Den prinzipiellen Aufbau von Computern beschreiben können.
    • Die wichtigsten Hardware-Komponenten von Computern kennen und ihre Leistungsfähigkeit abschätzen können.
  • 4. Computer-Software Leitbild: Was tun Computer den ganzen Tag?
    • Einprozesssysteme und das EVA-Prinzip verstehen
    • Programme als Instruktionsfolgen begreifen
    • Mehrprozesssysteme verstehen
    • Verschiedene Arten von Software benennen und unterscheiden können (Betriebssystem, Anwendersoftware, Treiber, etc.)
  • 5. Der Algorithmusbegriff Leitbild: Von der vagen Idee zur Instruktionsfolge
    • Den Begriff des Algorithmus verstehen
    • Probleme spezifizieren können
    • Einfache Lösungsideen als Algorithmen formulieren können
    • Programmiersprachen als Kommunikationsmittel für Algorithmen begreifen
    • Das Konzept des Compilers verstehen

Einführung in die Programmierung mittels Java

  • 6. Imperative Programmierung Leitbild: Tu was ich sage! (Leider nicht: Tu was ich meine!)
    • Zuweisungen verstehen und benutzen können
    • Grundlegende Kontrollstrukturen verstehen und benutzen können
    • Algorithmen als imperative Java-Programme formulieren können
  • 7. Die Java-Programmiersprache Leitbild: Eine Programmiersprache für alles und jedes
    • Syntax des imperativen Kerns von Java beherrschen
    • Java-Programme selbstständig erstellen können
    • Java-Programme übersetzen und testen können
  • 8. Elementare Datenstrukturen Leitbild: Wie rede ich über meine Daten?
    • Variablendeklaration, Identifier und Scoping verstehen und benutzen können
    • Zahlentypen als Datentypen kennen
    • Java-Programme erstellen können zur Lösung einfacher numerischer Probleme
    • Typkorrektheit und Typfehler verstehen
    • Die Speicherung von Variablen verstehen
  • 9. Strings Leitbild: Von der Papyrus-Manuskript bis zur DNA-Sequenz
    • Zeichentypen und Strings als Datentypen kennen
    • Einfache Stringalgorithmen implementieren können
    • Fortgeschrittene Stringalgorithmen kennen und implementieren können
    • Anwendungen in der Bioinformatik kennen
  • 10. Modellierung und Abstraktion in der Programmierung Leitbild: Warum ein Gedicht und eine DNA-Sequenz aus Programmiersicht dasselbe sind.
    • Modelle als Ausschnitte der Wirklichkeit begreifen
    • Problemstellungen auf ihren Kern reduzieren können
    • Abstrakte Konzepte erkennen können, die scheinbar unterschiedlichen Anwendungsgebieten zugrunde liegen
    • Bekannte abstrakte Konzepte auf unterschiedliche Anwendungsgebiete anwenden können
  • 11. Arrays Leitbild: Nummerierte Bankschließfächer
    • Konzept des Arrays verstehen
    • Java-Syntax von Arrays beherrschen
    • Java-Programme mit Array-Nutzung implementieren können
  • 12. Modularisierung im Kleinen und im Großen Leitbild: Wie man große Problem in genießbare Häppchen aufteilt
    • Das Konzept des Top-Down-Entwurf verstehen und anwenden können
    • Das Konzept des Unterprogramms/Methode verstehen und anwenden können
    • Das Konzept der Klassen- und Modulbildung verstehen
    • Java-Syntax der Modularisierung auf Methodenebene beherrschen
  • 13. Suchen Leitbild: Was ist die Telefonnummer von Herrn X?
    • Lineare Suche verstehen und implementieren können
    • Binäre Suche verstehen und implementieren können
    • Laufzeit der Verfahren vergleichen können
    • Abschätzen können, wann sich Vorsortierung lohnt
  • 14. Rekursion Leitbild: Die Türme von Hanoi
    • Das Konzept der Rekursion verstehen
    • Rekursive Methoden implementieren können für numerische Probleme wie ggT
    • Wechselseitige Rekursion verstehen und implementieren können

Grundlegende Datenstrukturen und Algorithmen

  • 15. Sortieren Leitbild: Das Telefonbuch
    • Folgende Sortierverfahren verstehen: Bubble-Sort, Insertion-Sort, Quick-Sort, Merge-Sort und Distribution-Sort
    • Drei dieser Verfahren implementieren können
    • Laufzeit der Algorithmen vergleichen können
  • 16. Listen als Datenstruktur Leitbild: Den richtigen Ansprechpartner in einer Behörde finden
    • Das Konzept der komplexe Datenstruktur verstehen
    • Die Liste als Datenstruktur verstehen
    • Listen in Java implementieren können
    • Den Unterschied zwischen Listen und Arrays erklären können
    • Vor- und Nachteile von Listen und Arrays vergleichen können
    • Fortgeschrittene Arten von Listen kennen
  • 17. Bäume und einfache Suchbäume Leitbild: Der Stammbaum
    • Das Konzept des (Such)Baumes verstehen
    • (Such)Bäume in Java implementieren können
    • Vor- und Nachteile von Arrays, Listen und Bäumen beurteilen können
  • 18. Fortgeschrittene Suchbäume
    • Eine Art fortgeschrittener Suchbäumen kennen und verstehen
    • Vor- und Nachteile gegenüber einfachen Suchbäumen beurteilen können
  • 19. Hashing
    • Konzept des Hashwerts verstehen
    • Einfache Hashfunktionen kennen und implementieren können
    • Einfache Hashverfahren kennen
  • 20. Graphen als Datenstruktur Leitbild: Busnetze, Eisenbahnnetze, Molekülverbindungen
    • Graphen als mathematische Objekte verstehen
    • Wichtige Graphbegriffe wie Weg, Zusammenhang, etc. kennen und anwenden können
    • Daten und ihre Struktur (wie DNA-Fragmente und ihre Überlappungen) mittels Graphen modellieren können
    • Die Datenstruktur des Graphen verstehen und implementieren können
  • 21. Graphalgorithmen Leitbild: Wie komme ich von Lübeck nach Kiel?
    • Arten der Graphtraversierung kennen
    • Kürzeste-Wege-Algorithmen kennen und implementieren können
    • Färbungsproblem kennen und mittels Backtracking lösen können
    • Hamiltonsches Pfadproblem kennen
  • 22. Problemlösungsstrategien Leitbild: Wie puzzelt man DNA-Fragmente zusammen?
    • Backtracking-Algorithmen verstehen und implementieren können
    • Greedy-Algorithmen verstehen und implementieren können
    • Dynamische Programme verstehen
  • 23. Geometrische Algorithmen Leitbild: Welcher Antikörper passt zum Antigen?
    • Möglichkeiten der Modellierung von Raum- und Flächendaten kennen
    • Algorithmen zum Schnitt von Polygonzügen kennen und implementieren können
    • Algorithmen zu konvexe Hüllen in der Ebene kennen

Schluss

  • Zusammenfassung, Abschlussevaluation, Diskussion, Ausblick
Literature:
  • Heinz-Peter Gumm, Manfred Sommer: Einführung in die Informatik, Oldenbourg Verlag, 2004

Die Vorlesung wird sich inhaltlich auf große Teile des Buches »Einführung in die Informatik« vom Gumm und Sommer (Oldenbourg, 39,80 €) stützen. Dieses Lehrbuch deckt das vorgeschlagene Curriculum weitgehend ab. Wir empfehlen jeden Teilnehmer, sich dieses Lehrbuch anzuschaffen. In der Lehrbuchsammlung der ZHB sind 10 aktuelle Exemplare vorhanden.

Lecture
Host: Tantau
Hours: 4 SWS, 9 ECTS

Für die Erlangung des Leistungszertifikates müssen folgende Leistungen erbracht werden:

  1. Indivduelle Bearbeitung der ein- bis zweiwöchentlichen Übungsblätter. Auf allen bis auf zwei Übungsblättern muss die Hälfte der möglichen Punkte erreicht werden und mindestens zweimal muß die eigene Lösung einer Aufgabe in der Übungsmappe vorgestellt werden.
  2. Bestehen der Klausur (voraussichtlich in der 1. vorlesungsfreien Woche am Donnerstag, 16.2.2006, 13-15 h). Die Klausurnote ergibt die Note für das Leistungszertifikat.
  3. Erfolgreiche Durchführung eines Software-Miniprojektes in der vorlesungsfreien Zeit. Februar/März 2006.
Dates: Di 14h-16h, Z1/2, Do 14h-16h, T1
1. Vorlesung: Di. 18.10.05
Vorlesungskarte: Vorlesungskarte
Skripte:

Exercise
Organisation:

Die 4SWS Vorlesung Informatik A werden durch Übungen ergänzt. Wohingegen die Vorlesung aufgrund der Teilnehmerzahl dozentenorientiert unterrichtet wird (werden muss), sollen die Übungen folgendermaßen organisiert sein:

  1. Teilnehmerorientierter Unterrichtsstil (keine zweite Vorlesung, das Üben steht im Vordergrund).
  2. Die 3SWS Übungen werden aufgeteilt
    1. in eine wöchentliche Doppelstunde, die in normalen Übungsräumen abgehalten werden, und
    2. in eine einstündige Übung in Rechnerräumen.

Bei Bedarf kann die Aufteilung aber auch variieren.

Über die Präsenzeit in den Übungen hinaus (Anwesenheitspflicht) sind für Informatik A 165h im Semester vorgesehen für die eigenen Vor- und Nachbereitung, das Lösen der Übungsaufgaben und die Prüfungsvorbereitung vorgesehen.

Wir schlagen folgende Aufteilung der Zeit für die Eigenarbeit vor:

  1. 105h (7SWS) für die Vor- und Nachbereitung der Vorlesung und das Lösen der ein- bis zweiwöchentlichen Übungsblätter.
  2. 40h Software-Miniprojekt in der vorlesungsfreien Zeit.
  3. 20h Klausurvorbereitung.
Hours: 3 SWS
Dates: Mo 16h-18h R1, R3, (2 Gruppen)
Do 10h-11h, 11h-12h PC-Pool MBT, Inst. für Chemie, EG (2 Gruppen)
1. Übung (PC Pool) Do. 20.10.05
Übungsblätter
Programmierprojekt:

Das Programmierprojekt soll in Gruppen von 2-3 Presonen durchgeführt werden, wobei der Arbeitsaufwand pro Person etwa 40 Stunden betragen soll.

Das ganze Projekt verläuft in mehreren Phasen:

  1. In der ersten Phase haben Sie zwei Möglichkeiten:

    Entweder: Erstellen Sie zu einem von Ihnen gewählten Thema eine Projektbeschreibung von etwa einer Seite Umfang. Daraus sollte hervorgehen:

    • was das Programm leisten soll (Spezifikation),
    • welche Teilprobleme dafür gelöst werden müssen (z.B. Dateiformate entwickeln, Klassen oder Methoden implementieren und dokumentieren),
    • welche Dokumentation erstellt werden soll.

    Legen Sie uns die Projektbeschreibung vor. Diese werden wir gegebenenfalls kürzen oder erweitern.

    Oder: Wählen Sie aus den vorgegebenen Projektbeschreibungen eine aus:

    • Dechiffrierung
    • Zellulare Automaten
    • Molekülvisualisierung
    • DNS-Puzzle
    • Räuber-Beute-Simulation
    • Ergebnisvorhersage
    • DNS-Vervollständigung
    • Schiffe versenken
  2. Führen Sie das Projekt gemäß der Projektbeschreibung durch.
  3. Geben Sie Ihre Programmdokumentation von 2-3 Seiten ab und führen Sie uns Ihr fertiges Projekt vor.

Abgabetermin: 31.03.2006

Evaluation
Evaluationen: 01.12.2005
WS 2005/06(Ergebnisse der schriftlichen Evaluation vor Weihnachten. Die Bewertung ist in der Tabelle relativ zu den Bewertungen der Grundstudiumsveranstaltungen der Fakultät für Elektrotechnik und Informatik der TU Berlin gezeigt.)