Allgemein

Das aktuelle Kursangebot findet ihr auf der Seite des Lehrstuhls:
http://ddi.cs.uni-potsdam.de/

Grundlagen der Programmierung (GDP)

Ehemals: Grundlagen der Programmierung 1

SWS: 8 (2*2 SWS Vorlesung, 2 SWS Übung, 2 SWS Rechnerübung)
LP: 6

Im allgemeinen wird nur eine Vorlesung gehalten. Der andere Termin ist eher als Ausweichtermin gedacht, falls der Haupttermin ausfallen muss.

Grundlagen der Programmierung 1 handelt von den grundlegenden Eigenschaften und Konzepten der Informatik. Dabei wird auf Datenstrukturen und Algorithmen sowohl in der Theorie, als auch der Praxis eingegangen.

Inhalt

  • Vom Problem zum Algorithmus
  • Grenzen der Algorithmisierung
  • Programmiersprachen (primär Syntax)
    • Elementaranweisungen / Objektbeschreibungen / Konstruktoren / Bezeichner
    • Bedingungen / Kontrollstrukturen
    • Funktionen / Prozeduren
  • Assemblersprachen und Von-Neumann-Rechner
  • Fundamentale Denkkonzepte der Informatik
  • Modellbildung
  • Funktionale Spezifikation
  • Datentyplehre
    • elementare Datentypen
    • Enumeration / Restriktion / Potenzmengen / Aggregation / Generalisation
    • Rekursion
    • Files
    • Bäume
    • Funktionenräume
  • Funktionale Programmierung
    • Funktionen höherer Ordnung
    • Currying
    • Applikation / Substitution
    • Formularmaschinen
    • Rekursion
    • Polymorphie
  • Syntax und Semantik von Programmiersprachen
    • Syntaxdiagramme / Backus-Naur-Form
    • Semantikumgebungen / Fixpunktberechnungen

Nützliche Grundlagen

Dieser Kurs ist als die ultimative Anfängerveranstaltung ausgelegt. Wer allerdings schon einmal programmiert hat, ist bei vielen Übungsaufgaben klar im Vorteil.

Literatur

Auch hier gibt es ein Skript von Prof. Schwill. Andere Literatur wird eigentlich nicht gebraucht, es steht alles im Skript.

Literatur:

  • „Datenstrukturen und Algorithmen“, Güting, Dieker, Teubner-Verlag, 3. Aufl., ISBN 978-3-519-22121-0
    • Im Bestand von Mario Frank

Aufwand

Der Aufwand für das Fach ist moderat. Mittlerweile ist es jedem Studenten freigestellt die Übungsaufgabe zu bearbeiten. Ich empfehle jedem sie sich wenigstens anzuschauen und einen Großteil auch zu machen. Insbesondere die Aufgaben zu den letzten beiden Kapiteln sind wichtig. In der Klausur WS2009/10 haben sie etwa 50% der Punkte ausgemacht.

Klausur

Die Klausur hat es meistens in sich. Prinzipiell ist sie nicht schwierig, aber viele kleine Flüchtigkeitsfehler summieren sich schnell auf. Manchmal ist sie ein wenig einseitig, was die Abdeckung der Themenbereiche betrifft. Man sollte sich auf jeden Fall mit Kommilitonen zusammensetzen und gemeinsam vorbereiten.

Fazit

Man sollte unbedingt am Ball bleiben. Das Niveau schwankt mitunter stark, besonders die Kapitel 4-8 sind relativ einfach. Dies sollte einen aber nicht dazu ermuntern das Fach zu unterschätzen.

Altklausuren

Algorithmen und Datenstrukturen

Ehemals: Grundlagen der Programmierung 2

SWS: 6 (2*2 SWS Vorlesung, 2 SWS Übung)
LP: 6

Inhalt

  • Programmierstile
    • Klassifikation von Programmiersprachen (imperativ/funktional/prädikativ)
  • Abstrakte Datentypen
  • Implementierung von Datentypen
  • Qualität von Programmen
    • Korrektheit und Komplexität
  • Algorithmen auf Zahlen
    • Multiplizieren, Matrizen multiplizieren
  • Entwurfsparadigmen für Algorithmen
    • Divide-and-Conquer
    • Backtracking,
    • Greedy-Methode
  • Algorithmen auf Folgen
    • Durchlaufen, Einfügen, Entfernen,
    • Verknüpfen, Spiegeln, Suchen von Elementen und Teilfolgen, Sortieren
  • Algorithmen auf Bäumen
    • Durchlaufen, Einfügen, Entfernen, Suchen von Elementen, Vergleichen,Optimieren
  • Algorithmen auf Graphen
    • Durchlaufen, Suchen von best. Teilstrukturen (Wegen, Spannbäumen)
  • Algorithmen auf Punktmengen
    • Suchen, Ermitteln ausgewählter Informationen (Distanzen, Clusterbildung)
  • Parallele Algorithmen
    • u.a. Sortieren
  • (NP-harte Probleme)
  • (Probabilistische Algorithmen)

Nützliche Grundlagen

Wie zu erwarten sollte man sich dunkel an GDP1 erinnern. Allerdings werden viele Konzepte in Algorithmen und Datenstrukturen sehr viel plastischer behandelt, was die Sache enorm erleichtert.

Literatur

Es gibt ein (meiner Meinung nach) sehr gutes Skript von Prof. Schwill und sämtliche Vorlesungsfolien auf der Moodle-Seite der Veranstaltung. Andere Literatur wird eigentlich nicht gebraucht, es steht alles im Skript.

Literatur:

  • T. Ottmann, P. Widmayer: Algorithmen und Datenstrukturen, Spektrum-Verlag 2002
  • R. Harper: Programming in Standard ML, E-Book 2011
  • K. Mehlhorn: Data structures and algorithms, Springer-Verlag 1984 (3 Bände)
  • „Datenstrukturen und Algorithmen“, Güting, Dieker, Teubner-Verlag, 3. Aufl., ISBN 978-3-519-22121-0
    • Im Bestand von Mario Frank

Aufwand

Die Übungsaufgaben sind ein wenig knackiger bzw. wirrer als in GDP I. Wenn man sich aber durch die wichtigsten durchgekämpft hat, dann kann man die Klausur gut bestehen.

Klausur

Die Klausur ist meiner Meinung nach einfacher als die von GDP I. Man hat mehr als genug Zeit im Skript nachzublättern und die Aufgaben sowie deren Themenabdeckung sind fair.

Fazit

Meiner Meinung nach einfacher und nützlicher als GDP I. Zusammenfassend würde ich die vorgestellten Algorithmen als „Allgemeinwissen für Informatiker“ bezeichnen.

Altklausuren

studium/kurse/ddi.txt · Zuletzt geändert: 2014/05/18 16:50 von jsohre
CC Attribution-Share Alike 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0