Differences

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

--- efinf:blc2016:graphen:graphen [2017/02/28 14:08]
Ivo Blöchliger [Hamiltonzyklus oder nicht?]
+++ 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? ====
@@ Line 9: / Line 31: @@
 {{:efinf:blc2016:graphen:plain.png?direct&200|}}
-  * {{ :efinf:blc2016:graphen:graph.rb |Graphen-Bibliothek, Ruby-Version}}
+  * {{ :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 =====