Algorithmen und Datenstrukturen

[Link]. Marc Fischlin, SS 2023

01
Einleitung

Folien beruhen auf gemeinsamer Veranstaltung mit Christian Janson aus dem SS 2020

13. Oktober 2010 | [Link] Fischlin | Kryptosicherheit | 1

 Algorithmen

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 01 Einleitung | 2

 Verortung

Eingabe
Computer
Programm
Algorithmus: höherer Setzen
:

Abstraktionsebene laufendes Programm Um

als Programm Euklidischer

Algorithmus Algorithmus Ausgabe
(ca.300 [Link].)
Abstraktion
+Verallgemeinerung Problem/
berechne ggT von a,b
Modell

(Problem-)
berechne ggT(21,39) =3
Instanz

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 01 Einleitung | 3

 ·
endlich viele Schritte
Algorithmus
T
·

ausführbar

Algorithmus:
Eine aus endlich vielen Schritten bestehende,
ausführbare Handlungsvorschrift
Eine aus endlich zur eindeutigen
vielen Schritten bestehende, ausführbare
Handlungsvorschrift
Umwandlung zur eindeutigen
von Eingabe- Umwandlung von
in Ausgabedaten.
Eingabe- in Ausgabedaten
Wa
nach Cormen et al., Introduction to Algorithms

Namensgeber: Ibn Musa Al-Chwarismis (ca. 825):

Buch: Regeln der Wiedereinsetzung und Reduktion,
ins Lateinische als „Al-Chwarismis Buch“ übersetzt

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 01 Einleitung | 4

 Diese Eisenschaffen soll en
Algorithme
Allgemeine Charakteristika Algorithmen (I) fu
er-len
endliche
keine Code
zeilen
not

↑
übereinstimmende Finitheit Algro hat>
-

liche Beschreibung
end
eine

Charakterisierung
in der Literatur! berechenbar Terminierung stopptProgramm =>
in

Zeit
Effektivität
hal : wer

auf Maschine aufführbar

Asanrayn
Allgemeinheit >
-

nicht
ein zehe
fergebenbeliebige Korrekt
sein Determiniertheit ↑
für selve

Korrektheit sondern für Determinismus

&Eingebe
↓ Eingeben
.

↓ gidget
Falls termiet , ,
Alg .
n

ist die anwendbar bestimmt

Ausgabe
mich i
Lasalsag ,
überde efekteflik
190
iç

kored the it likten

#
%
rezgewihdi
Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 01 Einleitung | 5
 Allgemeine Charakteristika Algorithmen (II)

Finitheit
berechenbar Terminierung
Effektivität

ist alle
Auß
hat endliche Zeile
Determiniertheit
↑
Code
Allgemeinheit
Terminerba s

Finitheit: Algorithmus hat endliche Beschreibung

Korrektheit Determinismus
Terminierung: Algorithmus stoppt in endlicher Zeit
Effektivität: Schritte sind auf Maschine ausführbar
anwendbar bestimmt

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 01 Einleitung | 6

 nicht durch Maschie berechenbres Problem
Ip Für
:

"Halte problem"
Gesucht "Programm"
: I mit
anhält
PCP)
2
wenn
H() =

senst

& Foto (14 . 04 .

23 08 : 27)
,
 Allgemeine Charakteristika Algorithmen (III)

Determiniertheit: > soarç aynıFinitheit -

gleicher EingabeTerminierung
Algorithmus liefert bei berechenbar
Effektivität
gleiche Ausgabe > Zufallszahlen -

determiniertheit nicht
generator ist
>
-

Determinismus: > gididat ayn -

Determiniertheit
,

Allgemeinheit
Algorithmus durchläuft für gleiche Eingabe
Korrektheit
immer die gleichen Schritte/Zustände Determinismus
Random quick Sort

anwendbar bestimmt

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 01 Einleitung | 7

 Allgemeine Charakteristika Algorithmen (IV)

Finitheit nicht für

Allgemeinheit: -

berechenbar Terminierung
Algorithmus
einige
für Eingaben
bestimmte

