[Logo of DHBW Stuttgart]

Algorithmen und Komplexität 2022

Vorlesung an der DHBW Stuttgart, 2022.
Stephan Schulz

Inhalte

Algorithmen sind eindeutig beschriebene Vorgehensweisen zum Lösen von bestimmten, wohldefinierten Problemen. Algorithmik beschäftigt sich mit den Eigenschaften, der Analyse, und dem Design von Algorithmen. Sie ist der Kern der Informatik.

In dieser Vorlesung beschäftigen wir uns mit dem Entwurf und der Evaluierung von Algorithmen. Wir untersuchen, wie man Stärken und Schwächen von bestimmten Algorithmen charakterisieren kann, und lernen verschiedenen praktisch relevante Algorithmen und Datenstukturen kennen.

Fragestellungen sind z.B.

Im begleitenden Labor werden viele der vorgestellten Algorithmen und Datenstrukturen in C umgesetzt.

Unterlagen zur Vorlesung

Unterlagen zum Labor AI

FAQ/Häufige Fehler

  1. Wie kann man bei Eingabe vom Terminal EOF/Ende der Eingabe signalisieren?

    Die Ende der Eingabe wird bei den meisten Betriebssystemen durch ^D (CTRL-D/STRG-D) angezeigt. Unter Windows müssen Sie bei den gängigen Terminals ^Z [RETURN] tippen (also zuerst CTRL-Z bzw. STRG-Z, dann noch einmal Return, Enter, DÜ, oder wie immer die Mach-Was-Taste auf ihrer Tastatur heißt).

  2. Wie gebe ich Fehlermeldungen aus?

    Fehlermeldungen sollten im allgemeinen mit fprintf(stderr, "Fehlermeldung\n"); oder ähnlich ausgegeben werden. Insbesondere: Die Ausgabe soll auf dem Standard-Fehler-Kanal (stderr) erfolgen. Sowohl stdout als auch stderr sind normalerweise ans Terminal gebunden. Aber wenn die "normale" Ausgabe direkt weiterverwendet wird (mit einer Pipe), oder in einen Datei umgelenkt wird (mit myprog > myres.txt), dann soll die Fehlermeldung ja trotzdem auf dem Terminal erscheinen, und nicht schweigend die Weiterverarbeitung stören.

    Fehlermeldungen (und die meisten Ausgaben) sollten in der Regel mit einem Zeilenumbruch ("\n") terminiert werden. Insbesondere werden Ausgaben auf stdout in der Regel erst dann ausgegeben, wenn die Zeile komplett ist. Das kann beim Fehlersuchen sehr in die Irre führen, weil man die Ausgabe noch nicht sieht, obwohl das Programm die längst geschrieben hat - die steckte dann im line buffer der Bibliothek, als das Programm abstürzte.

  3. Wenn ich char myarray[1000][1000] erkläre, stürzt mein Programm ab!

    Wahrscheinlich haben Sie die Definition dann in main() oder einer anderen Funktion stehen. Lokale Variablen werden in C beim Aufruf der Funktion auf dem Stack angelegt. Die Größe des Stacks ist bei den meisten Betriebssystemen limitiert. Deswegen sollte man sehr große Datenstrukturen nicht als "automatische" (lokale) Variable realisieren. Je nach Anwendungsfall kann man diese als globale Variable definieren (also außerhalb jeder Funktion) oder mit malloc() allokieren. Globale Variablen werden schon beim Kompilieren bzw. beim Laden des Programms im Data Segment des Prozesses angelegt und haben praktisch keine Größenbeschränkung. Dynamischer Speicher, der mit malloc() allokiert wird, ist ebenfalls weitgehend unbeschränkt, wenn man von der absoluten Speichergröße absieht.

  4. Welche Header sollte ich inkludieren?

    Die, die Sie brauchen. Und nach Möglichkeit nicht mehr. Und alle, die Sie brauchen, sollten im C-Standard vorkommen (mit C99 sind Sie auf der sicheren Seite, C11 unterstützen die meisten Compiler, C17 ist noch deutlich weniger weit verbreitet). Insbesondere sollten Sie nie conio.h inkludieren. Die meisten unserer Programme brauchen stdioh.h und stdlib.h. Manche auch string.h. Andere nach Bedarf. In den UNIX man-pages finden Sie zu den Funktionen der Standard-C-Library immer einen Abschnitt Synopsis, in dem die notwendigen Header zu finden sind.

  5. Das zweite Argument von fopen() hat kein Space!

    Etwas genauer: Das erste Zeichen des zweiten Arguments muß 'r' (für "read"), 'w' (für "write") oder 'a' (für "append") sein. Genaueres finden Sie wieder in der man-page.

  6. Aber mit meinem Compiler geht das!

    Ja, viele Compiler erlauben oder unterstützen Features, die nicht dem Standard entsprechen. Versuchen Sie trotzdem, Standard-konformes C zu schreiben. So bleibt Ihr Code portabel und Sie vermeiden einen lock-in.


DHBW Stuttgart, Prof. Dr. Stephan Schulz