Differences
This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision | ||
efinf:blc2016:graphen:graphen [2017/02/07 08:09] Ivo Blöchliger [Mathematische Notationen] |
efinf:blc2016:graphen:graphen [2017/04/04 15:30] (current) Ivo Blöchliger [Labyrinth-Generator] |
||
---|---|---|---|
Line 1: | Line 1: | ||
+ | ===== Labyrinth-Generator ===== | ||
+ | * Vorlage {{ : | ||
+ | * Anderer Generator {{ : | ||
+ | |||
+ | ===== Lernziele / Prüfungsstoff ===== | ||
+ | * Begriffe und Definitionen kennen und anwenden, wie | ||
+ | * Knoten, Kanten, gerichtet/ | ||
+ | * Zum Eulerzyklus: | ||
+ | * Notwendige und hinreichende Bedingungen für die Existenz eines Eulerzyklus kennen und begründen. | ||
+ | * Algorithmus zur Bestimmung eines Zyklus als Pseudocode formulieren. | ||
+ | * In einem konkreten Beispiel einen Eulerzyklus bestimmen. | ||
+ | * Zum Hamiltonzyklus: | ||
+ | * Rekursive Funktion zur Bestimmung eines Hamiltonzyklus formulieren und deren Komplexität (Grössenordnung der Anzahl Rechenschritte) abschätzen. | ||
+ | * Kürzeste Wege | ||
+ | * Algorithmus von Dijkstra auf einfachem Beispiel anwenden. | ||
+ | * Algorithmus von Dijkstra als Pseudocode formulieren und dessen Komplexität abschätzen. | ||
+ | * Begründen, warum der Algorithmus von Dijkstra für die Routenplanung im grossen Massstab nicht effizient genug ist.\ | ||
+ | * Graphensuche mit Todo-Liste | ||
+ | * Pseudo-Code wiedergeben und/oder anwenden. | ||
+ | * Unterschiedliche Arten der Handhabung der Todo-Liste verstehen/ | ||
+ | |||
===== Arbeitsblätter ===== | ===== Arbeitsblätter ===== | ||
* {{ : | * {{ : | ||
+ | * {{ : | ||
+ | |||
+ | ==== Hamiltonzyklus oder nicht? ==== | ||
+ | {{ : | ||
+ | |||
+ | {{ : | ||
+ | {{: | ||
+ | * {{ : | ||
+ | * {{ : | ||
===== Mathematische Notationen ===== | ===== Mathematische Notationen ===== | ||
* Knotenmenge (Vertexset) $V$. Anzahl Knoten $n=|V|$. $V$ ist oft ein Intervall natürlicher Zahlen, $\{0, | * Knotenmenge (Vertexset) $V$. Anzahl Knoten $n=|V|$. $V$ ist oft ein Intervall natürlicher Zahlen, $\{0, |