Differences

This shows you the differences between two versions of the page.

--- efinf:blc2016:graphen:graphen [2017/01/24 09:31]
Ivo Blöchliger [Begriffe]
+++ efinf:blc2016:graphen:graphen [2017/04/04 15:30] (current)
Ivo Blöchliger [Labyrinth-Generator]
@@ Line 1: / Line 1: @@
+===== Labyrinth-Generator =====
+  * Vorlage {{ :efinf:blc2016:graphen:labyrinth.rb |}} und {{ :efinf:blc2016:graphen:labyrinth-solution.rb |Lösungsvorschlag}}
+  * Anderer Generator {{ :efinf:blc2016:graphen:labgen.rb |Code Qualität: WTF}}. Wer mir die Funktionsweise des Codes überzeugend erklären kann, kriegt ein Arduino-Set ;-)
+===== Lernziele / Prüfungsstoff =====
+  * Begriffe und Definitionen kennen und anwenden, wie
+    * Knoten, Kanten, gerichtet/ungerichtet, Grad eines Knotens, Weg, Zyklus, kompletter Graph, Baum, $N^+(v)$, $N^-(v)$, zusammenhängender Graph, planarer Graph
+  * 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/anwenden.
+===== Arbeitsblätter =====
+  * {{ :efinf:blc2016:graphen:graphen.pdf |Graphentheorie}}
+  * {{ :efinf:blc2016:graphen:shortest.txt |Datei für Aufgabe 17, Kürzester Weg}}
+==== Hamiltonzyklus oder nicht? ====
+{{ :efinf:blc2016:graphen:knacknuss.txt |Knacknuss}}
+{{ :efinf:blc2016:graphen:knacknuss.pdf |PDF-Version (z.B. für Inkscape)}}
+{{:efinf:blc2016:graphen:plain.png?direct&200|}}
+  * {{ :efinf:blc2016:graphen:graph-5a.rb |Graphen-Bibliothek, Ruby-Version}}
+  * {{ :efinf:blc2016:graphen:graphlib.zip |Graphen-Bibliothek, Processing-Version (nicht direkt Eclipse-tauglich)}}
 ===== Mathematische Notationen =====
   * Knotenmenge (Vertexset) $V$. Anzahl Knoten $n=|V|$. $V$ ist oft ein Intervall natürlicher Zahlen, $\{0,1,2,\ldots,n-1\}$.
@@ Line 29: / Line 63: @@
 === Aufgaben ===
   - Finden Sie einen Weg, der die Kanten eines Würfels alle genau einmal beschreitet. Wie sieht es mit einem Tetraeder, Oktaeder, Dodekaeder und Ikosaeder aus? Wie sieht die Sache in einem 4-dimensionalen Würfel aus?
   - Die Koordinaten der Eckpunkte eines Einheitsquadrates sind (0,0), (0,1), (1,1) und  (1,0). Überlegen Sie sich, wie die Koordinaten eines Würfels sind und welche Eckpunkte miteinander verbunden werden. Verallgemeinern Sie auf 4 Dimensionen und schreiben Sie ein Programm, das die Knotenmenge und die Kantenmenge eines 4D-Würfels generiert.
+  - Finden Sie einen Weg, der die Kanten eines 4D-Würfels alle genau einmal beschreitet.