AuD WiSe2020/21

Algorithmen und Datenstrukturen

0.0 (0)

Fichier Détails

Cartes-fiches	14
Langue	Deutsch
Catégorie	Technique
Niveau	Université
Crée / Actualisé	27.02.2021 / 27.02.2021
Lien de web	https://card2brain.ch/box/20210227_aud_wise202021
Intégrer	<iframe src="https://card2brain.ch/box/20210227_aud_wise202021/embed" width="780" height="150" scrolling="no" frameborder="0"></iframe>

Liste des carte

Étudier

Was ist ein Algorithmus?

Commandes clavier:

= tourner,

= avant/arrière,

= faire défiler

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

Commandes clavier:

= tourner,

= avant/arrière,

= faire défiler

(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

Commandes clavier:

= tourner,

= avant/arrière,

= faire défiler

Gleicher Input liefert gleiches Ergebnis

Determinismus

Commandes clavier:

= tourner,

= avant/arrière,

= faire défiler

Alle Schritte sind genau festgelegt

Randomisierter Algorithmus

Commandes clavier:

= tourner,

= avant/arrière,

= faire défiler

Man darf „würfeln“

adjazent

Commandes clavier:

= tourner,

= avant/arrière,

= faire défiler

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

Commandes clavier:

= tourner,

= avant/arrière,

= faire défiler

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

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

Weg

Commandes clavier:

= tourner,

= avant/arrière,

= faire défiler

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

Pfad

Commandes clavier:

= tourner,

= avant/arrière,

= faire défiler

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

geschlossener Weg

Commandes clavier:

= tourner,

= avant/arrière,

= faire défiler

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

Créer ou copier des fichiers d'apprentissage

Créer ou copier des fichiers d'apprentissage

Connecte-toi pour voir toutes les cartes.

SWITCHaai

Office 365

Edulog

Apple ID

Google