Algorithmen und Datenstrukturen

Praktische Einführung und Programmierung

Stefan Bosse

Universität Koblenz - FB Informatik

1 / 19

Stefan Bosse - Algorithmen und Datenstrukturen - Modul 0 Überblick ::

Überblick

2 / 19

Stefan Bosse - Algorithmen und Datenstrukturen - Modul 0 Überblick :: Mitarbeiter

Mitarbeiter

  1. Prof. Dr. Stefan Bosse, Praktische Informatik (Vorlesung und Übung)

    • Verteilte Künstliche Intelligenz & Sensornetzwerke
    • Betriebssysteme & Virtualisierung
    • Technische Systeme

  2. WiMi Sidar Cilinc (Übung)

    • AG Praktische Informarik

  3. HiWi Valerie Simon, Elena XX (Übung)

3 / 19

Stefan Bosse - Algorithmen und Datenstrukturen - Modul 0 Überblick :: Aufbau der Veranstaltung

Aufbau der Veranstaltung

  1. Vorlesungen

    • Mittwoch 10-12 Uhr (Hauptstrang, Grundlagen)
    • Donnerstag 12-14 Uhr (Nebenstrang, Besondere Themen, wie z.B. Numerik)

  2. Übungen

    • Dienstags 14-16 Uhr
    • Donnerstags 14-16 Uhr
    • Freitags 10-12 Uhr
4 / 19

Stefan Bosse - Algorithmen und Datenstrukturen - Modul 0 Überblick :: Übungsformat

Übungsformat

Notebooks: Alle Übungen sind digital und werden im Web Browser bearbeitet (lokal, ggfs. off-line). Die Inhalte einer Übungseinheit werden als Datei im JSON Format gespeichert und hochgeladen.

  • Es sollen die Datenstrukturen und Algorithmen dieses Kurses in Java (Ver. 7) implementiert und profiliert werden.

    • Profilieren bedeutet: Bestimmung der Rechenzeit für eine Problemgröße, die Anzahl der ausgeführten VM Instruktionen, deren Art und Verteilung, und Untersuchung des Speicherbedarfs.
    • Es wird eine dafür entwickelte Mikro VM (uJ) verwendet die alle nötigen Informationen für das Profiling liefert.

  • In der Vorlesung wird i.A. nur eine Pseudonotation für Algorithmik und Datenstrukturen verwendet.

5 / 19

Stefan Bosse - Algorithmen und Datenstrukturen - Modul 0 Überblick :: Übungsformat

Übungsformat

+

6 / 19

Stefan Bosse - Algorithmen und Datenstrukturen - Modul 0 Überblick :: Leistungskriterien

Leistungskriterien

  1. Übungen

    • Bearbeitung der Übungseinheiten in Einzelarbeit (in Gruppe), alle Abgaben!
    • Abgabe des Übungszettels in digitaler Form als Gruppe (JSON Datei)
    • Programmierung in Java
    • Bewertungsschema 0/1/2
    • Musterlösungen sind in den digitalen Zetteln enthalten und werden mit einem Schlüssel freigeschaltet (gibt es im Tutorium).

  2. Klausur

    • 60-90 Minuten
    • Vor allem Abfrage von Wissen und Verständnis
    • "Programmierung" der Algorithmen und Beschreibung nur in Pseudonotation (standardisiert für diesen Kurs)
7 / 19

Stefan Bosse - Algorithmen und Datenstrukturen - Modul 0 Überblick :: Veranstaltungsformat

Veranstaltungsformat

  • größtenteils in Präsenz

  • Videos mit Nachbesprechung oder als Ergänzung zu Übungen

  • evtl. gelegentlich On-line (Video Meeting)

Für alle die Terminkonflikte haben wird die Veranstaltung tagesaktuell aufgezeichnet und steht On-line zum Abruf.

8 / 19

Stefan Bosse - Algorithmen und Datenstrukturen - Modul 0 Überblick :: Veranstaltungsformat

