AuD WiSe2020/21
Algorithmen und Datenstrukturen
Algorithmen und Datenstrukturen
Kartei Details
| Karten | 14 |
|---|---|
| Sprache | Deutsch |
| Kategorie | Technik |
| Stufe | Universität |
| Erstellt / Aktualisiert | 27.02.2021 / 27.02.2021 |
| Lizenzierung | Keine Angabe |
| Weblink |
https://card2brain.ch/box/20210227_aud_wise202021
|
| Einbinden |
<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
