AuD WiSe2020/21

Algorithmen und Datenstrukturen

0.0 (0)

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>

Card list

Study

Was ist ein Algorithmus?

Keyboard commands:

= turn,

= for-/backward,

= scroll

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

Keyboard commands:

= turn,

= for-/backward,

= scroll

(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

Keyboard commands:

= turn,

= for-/backward,

= scroll

Gleicher Input liefert gleiches Ergebnis

Determinismus

Keyboard commands:

= turn,

= for-/backward,

= scroll

Alle Schritte sind genau festgelegt

Randomisierter Algorithmus

Keyboard commands:

= turn,

= for-/backward,

= scroll

Man darf „würfeln“

adjazent

Keyboard commands:

= turn,

= for-/backward,

= scroll

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

Keyboard commands:

= turn,

= for-/backward,

= scroll

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

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

Weg

Keyboard commands:

= turn,

= for-/backward,

= scroll

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

Pfad

Keyboard commands:

= turn,

= for-/backward,

= scroll

wiederholt sich in einer Kantenfolge kein Knoten spricht man von einem Pfad

geschlossener Weg

Keyboard commands:

= turn,

= for-/backward,

= scroll

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))

1 / 14

Card list

Study

AuD WiSe2020/21

Create or copy sets of flashcards

Create or copy sets of flashcards

Log in to see all the cards.

SWITCHaai

Office 365

Edulog

Apple ID

Google