Veranstaltungsformat

  • größtenteils in Präsenz

  • Videos mit Nachbesprechung oder als Ergänzung zu Übungen

  • evtl. gelegentlich On-line (Video Meeting)

Für alle die Terminkonflikte haben wird die Veranstaltung tagesaktuell aufgezeichnet und steht On-line zum Abruf.

Alle Dokumente, Videos, und Übungen gibt es hier: https://edu-9.de/Lehre/ad1k.

9 / 19

Stefan Bosse - Algorithmen und Datenstrukturen - Modul 0 Überblick :: Inhalte

Inhalte

  1. Einführung in Komplexität und Effizienz, Grundlagen
  2. Darstellung von Algorithmen: Diagramme und Pseudonotation
  3. Numerische Algorithmen
  4. Abstrakte Datentypen
  5. Arrays und Tabellen
  6. Datenbanken und Datenorgansation
  7. Sortierverfahren (für geordnete Daten)
  8. Mengen: Ungeordnete Daten
  9. Warteschlange und Stapelspeicher
  10. Listen
  11. Bäume
  12. Graphen
10 / 19

Stefan Bosse - Algorithmen und Datenstrukturen - Modul 0 Überblick :: Literatur

Literatur

Algorithmen und Datenstrukturen
Thomas Ottman
Peter Widmayer
Spektrum Verlag

Algorithmen und Datenstrukturen
Eine Einführung in Java
Gunter Saake, Kai Uwe Sattler
dpunkt Verlag

11 / 19

Stefan Bosse - Algorithmen und Datenstrukturen - Modul 0 Überblick :: Was sind Algorithmen und Datenstrukturen?

Was sind Algorithmen und Datenstrukturen?

  1. Algorithmen: Wie werden Daten berechnet?
  2. Datenstrukturen: Wie sind Daten strukturiert?
  3. Laufzeit und Komplexität: Wie effizient sind Algorithmen und Datenstrukturen?
                                             ――――┐             
┌――――――――――┐                                     │             
│Problem   │   ┌―――――――――――――┐   ┌――――――――――┐    │             
├――――――――――┼――▶│Algorithmus A├――▶│Programm A│    │             
│Aufgabe   │   └―――――――――――――┘   └――――――――――┘    │ Programmier-
└――――――――――┘   ┌―――――――――――――┐   ┌――――――――――┐    │ sprachen    
      ┌――――――――┤Algorithmus B├――▶│Programm B│    │             
      │        └――――――┬――――――┘   └―――――┬――――┘    │             
┌―――――┴――――┐          │     Messen?    │         │             
│Daten-    │          ▼                ▼     ――――┘             
│struktur 1│   ┌――――――――――――――――――――――――――――┐                  
└――――――――――┘   │  Komplexität / Effizienz ? │                  
┌――――――――――┐   └――――――――――――――――――――――――――――┘                  
│Daten-    │                                                   
│struktur 2│                                                   
└――――――――――┘
12 / 19

Stefan Bosse - Algorithmen und Datenstrukturen - Modul 0 Überblick :: Historischer Überblick: Algorithmen

Historischer Überblick: Algorithmen

300 v. Chr.
Euklids Algorithmus zur Bestimmung des ggT (beschrieben im 7. Buch der Elemente), also des größten gemeinsamen Teilers, mit dem etwa ggT(300, 200) = 100 sehr effizient berechnet werden kann, ist die erste Beschreibung eines Verfahrens, das modernen Kriterien für Algorithmen gerecht wird.
800 n. Chr.
Der persisch-arabische Mathematiker Muhammed ibn Musa abu Djafar alChoresmi (oft auch als »al Chworesmi« oder »al Charismi« geschrieben) veröffentlicht eine Aufgabensammlung für Kaufleute und Testamentsvollstrecker, die später ins Lateinische als Liber Algorithmi übersetzt wird.

Das Wort Algorithmus ist ein Kunstwort aus dem Namen dieses Mathematikers und dem griechischen »arithmos« für Zahl.

