Lernkarten

Karten 14 Karten
Lernende 0 Lernende
Sprache Deutsch
Stufe Universität
Erstellt / Aktualisiert 27.02.2021 / 27.02.2021
Lizenzierung Keine Angabe
Weblink
Einbinden
0 Exakte Antworten 14 Text Antworten 0 Multiple Choice Antworten
Fenster schliessen

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

Fenster schliessen

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).
Fenster schliessen

Determiniertheit

Gleicher Input liefert gleiches Ergebnis

Fenster schliessen

Determinismus

Alle Schritte sind genau festgelegt

Fenster schliessen

Randomisierter Algorithmus

Man darf „würfeln“

Fenster schliessen

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.

Fenster schliessen

inzident

Eine Kante e={v,w} in einem einfachen Graphen. 

v ist inzident ("zusammentreffend mit") zu e.

Fenster schliessen

Weg

wiederholt sich keine Kante in einer Kantenfolge, dann spricht man von einem Weg