AuD WiSe2020/21
Algorithmen und Datenstrukturen
Algorithmen und Datenstrukturen
Set of flashcards Details
| Flashcards | 14 |
|---|---|
| Language | Deutsch |
| Category | Technology |
| Level | University |
| Created / Updated | 27.02.2021 / 27.02.2021 |
| Weblink |
https://card2brain.ch/box/20210227_aud_wise202021
|
| Embed |
<iframe src="https://card2brain.ch/box/20210227_aud_wise202021/embed" width="780" height="150" scrolling="no" frameborder="0"></iframe>
|
Was ist ein Algorithmus?
Ein Algorithmus ist eine aus endlich vielen Schritten bestehende eindeutige Handlungsvorschrift zur Lösung eines Problems oder einer Klasse von Problemen.
Beispiele: Kochrezepte und Bedienungsanleitungen sowie Notenblätter oder ein Programmablaufplan
Eigenschaften von Algorithmen
- (1) Finitheit: Das Verfahren muss in einem endlichen Text eindeutig beschreibbar sein.
- (2) Ausführbarkeit: Jeder Schritt des Verfahrens muss tatsächlich ausführbar sein.
- (3) Dynamische Finitheit: Das Verfahren darf zu jedem Zeitpunkt nur endlich viel Speicherplatz benötigen (s. Platzkomplexität).
- (4) Terminierung: Das Verfahren darf nur endlich viele Schritte benötigen (s. auch Zeitkomplexität).
Determiniertheit
Gleicher Input liefert gleiches Ergebnis
Determinismus
Alle Schritte sind genau festgelegt
Randomisierter Algorithmus
Man darf „würfeln“
adjazent
Eine Kante e={v,w} in einem einfachen Graphen verbindet v und w, und v und w sind adjazent ("benachbart"), v ist Nachbar von w.
inzident
Eine Kante e={v,w} in einem einfachen Graphen.
v ist inzident ("zusammentreffend mit") zu e.
Weg
wiederholt sich keine Kante in einer Kantenfolge, dann spricht man von einem Weg
Pfad
wiederholt sich in einer Kantenfolge kein Knoten spricht man von einem Pfad
geschlossener Weg
wiederholt sich keine Kante in einer Kantenfolge, dann spricht man von einem Weg. Kehrt er am Ende zum Startknoten zurück (-> geschlossener Weg).
Kreis
Ist ein geschlossener Pfad. Keine Kante wiederholt sich in einer Kantenfolge und kehrt zum Startknoten zurück.
Eulerweg/Eulertour
Eulerweg: ist ein Weg, der alle Kanten eines Graphens enthält.
Eulertour: kehrt außerdem zum Startknoten zurück.
Hamiltonpfad/Hamiltonkreis
Hamiltonpfad: besucht alle Knoten eines Graphens
Hamiltonkreis (auch Hamiltontour) kehrt außerdem zum Startknoten zurück
Grad eines Knotens
ist die Anzahl der inzidenten Kanten (Schreibweise: δ(v))