1574
Adam Rieses Rechenbuch verbreitet mathematische Algorithmen in Deutschland.
1614
Die ersten Logarithmentafeln werden algorithmisch berechnet – ohne Computer dauerte dies 30 Jahre!
1703
Binäre Zahlensysteme werden von Leibnitz eingeführt. Diese Zahlensysteme bilden die Grundlage der internen Verarbeitung in modernen Computern.
13 / 19

Stefan Bosse - Algorithmen und Datenstrukturen - Modul 0 Überblick :: Historischer Überblick: Algorithmen

Historischer Überblick: Algorithmen

1815
Augusta Ada Lovelace, die erste »Computer-Pionierin«, wird geboren. Sie entwickelt schon früh Konstruktionspläne für verschiedenartige Maschinen, wird Assistentin von Babbage und entwirft Programme für dessen erste Rechenmaschinen.
1822
Charles Babbage entwickelt die sogenannte Difference Engine, die in einer verbesserten Version 1833 fertiggestellt wird. Später entwickelt er auch die Analytical Engine, die bereits die wichtigsten Komponenten eines Computers umfasst, aber niemals vollendet wird.
1931
Gödels Unvollständigkeitssatz beendet den Traum vieler damaliger Mathematiker, die gesamte Beweisführung aller Sätze in der Mathematik mit algorithmisch konstruierten Beweisen durchzuführen.
1936
Die Church’sche These vereinheitlicht die Welt der Sprachen zur Notation von Algorithmen, indem für viele der damaligen Notationen die gleiche Ausdrucksfähigkeit postuliert wird.
danach
Mit der Realisierung der ersten Computer erfolgte natürlich der Ausbau der Algorithmentheorie zu einem eigenen Wissenschaftsgebiet.

Auch für den Bereich der Datenstrukturen können lang zurückreichende Wurzeln gefunden werden, etwa das Indexierungssystem historischer Bibliotheken.

14 / 19

Stefan Bosse - Algorithmen und Datenstrukturen - Modul 0 Überblick :: Grundprinzipien

Grundprinzipien

Algorithmen sollen einfachen zu beschreiben und zu lesen sein. Einfache Beschreibungssparchen sollten verwendet werden:

  • Ablauf- und Struktugramme
  • Abstrakte Notationen
  • Mathematische Notation, Datenflussdiagramme
  • Programmiersprachen

Ablaufstrukturen bzw. Programmiersprachen sollten beschränkt sein, d.h. keine beliebigen Eingänge und Ausgänge im Ablausfluss besitzen ⇒ Dann unbeschränkte Ablaufstrukturen mit Sprungbefehlen, goto

15 / 19

Stefan Bosse - Algorithmen und Datenstrukturen - Modul 0 Überblick :: Datenstrukturen

Datenstrukturen

Die Strukturierung von Daten hat nicht unbedingt Einfluss auf die Effizienz. Die Strukturierung soll vor allem die Beschreibung der Algorithmen vereinfachen. Analogie zu Datenstrukturen: Funktionen

16 / 19

Stefan Bosse - Algorithmen und Datenstrukturen - Modul 0 Überblick :: Datenstrukturen

Datenstrukturen

https://codeandart.at/code/processing/datenstrukturen

Unterteilung von Datenstrukturen in statische und dynamische Strukturen (können wachsen).

17 / 19

Stefan Bosse - Algorithmen und Datenstrukturen - Modul 0 Überblick :: Datentyp versa Datenstruktur

Datentyp versa Datenstruktur

https://www.computerweekly.com/de/definition/Datentyp Datentypen sind primitive Datenstrukturen, elementar und konkret, sie werden durch die Programmiersparche unterstützt. Datenstrukturen gehören i.A. zu abstrakten Datentypen mit erforderlicher Algorithmik.

18 / 19

Stefan Bosse - Algorithmen und Datenstrukturen - Modul 0 Überblick :: Tasxonomie der Datenstrukturen

Tasxonomie der Datenstrukturen

https://www.computerweekly.com/de/definition/Datentyp Java hat zwei Hauptdatentypen: primitive und nicht-primitive

19 / 19