Effektivität
ganze Problemklasse anwendbar
sondern
alle beliebige
für
Eingaben
Korrektheit:
Allgemeinheit Determiniertheit
Falls Algorithmus terminiert, ist die
Korrektheit Ausgabe richtigDeterminismus
Primachentester (für Effizienz
Kunde of
% Karakt
anwendbar bestimmt
100

verzichtet)

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 01 Einleitung | 8

 Beispiel: Euklidischer Algorithmus (I)

gcd(a,b) // a,b0 integers

1 IF b==0 THEN
2 return a
3 ELSE //a mod b Divisionsrest
4 return gcd(b,a mod b)

Finitheit: Algorithmus hat endliche Beschreibung 

Terminierung: Algorithmus stoppt in endlicher Zeit
Effektivität: Schritte sind auf Maschine ausführbar 
g ad 70) > yed (70 30)
(100 ,
gad
-

(30 10) gad (0 0)

-
O10
,
"
>
-

, + ,
>
-

-- 1-

10
Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 01 Einleitung | 9
 Beispiel: Euklidischer Algorithmus (II)

gcd(a,b) // a,b0 integers

1 IF b==0 THEN
2 return a
3 ELSE //a mod b Divisionsrest
4 return gcd(b,a mod b)

Finitheit: Algorithmus hat endliche Beschreibung

Terminierung: Algorithmus stoppt in endlicher Zeit 
Effektivität: Schritte sind auf Maschine ausführbar
Divisionsrest ist stets zwischen 0 und b1, so dass
zweites Argument in jeder Iteration um mindestens 1 kleiner wird
und schließlich Basisfall b=0 erreicht wird
Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 01 Einleitung | 10
 Beispiel: Euklidischer Algorithmus (III)

gcd(a,b) // a,b0 integers

1 IF b==0 THEN
2 return a
3 ELSE //a mod b Divisionsrest
4 return gcd(b,a mod b)

Determiniertheit: gleiche Eingabe, gleiche Ausgabe 

Determinismus: gleiche Eingabe, gleiche Schritte 

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 01 Einleitung | 11

 Beispiel: Euklidischer Algorithmus (IV)

gcd(a,b) // a,b0 integers

menn
die Reihenfolge unterschiedli
ist
1 IF b==0 THEN d (70 100) + 2cd (100 701
& , ,

I
2 return a
3 ELSE //a mod b Divisionsrest
4 return gcd(b,a mod b) 19

Allgemeinheit: für Problemklasse anwendbar 

Korrektheit: falls terminiert, Ausgabe richtig 
Folgt aus gcd(𝑎, 𝑏) = gcd(𝑏, 𝑎 𝑚𝑜𝑑 𝑏) (ohne Beweis)
sowie gcd 𝑎, 0 = 𝑎
Terminierungsbedingung
Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 01 Einleitung | 12
 01 Einleitung
Lernziele Algorithmen 02 Sortieren

Abschnitte 6 und 7
geeignete Modellierung
von Problemen erlernen
Entwurfs-
paradigmen Übungen
kennenlernern
Umsetzung in
Abschnitt 7 Algorithmus Programme können
(hier: Java)

wichtige
Algorithmen
Analysetechniken erlernen (dorretheit
wissen
Abschnitt 6
Korrektheit Terminierung Aufwand

Abschnitte 2 und 8 (auch 6,7) weSchade inten

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 01 Einleitung | 13
 Vorlesung und Übung (I)

Eingabe
Computer
Programm

Algorithmus Ausgabe

Abstraktion
+Verallgemeinerung Problem/
Modell Übung
Vorlesung
(Problem-) +Übung
Instanz

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 01 Einleitung | 14

 Vorlesung und Übung (II) Code generiert mittels ChatGPT auf die Frage
„Wie könnte bfs in java aussehen“, 21.März 2023

…
lauffähiger 1 public void bfs(int s) {
2 Eingabe visited
boolean[]
Java-Code
= new boolean[V];
Computer
3 LinkedList<Integer> queue
Programm
= new LinkedList<>();
4
5 visited[s] = true;
6 [Link](s);
Pseudocode: …
Algorithmus Ausgabe
einfacher Zugang

BFS(G,s)
Abstraktion
+Verallgemeinerung Problem/
Modell Übung
1 [Link]=GRAY; …
2 newQueue(Q); Vorlesung
3 (Problem-)
enqueue(Q,s); +Übung
… Instanz

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 01 Einleitung | 15

 Wie verhalten sich
Determiniertheit (gleiche Eingabe, gleiche Ausgabe) und
Determinismus (gleiche Eingabe, gleiche Schritte/Zustände)
zueinander?
Determiniertheit = DeterminisO mus
Das Algorithme
Das Algorithms hat die 2
führt
&- selbe Schritte/Zustände
steich Ausgebe gleiche
bei

Figeben
L
a
-
bei
gleicher Eingabe durch
Was halten Sie von folgender Idee, die
- mod-Funktion
(z.B. für den Euklidischen Algorithmus) umzusetzen?

MOD(a,b) //a,b0 integers Timmiert

1 WHILE a>=b DO nicht
2 a=a-b fürb =
0

3 END WHILE
4 return a

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 01 Einleitung | 16

 Datenstrukturen

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 01 Einleitung | 17

 Datenstrukturen

Datenstrukturen:
Eine aus endlich vielen Schritten bestehende,
ausführbare Handlungsvorschrift zur eindeutigen
Eine Datenstruktur ist eine Methode,
Umwandlung
Daten für den von Eingabe-
Zugriff in Ausgabedaten.
und die Modifikation zu organisieren

nach Cormen et al., Introduction to Algorithms

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 01 Einleitung | 18

 Beispiel: Array

0 1 2 3 4 5 6 7 8

A 12 47 17 98 72

Datenstrukturen beinhalten

Daten + Strukturbestandteile
-
720]
A
- iste
z.B. A[7] ist achter erste

Eintrag im Speicher

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 01 Einleitung | 19

Abstrakte Datentypen (ADTs) und Datenstrukturen

näher an der Anwendung

Beispiel:

Stack mit Operationen

Abstrakter Datentyp („was“) isEmpty,pop,push
new Stock

Übergang fließend; ADTs

werden daher oft auch als
Datenstruktur bezeichnet

Stack-Operationen
Datenstruktur („wie“) als Array
oder verkettete Liste

näher „an der Maschine“

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 01 Einleitung | 20

 Lernziele Datenstrukturen
Abschnitte 3-5
Vor- und Nachteile
der verschiedenen Strukturen
Einfache erkennen
Datenstrukturen Übungen
beherrschen
Umsetzung in
Abschnitt 3 Daten- Programme können
strukturen (hier: Java)

komplexe
Datenstrukturen
Analysetechniken erlernen
kennenlernen
Abschnitte 4 und 5
Korrektheit Terminierung Aufwand

Abschnitte 3-5
Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 01 Einleitung | 21
 Algorithmen
und
Datenstrukturen

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 01 Einleitung | 22

 Datenstrukturen in Algorithmen

abstrantes Modell
verwendet Daten-
Problem Algorithmus
struktur

Dijkstra(…)
gesucht:
„Suche 1 … Datenstruktur,
kürzesten 2 WHILE… mit der man leicht
Weg“ 3 „gib mir den kleinste Einträge
kleinsten Wert“ finden kann
Abschnitt 6 4 …

Datenstruktur wirkt sich auf Effizienz

des Algorithmus aus
Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 01 Einleitung | 23
 Algorithmen für Datenstrukturen

Daten- verwendet Daten-

Problem Algorithmus
struktur struktur

„Konstruiere eine
10x30 =
O
300

Datenstruktur, mit der

man schnell kleinste
300 F
250-3-
Werte finden kann“

komplexere einfache
Datenstruktur Abschnitt 4 (auch 3 und 5) Datenstruktur
(z.B. Heap) (z.B. Array)

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 01 Einleitung | 24