Nächste Seite: Fr 18. Jul 13:33:15 Aufwärts: The 11 ... Vorherige Seite: 2025-07-18 ...before ...vhdl3network20250716.vhdl
(C) as Excerpt, David Vajda
2025-06-08
Algorithmen in C, Exzerpt, Robert Sedgewick
1.) Laufzeit von Algorithmen, Analyse von Algorithmen
1, N, log N, N log N, N^2, N^3, 2^N
1: konstant, bzw,
1 oder 3 mal oder 4 mal oder 8 mal, waehrend N ist 2048 bis 4G
2: np vollstaendigkeit
deterministisch: schleife, Hashwerte, immer weiterrechnen, Pruefsumme
aber auch: fakultaet
zerlegbar:
4! = 4*3!
3! = 3*2!
...
oder sortieralgo:
innere schleife
aeussere schleife
wuerde sagen, n! problem, aber egal
wuerde sagen
log N
oder N log N problem
ok, nur, das eine haengt nicht vom anderen ab
deterministisch nicht deterministisch
knoten im baum, ist nicht deterministisch
knoten von der schlange, nachbarn rauf
nachbarn in der schlange, kommt der erste runter
wieder nachbarn und so weiter
aber was passiert, haengt ab von knoten nachbarn und entscheidung
ok: dieses problem, beschreibung
richtig lernen, nebenbei:
alles aufschreiben was da steht, mit oder ohne verstehen, verstehen hier mal ok
aber einfach aufschreiben, also da steht
sortieralgorithmen
werke anderer
und begriffe in np
Sortieralgorithmen:
Selection Sort
Insertion Sort
Bubble Sort
wichtigstes vorweg:
Selection Sort
Insertion Sort
Bubble Sort
SIB
BIS
BSI
oder wie auch immer, kann man sich merken
Selection Insertion Bubble
Vorsicht, Bubble nicht gleich Quicksort
Bubble einfach um zu setzen, immer paarweise
desweiteren:
Selection Sort
Insertion Sort
Bubble Sort
Quick Sort
Quick Bubble Selection Insertion
Dann: Shellsort, bisher nicht gehoert, merken ueber
BASH, Shell, OK und eben so netter Name
Selection Insertion Bubble Quick Shell
SQBSI
Dann kommt:
Distribution Counting?
Sortieren von Dateien und Grossen Datensaetzen
Quicksort:
Der Algorithmus
Beseitigung der Rekursion
kleine Teildateien ...
Digitales sortieren
???
digitales sortieren neues phaenomen,
Digitales sortieren, mehrere algo ebenso wie klassisch, verschiedene namen
Bits
Radix Exchange Sort
Straight Radix Exchange Sort
lineares sortierverfahren
neues wort:
prioritaetswarteschlangen, begriff heaps
heapsort
neuer algo: heapsort
also jetzt
SQSBI
Shell Sort
Quick Sort
Selection Sort
Bubble Sort
Insertion Sort
Stop: die 3 klassiker sind
Insertion Selection Bubble
vom Namen sind klassiker
Insertion Selection Bubble Quick
Insertion Selection Bubble Quick Shell
neue Namen
Heapsort
Klassiker unter den Namen wie vielleicht auch Heapsort
Mergesort
also, die 4 klassiker plus 1 = shellsort
und die anderen 2 klassiker vom namen
insertion selection bubble quick
shell
heap merge
dazu kommen, algos aus dem digitalen sortieren, quasi
klassiker unter den namen
bits
radix exchange sort
straight radix exchange sort
also
insertion selection bubble quick
shell
heap merge
bits
radix exchange sort
straight radix exchange sort
dann kommen noch namen im bereich mit dem ganzen
digitales sortieren
externes sortieren
das vielleicht einfach merken, wie die algo selber
digitales sortieren
externes sortieren
digital/extern
dann kommt dazu
digital,
radix exchange, wurzel austausch oder was auch immer
prioritaetswarteschlangen
heap
digital
prioritaetswarteschlangen, heap
mergesort, mischen
mischen,
bottum up mergesort
externes sortieren
sortieren-mischen
mehrweg-mischen
replacement selection
mehrphasen mischen
neue begriffe
digitales sortieren
externes sortieren
radix exchange sort
lineares sortierverfahren
prioritaetswarteschlangen
heaps
heapsort
mergesort
mischen
externes sortiern
sortieren-mischen
ausgeglichenes mehrweg-mischen
replacement selection
mehrphasen-mischen
also, jetzt namen unter den sortieralgo
bubble insertion selection
bubble insertion selection quick shell
bubble insertion selection quick shell merge heap
mit allen namen
bubble insertion selection quick shell merge heap
radix exchange
straight radix exchange
jetzt gibt es
digitales sortieren und
externes sortieren
aber dazu noch
mischen
mischen ist jetzt ein neuer begriff, so sehr
prioritaetswarteschlangen nach pater noster klingt finde ich ist
prioritaetswarteschlange, einfach heap
auch so ein begriff
trotzdem
mischen digital extern
und extern und mischen scheint gut zusammen zu tun
sortieren mischen, mehrweg mischen und so weiter
geheort zu extern ok
also einteilung
mit prioritaetswarteschlange
digital
extern
prioritaetswarteschlange = heap
mischen
4 grosse
digital
extern
heap
merge
DEHM
MEHD
oder so
Extern Digital Merge Heap
EDMH
ab, jetzt: 2025-06-08
1.) sortieralgorithmen lernen ohne wenn und aber und moeglichst ohne Inhalt
Kommentar des Vajdas: Lernen mit inhalt macht selten sinn
Dafuer gibt es ein anschauliches beispiel, man muss erst wissen wie ein
entsprechendes ding heisst, benutzt man den namen dann haeufig genug
wird man schon frueher oder spaeter lernen was drin steckt
beispiel: sie wissen wahrscheinlich auch schon was ein auto ist, und den
inhalt werden die wenigsten kennen, gerissenste ausgebildete automechaniker
vielleicht. trotzdem werden sie nicht erst den inhalt des autos studieren
und sich dann merken was es ist
das ist mit Algorithmen genauso. erst lernen, wie sie heissen,
ein paar sortieralgorithmen kann ich mir besonders gut merken, dazu
gehoeren
ich weiss nie, welcher es jetzt ist
insertion sort oder selection sort
und bubble sort
wenn es aber zum beispiel um radix exchange sort geht, finde ich reicht
erst mal der name alleine. einige algorithmen wird man immer mehrr lernen
erst den, dann den. zum Beispiel, weiss ich mittlerweise SHA256 und so weiter
aber ich weiss, was normales Hashing ist, normalst, wie bei sedgewick
dazu kommt Adler32, Fletcher's checksum, Parity, Arith Mittel
einiges weiss man schon ohne es zu wisen, wie es heisst, indem man die
namen lernt weiss man es am ende, inhalte kommen immer mehr dazu
mit den lernen ist es wie mit menschen aus gebildeten familien
man sagt, das Linus Torvalds aus einer Familie mit Naturwissenschaftlern
stammt, das ist zu erkennen am Namen und er macht immer wieder menschen
darauf aufmerksam keine zu sein.
da mag er recht haben.
mein Name ist David, und sie sind trotzdem nicht alle ganz dumm
Lempel ziv ist ein gutes Beispiel, aber
David Ricardo ein anderes
Also, totalschaden wuerde ich nicht sagen. Sondern, mein vater war
phil prof, schoene buecher muss ich moegen, meine mama phil doktor und
schreibt.
gut, aber: ich sage so:
man sagt im deutschen, in die gefahr in die man sich begibt, kommt man
drin um. das ist richtig. manche leute vermeiden deswegen die gefahr
um nicht drin um zu kommen, muessen sie sich nicht negativ anrechnen
kommt mit dem alter, aber - sich in keine gefahr zu begeben, ist auch
eine gefahr. nicht nur das - einen tot muss man sterben
doch wie lernen leute in rein naturwissenschaftlichen familien begriffe
besser, indem sie - sie staendig heeren
wer info lernen will, der muss einfach, wenn die family es nicht tut
staendig die begriffe sagen, die in lehrbuechern stehen
deswegen unterstuetze ich keine angriffe gegen religioese, die etwas
verehren was nicht ist, oder leute die etwas erklaeren ...
ich sage: das kommt vielleicht spaeter, wenn sie bereits wissen, was es Ist
kann man naemlich lernen und sie kommen auch aus einer welt voller sprache
das ist das erste. das zweite ist, dass dieses thema was ich hier
sage unwuerdig ist, aus einem grund. es wurde das NP Vollstaendigkeitsproblem
geloest, und diese sprechweisen sind es.
sie sind allenfalls lernwissenschaftlich oder erziehungswissenschaftlich
die reinste erfindung allenfalls doch ein NP Vollstaendigkeitstheorem
zu loesen ist viel besser, deswegen ersparen wir uns diesen ganzen
mist.
1
log N
N
N log N
N^2
N^3
2^N
1: ein mal oder hoechstens mehrere male, konstante laufzeit
log N: Laufzeit eines Programm ist logarithmisch
N: Laufzeit eines Programms ist linear
N log N: mangels eines passenden adjektivs: linearithmisch: Robert Sedgewick
N^2: laufzeit eines programms ist quadratisch
N^3: programm hat kubische laufzeit
2^N: exponentielle laufzeit
1: konstante laufzeit
log N: logarithmisch laufzeit
N: lineare laufzeit
N log N: linearithmisch: Robert Sedgewick
N^2: quadratische laufzeit
N^3: kubische laufzeit
2^N: exponentielle laufzeit
Adjektive, auftreten:
1: konstante laufzeit
vermutung: zum beispiel rest vom programm ...
viele programme fuehren anweisungen durchschnittlich ein oder mehere male aus
nicht mehr oder weniger
log N: logarithmisch laufzeit:
kennzeichen, bezueglich der laufzeit, symptomatisch: mit wachsenden N wird laufzeit
allmaehlich langsamer
loesen umfangreiches problem, wandeln es in kleinere probleme um...
verringern den umfang um einen etwas kleineren geringeren
N: lineare laufzeit
Die Laufzeit ist ebenso gross, wie die Anzahl der Daten, proportionaler faktor...
N log N: linearithmisch: Robert Sedgewick
zerlegen das programm in kleiner probleme, die immer kleiner werden,
loesen indem sie in kleinere Teilprobleme aufteilen
und kombinieren ddan diese loesungen.
N^2: quadratische laufzeit
auftreten: typisch paarweise kombinationen von datenelementen
doppelt verschachtelte schleife typisch i=0..N, j=0..N
N^3: kubische laufzeit
2^N: exponentielle laufzeit
typisches auftreten: gewaltsame methoden, brute Force Attack
versuch alle Hashwerte durch brute force zu erraten
oder passwoerter zu erraten
log N:
symptomatisch: werden mit wachsenden N allmaehlich langsamer
auftreten: umfangreiches problem
umfangreiches problem loesen indem sie es in einen kleineres problem umwandeln,
wobei sie den umfang um einen gewissenkonstanten teil verringern
N log N:
ebenso, aber sie kombinieren am ende die entstandenen loesungen wiederum noch zusaetzlich miteinander
das waere das erste thema:
Analyse von Algorithmen
Klassifikation von Algorithmen
Berechnungskomplexitaet
Jetzt der Begriff der Schranke, also
Analyse von Algorithmen
Klassifikation von Algorithmen, hier typischerweise
1, N, log N, N, N log N, N^2, ...
Berechnungskomplexitaet
Jetzt der Begriff der Schranke, also
Hier: g(N), O(f(N))
was heisst das?
na ja, wir haben nicht nur 1, N, log N, ...
sondern in wirklichkeit haben wir natuerlich eine funktion, bzw. abbildung
die laufzeit betraegt:
g(N)
eines programms
man koennte es auch f(N) h(N) ... nennen
gut, die laufzeit betraegt einfach
g(N)
und wir gehen aus, dass es sich nicht einfach um eine wie auch immer
sehr lineare abbidung handelt
f(N) waere wiederum eine Abbildung bezogen auf eine Menge N, die sich
sagen wir nahezu konstant verhaelt
f(N) = k, sagen wir
aber, alternative denkweise
f(N) > g(N)
das gilt immer, es gilt fuer alle N
g(N) < f(N)
gut, dabei wird f(N) von g(N) nie ueberschritten, dann laesst sich
g(N) als obere Schranke annehmen
obere und untere Schranke
obere und untere Grenze
Minimum und Maximum
Supremum und ...
Minimum und Maximum obere und untere Grenze
obere und Untere Schranke ...
obere Schranke: O
untere Schranke: U
mathematisch meist: S, obere schranke
s: untere Schranke
so, dann ist
O(f(N))
obere schranke von g(N)
ganz einfach, unter einer bedingung
Konstante c0 und N0
fuer alle N > N0
das heisst nicht beliebig, wie immer anfang und ...
c0 f(N)
das heisst, wir denken ab einem initialwert, anfang,
vollstaendige induktion z.B.
und ab dem gilt c0 und erst ab N0 gedacht
... ok
also:
Analyse von Algorithmen
Klassifikation von Algorithmen, hier typischerweise
1, N, log N, N, N log N, N^2, ...
Berechnungskomplexitaet
Jetzt der Begriff der Schranke, also
Hier: g(N), O(f(N))
gut, jetzt:
Analyse von Algorithmen
Klassifikation von Algorithmen, hier typischerweise
1, N, log N, N, N log N, N^2, ...
Berechnungskomplexitaet
Jetzt der Begriff der Schranke, also
Hier: g(N), O(f(N))
analyse des durchschnittlichen falls
wir hatten,
durchschnittlicher fall an verteilung von daten +
verteilung von daten:
na ja, sortieralgorithmus ist wohl deterministisch, wenn man zum beispiel
die schleifen anguckt
trotzdem: das vertauschen wird bei, trotz gleichbleibender vergleiche
mehr, also wenn die verteilung anders ist, mehr taeusche
eventuell wenn nicht durch den ersten durchlauf schon alles richtig einfach
getauscht wurde
vorsicht tricky, nicht so schnell
so, deterministisch bleibt deterministisch
anderes problem:
graph: guenstige verteilung der daten
2. problem: programm selbst kann muss aber nicht hinzukommen
BFS: stur die knoten in der ersten permutation wie vorgegeben an nachbarn durchlaufen
das ist auch eine entscheidung, eine sture entscheidung
aber, es gibt die moeglichkeit sich trotzdem noch weitere entscheidungen einfallen
zu lassen, indem ich noch was dazu tue
aber: hier arbeitet programm an entscheidungen, immer dasselbe zu tun, ist auch eine
nur: hier haengt es von der verteilung der daten selber ab
aber: anders problem
wachsendes N
OK, wachsendes N, mehr Daten ist ein problem der Verteilung weil je groesser eine menge
ist, die kardinalitaet ist teil der menge
aber: man kann die elemente bei gleicher menge anders verteilen
bei einigen programmen vielleicht mehr oder weniger egal wo
bei anderen gar nicht ...
unguenstigster fall
Analyse von Algorithmen
Klassifikation von Algorithmen, hier typischerweise
1, N, log N, N, N log N, N^2, ...
Berechnungskomplexitaet
Jetzt der Begriff der Schranke, also
Hier: g(N), O(f(N))
analyse des durchschnittlichen falls
naeherungsweise und asymptotische ergebnisse
Name: Robert Sedgewick
Obere und untere schranke, O und o
eigentlich,
Supremum und Infimum
Mathematische Grundlagen:
Luise Unger, Fernuni Hagen
obere untere Schranke
obere und untere Grenze, Minimum und Maximum
Supremum und Infimum, S und s
alternative Schreibweise,
Supremum: S
infimum: s
Obere Schranke???: O
Untere Schranke???: U
Maximum??????????!!!: M
Minimum??????????????!!!: m
andere Formulierung:
O-Schreibweise
also, Obere Schranke, O(f(N))
Obere schranke, schreibweise, wenn f(N) diese obere Schranke angibt.
Berechnungskomplexitaet
hier begriff:
obere schranke u.
untere schranke
O-Symbolik,
O-Schreibweise
enthaelt impliziet, die Konstanten
c0 und N
Naeherungsweise und assymptotische Ergebnisse
1. Frage, ..
erst mal das oben in der liste ergaenzen
erste frage: bisher haben wir
1
N
lg N
N lg N
N^2
...
zweite frage:
es gibt ja polynome auch bei robert sedgewick ist die rede von polynomen
wie waere es mit
2^N + N^3 + N^2 + N + 1 + ln N
1: konstante laufzeit
log N: logarithmisch laufzeit
N: lineare laufzeit
N log N: linearithmisch: Robert Sedgewick
N^2: quadratische laufzeit
N^3: kubische laufzeit
2^N: exponentielle laufzeit
Analyse von Algorithmen
Klassifikation von Algorithmen
Berechnungskomplexitaet
Analyse des Durchschnittlichen Falls
Naeherungsweise und asymptotische Ergbnisse
...
der ausdruck koennte eine folge, von aus kleiner werdenden termen
bestehen
ohne, den gerade, es geht ja auch
c3 N log N + c2 N/2 log N/3 + ...
oder so.
fuehrender term ...
immer kleiner werdenden termen, koennte
term
