diff options
18 files changed, 359 insertions, 1 deletions
diff --git a/Info/11/NTG/1/Breitensuche/Implementierung/Repository Breitensuche.json b/Info/11/NTG/1/Breitensuche/Implementierung/Repository Breitensuche.json new file mode 100644 index 00000000..2e5d2005 --- /dev/null +++ b/Info/11/NTG/1/Breitensuche/Implementierung/Repository Breitensuche.json @@ -0,0 +1,6 @@ +{ + "name": "Breitensuche", + "files": "[{\"id\":2497876,\"version\":2,\"filename\":\"Graph\",\"path\":[],\"text\":\"class Graph {\\n // Attribut, das die aktuelle Anzahl an Knoten speichert\\n int anzKnoten;\\n // Knotenarray\\n Knoten[] knoten;\\n // Adjazenzmatrix\\n int[][] kanten;\\n \\n /**\\n * Erzeugt einen neuen Graphen.\\n * \\n * Der neue Graph hat Platz fuer maxAnzahlKnoten.\\n * Er enthaelt nach der Initialisierung weder Knoten noch\\n * Kanten.\\n * @param maxAnzahlKnoten die maximale Anzahl an Knoten\\n */\\n Graph(int maxAnzahlKnoten) {\\n // Initialisierung der Attribute\\n anzKnoten \\u003d 0; // Der Graph enthaelt noch keine Knoten\\n knoten \\u003d new Knoten[maxAnzahlKnoten];\\n kanten \\u003d new int[maxAnzahlKnoten][maxAnzahlKnoten];\\n\\n // Initialisierung der leeren Adjazenzmatrix\\n for (int i \\u003d 0; i \\u003c maxAnzahlKnoten; i++) {\\n for (int j \\u003d 0; j \\u003c maxAnzahlKnoten; j++) {\\n kanten[i][j] \\u003d -1;\\n }\\n }\\n \\n }\\n\\n /**\\n * Liefert die Bezeichnung eines Knoten\\n * \\n * @param knotenIndex der Index des Knoten\\n * @return die Bezeichnung des Knoten\\n */\\n String knotenBezeichnungFinden(int knotenIndex) {\\n Knoten knotenAnIndex \\u003d knoten[knotenIndex];\\n return knotenAnIndex.bezeichnung;\\n }\\n\\n /**\\n * Findet den Index eines Knoten anhand seiner Bezeichnung\\n * \\n * @param bezeichnung die Bezeichnung des Knoten\\n * @return den Index des Knoten, -1 falls Knoten nicht gefunden\\n */\\n int knotenFinden(String bezeichnung) {\\n for (int i \\u003d 0; i \\u003c anzKnoten; i++) {\\n if(knoten[i].bezeichnung \\u003d\\u003d bezeichnung) {\\n return i;\\n }\\n }\\n return -1;\\n }\\n\\n /**\\n * Fuegt einen neuen Knoten dem Graph hinzu\\n * \\n * @param bezeichnung die Bezeichnung des neuen Knoten\\n */\\n void knotenHinzufuegen(String bezeichnung) {\\n Knoten neuerKnoten \\u003d new Knoten(bezeichnung);\\n knoten[anzKnoten] \\u003d neuerKnoten;\\n anzKnoten \\u003d anzKnoten + 1;\\n }\\n \\n /**\\n * Fuegt eine gerichtete Kante dem Graphen hinzu\\n * \\n * @param start der Startknoten der Kante\\n * @param ziel der Zielknoten der Kante\\n * @param gewicht das Kantengewicht\\n */\\n void kanteHinzufuegen(String start, String ziel, int gewicht) {\\n int startIndex \\u003d knotenFinden(start);\\n int zielIndex \\u003d knotenFinden(ziel);\\n kanten[startIndex][zielIndex] \\u003d gewicht;\\n }\\n\\n /**\\n * Fuegt eine ungerichtete Kante dem Graphen hinzu\\n * \\n * @param k1 erster Nachbarknoten\\n * @param k2 zweiter Nachbarknoten\\n * @param gewicht das Kantengewicht\\n */\\n void ungerichteteKanteHinzufuegen(String k1, String k2, int gewicht) {\\n kanteHinzufuegen(k1, k2, gewicht);\\n kanteHinzufuegen(k2, k1, gewicht);\\n }\\n\\n /*******************************************************\\n * Eigenschaften eines Graphen *\\n *******************************************************/\\n\\n /**\\n * Zaehlt die ausgehenden Kanten eines Knotens\\n * \\n * @param bezeichnung die Bezeichnung des Knoten\\n * @return die Anzahl der ausgehenden Kanten\\n */\\n int ausgehendeKantenZaehlen(String bezeichnung) {\\n int knotenIndex \\u003d knotenFinden(bezeichnung);\\n int anzahl \\u003d 0;\\n for (int i \\u003d 0; i \\u003c anzKnoten; i++) {\\n if(kanten[knotenIndex][i] !\\u003d -1) {\\n anzahl \\u003d anzahl + 1;\\n }\\n }\\n return anzahl;\\n }\\n\\n /**\\n * Traversiert den Graphen mit der Breitensuche\\n * \\n * @param startKnotenBezeichnung die Bezeichnung des Startknotens\\n * @return ein Feld das fuer jeden Knoten speichert wann er besucht wurde.\\n */\\n int[] breitensuche(String startKnotenBezeichnung) {\\n int[] besuchsreihenfolge /* FIXME 1: initialisiere das Feld passend zur Anzahl der Knoten. */;\\n int anzahlBesuchterKnoten \\u003d 1;\\n\\n Warteschlange ausstehendeKnoten \\u003d new Warteschlange();\\n\\n int startKnotenIndex \\u003d knotenFinden(startKnotenBezeichnung);\\n\\n // TODO 1: Fuege den StartKnoten in die Warteschlange ein.\\n \\n // Markiere den Startknoten, indem er in besuchsreihenfolge als ersten besuchter Knoten vermerkt wird.\\n besuchsreihenfolge[startKnotenIndex] \\u003d anzahlBesuchterKnoten;\\n\\n while (false /* FIXME 2: Solange die Warteschlange NICHT leer ist */) {\\n // TODO 3: Implementiere den Schleifenrumpf passend zu deinem Pseudocode.\\n \\n // Tipp: Ist ein Knoten bereits besucht, liefert dir die Bedingung besuchsreihenfolge[i] \\u003d\\u003d 0.\\n }\\n\\n return besuchsreihenfolge;\\n }\\n}\\n\\nGraph g1 \\u003d new Graph(4);\\nfor (int i \\u003d 1; i \\u003c 5; i++) { g1.knotenHinzufuegen(\\\"v\\\" + i); }\\ng1.ungerichteteKanteHinzufuegen(\\\"v1\\\", \\\"v2\\\", 1);\\ng1.ungerichteteKanteHinzufuegen(\\\"v2\\\", \\\"v3\\\", 1);\\ng1.ungerichteteKanteHinzufuegen(\\\"v3\\\", \\\"v4\\\", 1);\\ng1.ungerichteteKanteHinzufuegen(\\\"v1\\\", \\\"v4\\\", 1);\\nint[] sollReihenfolge \\u003d { 1, 2, 4, 3 };\\n\\nprintln(\\\"Besuchsreihenfolge g1: \\\" + g1.breitensuche(\\\"v1\\\"));\\nif(!Arrays.equals(g1.breitensuche(\\\"v1\\\"), sollReihenfolge)) {\\n println(\\\"Deine Breitensuche funktioniert noch nicht richtig.\\\");\\n System.exit(1);\\n}\\n\\n\"},{\"id\":2497877,\"version\":1,\"filename\":\"Knoten\",\"path\":[],\"text\":\"class Knoten {\\n String bezeichnung;\\n\\n Knoten(String neueBezeichnung) {\\n bezeichnung \\u003d neueBezeichnung;\\n }\\n}\"},{\"id\":2497879,\"version\":1,\"filename\":\"Warteschlange\",\"path\":[],\"text\":\"class Warteschlange {\\n ArrayList\\u003cInteger\\u003e schlange;\\n\\n public Warteschlange() {\\n this.schlange \\u003d new ArrayList\\u003cInteger\\u003e();\\n }\\n\\n /**\\n * Fuegt eine Zahl der Warteschlange hinzu.\\n * \\n * @param i die zuhinzufuegende Zahl\\n */\\n void einfuegen(int i) {\\n schlange.add(i);\\n }\\n\\n /**\\n * Entfernt die erste Zahl der Warteschlange und gibt diese zurueck.\\n * \\n * @return die erste Zahl der Warteschlange\\n */\\n int erstenRausnehmen() {\\n int i \\u003d schlange.get(0);\\n schlange.remove(0);\\n return i;\\n }\\n\\n /**\\n * Gibt zureuck ob die Warteschlange leer ist.\\n * \\n * @return true falls die Warteschlange leer ist, false anderenfalls\\n */\\n boolean istLeer() {\\n return schlange.isEmpty();\\n }\\n}\"},{\"id\":2497892,\"version\":1,\"filename\":\"Arrays\",\"path\":[],\"text\":\"class Arrays {\\n public static boolean equals(int[] a1, int[] a2) {\\n if (a1.length !\\u003d a2.length) {\\n return false;\\n }\\n\\n for (int i \\u003d 0; i \\u003c a1.length; i++) {\\n if (a1[i] !\\u003d a2[i]) {\\n return false;\\n }\\n }\\n\\n return true;\\n }\\n}\"}]", + "history": "[{\"timestamp\":\"Tue Oct 21 16:37:42 CEST 2025\",\"version\":1,\"userId\":58291,\"username\":\"Florian.Fischer\",\"name\":\"Florian Fischer\",\"comment\":\"Initialer Commit\",\"isIntermediateEntry\":false,\"historyFiles\":[{\"id\":2497876,\"version\":1,\"type\":\"create\",\"filename\":\"Graph\",\"path\":[],\"content\":\"class Graph {\\n // Attribut, das die aktuelle Anzahl an Knoten speichert\\n int anzKnoten;\\n // Knotenarray\\n Knoten[] knoten;\\n // Adjazenzmatrix\\n int[][] kanten;\\n \\n /**\\n * Erzeugt einen neuen Graphen.\\n * \\n * Der neue Graph hat Platz fuer maxAnzahlKnoten.\\n * Er enthaelt nach der Initialisierung weder Knoten noch\\n * Kanten.\\n * @param maxAnzahlKnoten die maximale Anzahl an Knoten\\n */\\n Graph(int maxAnzahlKnoten) {\\n // Initialisierung der Attribute\\n anzKnoten \\u003d 0; // Der Graph enthaelt noch keine Knoten\\n knoten \\u003d new Knoten[maxAnzahlKnoten];\\n kanten \\u003d new int[maxAnzahlKnoten][maxAnzahlKnoten];\\n\\n // Initialisierung der leeren Adjazenzmatrix\\n for (int i \\u003d 0; i \\u003c maxAnzahlKnoten; i++) {\\n for (int j \\u003d 0; j \\u003c maxAnzahlKnoten; j++) {\\n kanten[i][j] \\u003d -1;\\n }\\n }\\n \\n }\\n\\n /**\\n * Liefert die Bezeichnung eines Knoten\\n * \\n * @param knotenIndex der Index des Knoten\\n * @return die Bezeichnung des Knoten\\n */\\n String knotenBezeichnungFinden(int knotenIndex) {\\n Knoten knotenAnIndex \\u003d knoten[knotenIndex];\\n return knotenAnIndex.bezeichnung;\\n }\\n\\n /**\\n * Findet den Index eines Knoten anhand seiner Bezeichnung\\n * \\n * @param bezeichnung die Bezeichnung des Knoten\\n * @return den Index des Knoten, -1 falls Knoten nicht gefunden\\n */\\n int knotenFinden(String bezeichnung) {\\n for (int i \\u003d 0; i \\u003c anzKnoten; i++) {\\n if(knoten[i].bezeichnung \\u003d\\u003d bezeichnung) {\\n return i;\\n }\\n }\\n return -1;\\n }\\n\\n /**\\n * Fuegt einen neuen Knoten dem Graph hinzu\\n * \\n * @param bezeichnung die Bezeichnung des neuen Knoten\\n */\\n void knotenHinzufuegen(String bezeichnung) {\\n Knoten neuerKnoten \\u003d new Knoten(bezeichnung);\\n knoten[anzKnoten] \\u003d neuerKnoten;\\n anzKnoten \\u003d anzKnoten + 1;\\n }\\n \\n /**\\n * Fuegt eine gerichtete Kante dem Graphen hinzu\\n * \\n * @param start der Startknoten der Kante\\n * @param ziel der Zielknoten der Kante\\n * @param gewicht das Kantengewicht\\n */\\n void kanteHinzufuegen(String start, String ziel, int gewicht) {\\n int startIndex \\u003d knotenFinden(start);\\n int zielIndex \\u003d knotenFinden(ziel);\\n kanten[startIndex][zielIndex] \\u003d gewicht;\\n }\\n\\n /**\\n * Fuegt eine ungerichtete Kante dem Graphen hinzu\\n * \\n * @param k1 erster Nachbarknoten\\n * @param k2 zweiter Nachbarknoten\\n * @param gewicht das Kantengewicht\\n */\\n void ungerichteteKanteHinzufuegen(String k1, String k2, int gewicht) {\\n kanteHinzufuegen(k1, k2, gewicht);\\n kanteHinzufuegen(k2, k1, gewicht);\\n }\\n\\n /*******************************************************\\n * Eigenschaften eines Graphen *\\n *******************************************************/\\n\\n /**\\n * Zaehlt die ausgehenden Kanten eines Knotens\\n * \\n * @param bezeichnung die Bezeichnung des Knoten\\n * @return die Anzahl der ausgehenden Kanten\\n */\\n int ausgehendeKantenZaehlen(String bezeichnung) {\\n int knotenIndex \\u003d knotenFinden(bezeichnung);\\n int anzahl \\u003d 0;\\n for (int i \\u003d 0; i \\u003c anzKnoten; i++) {\\n if(kanten[knotenIndex][i] !\\u003d -1) {\\n anzahl \\u003d anzahl + 1;\\n }\\n }\\n return anzahl;\\n }\\n\\n /**\\n * Traversiert den Graphen mit der Breitensuche\\n * \\n * @param startKnotenBezeichnung die Bezeichnung des Startknotens\\n * @return ein Feld das fuer jeden Knoten speichert wann er besucht wurde.\\n */\\n int[] breitensuche(String startKnotenBezeichnung) {\\n //int[] besuchsreihenfolge /* FIXME 1: initialisiere das Feld passend zur Anzahl der Knoten. */;\\n int[] besuchsreihenfolge \\u003d new int[anzKnoten];\\n int anzahlBesuchterKnoten \\u003d 1;\\n\\n Warteschlange ausstehendeKnoten \\u003d new Warteschlange();\\n\\n int startKnotenIndex \\u003d knotenFinden(startKnotenBezeichnung);\\n\\n // TODO 1: Fuege den StartKnoten in die Warteschlange ein.\\n ausstehendeKnoten.einfuegen(startKnotenIndex);\\n \\n // Markiere den Startknoten, indem er in besuchsreihenfolge als ersten besuchter Knoten vermerkt wird.\\n besuchsreihenfolge[startKnotenIndex] \\u003d anzahlBesuchterKnoten;\\n\\n while (!ausstehendeKnoten.istLeer() /* FIXME 2: Solange die Warteschlange NICHT leer ist */) {\\n // TODO 3: Implementiere den Schleifenrumpf passend zu deinem Pseudocode.\\n int knotenIndex \\u003d ausstehendeKnoten.erstenRausnehmen();\\n for (int i \\u003d 0; i \\u003c anzKnoten; i++) {\\n if(kanten[knotenIndex][i] !\\u003d -1 \\u0026\\u0026 besuchsreihenfolge[i] \\u003d\\u003d 0) {\\n anzahlBesuchterKnoten++;\\n besuchsreihenfolge[i] \\u003d anzahlBesuchterKnoten;\\n ausstehendeKnoten.einfuegen(i);\\n }\\n }\\n }\\n\\n return besuchsreihenfolge;\\n }\\n}\\n\\nGraph g1 \\u003d new Graph(4);\\nfor (int i \\u003d 1; i \\u003c 5; i++) { g1.knotenHinzufuegen(\\\"v\\\" + i); }\\ng1.ungerichteteKanteHinzufuegen(\\\"v1\\\", \\\"v2\\\", 1);\\ng1.ungerichteteKanteHinzufuegen(\\\"v2\\\", \\\"v3\\\", 1);\\ng1.ungerichteteKanteHinzufuegen(\\\"v3\\\", \\\"v4\\\", 1);\\ng1.ungerichteteKanteHinzufuegen(\\\"v1\\\", \\\"v4\\\", 1);\\nint[] sollReihenfolge \\u003d { 1, 2, 4, 3 };\\n\\nprintln(\\\"Besuchsreihenfolge g1: \\\" + g1.breitensuche(\\\"v1\\\"));\\nif (!Arrays.equals(g1.breitensuche(\\\"v1\\\"), sollReihenfolge)) {\\n println(\\\"Deine Breitensuche funktioniert noch nicht richtig.\\\");\\n System.exit(1);\\n}\\n\\n\",\"changeSet\":\"\"},{\"id\":2497877,\"version\":1,\"type\":\"create\",\"filename\":\"Knoten\",\"path\":[],\"content\":\"class Knoten {\\n String bezeichnung;\\n\\n Knoten(String neueBezeichnung) {\\n bezeichnung \\u003d neueBezeichnung;\\n }\\n}\",\"changeSet\":\"\"},{\"id\":2497879,\"version\":1,\"type\":\"create\",\"filename\":\"Warteschlange\",\"path\":[],\"content\":\"class Warteschlange {\\n ArrayList\\u003cInteger\\u003e schlange;\\n\\n public Warteschlange() {\\n this.schlange \\u003d new ArrayList\\u003cInteger\\u003e();\\n }\\n\\n /**\\n * Fuegt eine Zahl der Warteschlange hinzu.\\n * \\n * @param i die zuhinzufuegende Zahl\\n */\\n void einfuegen(int i) {\\n schlange.add(i);\\n }\\n\\n /**\\n * Entfernt die erste Zahl der Warteschlange und gibt diese zurueck.\\n * \\n * @return die erste Zahl der Warteschlange\\n */\\n int erstenRausnehmen() {\\n int i \\u003d schlange.get(0);\\n schlange.remove(0);\\n return i;\\n }\\n\\n /**\\n * Gibt zureuck ob die Warteschlange leer ist.\\n * \\n * @return true falls die Warteschlange leer ist, false anderenfalls\\n */\\n boolean istLeer() {\\n return schlange.isEmpty();\\n }\\n}\",\"changeSet\":\"\"},{\"id\":2497892,\"version\":1,\"type\":\"create\",\"filename\":\"Arrays\",\"path\":[],\"content\":\"class Arrays {\\n public static boolean equals(int[] a1, int[] a2) {\\n if (a1.length !\\u003d a2.length) {\\n return false;\\n }\\n\\n for (int i \\u003d 0; i \\u003c a1.length; i++) {\\n if (a1[i] !\\u003d a2[i]) {\\n return false;\\n }\\n }\\n\\n return true;\\n }\\n}\",\"changeSet\":\"\"}]},\n{\"timestamp\":\"21.10.2025, 16:40\",\"version\":2,\"userId\":58291,\"username\":\"Florian.Fischer\",\"name\":\"Florian Fischer\",\"comment\":\"Entferne Implementierung und ergaenze einen Hinweis\",\"isIntermediateEntry\":false,\"historyFiles\":[{\"id\":2497876,\"version\":2,\"type\":\"change\",\"content\":\"[{\\\"diffs\\\":[[0,\\\"{\\\\n \\\"],[-1,\\\"//\\\"],[0,\\\"int[] be\\\"]],\\\"start1\\\":3550,\\\"start2\\\":3550,\\\"length1\\\":18,\\\"length2\\\":16},{\\\"diffs\\\":[[0,\\\"*/;\\\\n\\\"],[-1,\\\" int[] besuchsreihenfolge \\u003d new int[anzKnoten];\\\\n\\\"],[0,\\\" \\\"]],\\\"start1\\\":3649,\\\"start2\\\":3649,\\\"length1\\\":61,\\\"length2\\\":8},{\\\"diffs\\\":[[0,\\\"in.\\\\n\\\"],[-1,\\\" ausstehendeKnoten.einfuegen(startKnotenIndex);\\\\n\\\"],[0,\\\" \\\"]],\\\"start1\\\":3882,\\\"start2\\\":3882,\\\"length1\\\":61,\\\"length2\\\":8},{\\\"diffs\\\":[[0,\\\"le (\\\"],[-1,\\\"!ausstehendeKnoten.istLeer()\\\"],[1,\\\"false\\\"],[0,\\\" /* \\\"]],\\\"start1\\\":4083,\\\"start2\\\":4083,\\\"length1\\\":36,\\\"length2\\\":13},{\\\"diffs\\\":[[0,\\\" \\\"],[-1,\\\"int knotenIndex \\u003d ausstehendeKnoten.erstenRausnehmen();\\\\n for (int i \\u003d 0; i \\u003c anzKnoten; i++) {\\\\n if(kanten[knotenIndex][i] !\\u003d -1 \\u0026\\u0026 besuchsreihenfolge[i] \\u003d\\u003d 0) {\\\\n anzahlBesuchterKnoten++;\\\\n besuchsreihenfolge[i] \\u003d anzahlBesuchterKnoten;\\\\n ausstehendeKnoten.einfuegen(i);\\\\n }\\\\n }\\\"],[1,\\\"\\\\n // Tipp: Ist ein Knoten bereits besucht, liefert dir die Bedingung besuchsreihenfolge[i] \\u003d\\u003d 0.\\\"],[0,\\\"\\\\n \\\"]],\\\"start1\\\":4240,\\\"start2\\\":4240,\\\"length1\\\":361,\\\"length2\\\":112},{\\\"diffs\\\":[[0,\\\"1\\\\\\\"));\\\\nif\\\"],[-1,\\\" \\\"],[0,\\\"(!Arrays\\\"]],\\\"start1\\\":4774,\\\"start2\\\":4774,\\\"length1\\\":17,\\\"length2\\\":16}]\"}]}", + "description": "Einfache Implementierung der Breitensuche." +}
\ No newline at end of file diff --git a/Info/11/NTG/1/Breitensuche/Implementierung/slides.md b/Info/11/NTG/1/Breitensuche/Implementierung/slides.md new file mode 100644 index 00000000..bc898ac2 --- /dev/null +++ b/Info/11/NTG/1/Breitensuche/Implementierung/slides.md @@ -0,0 +1,13 @@ +--- +author: Florian Fischer +theme: metropolis +aspectratio: 169 +--- + + +## \faIcon{desktop} Arbeitsauftrag: Implementierung der Breitensuche + +1. Initialisiere das Feld `besuchsreihenfolge`. +2. Korrigiere die Bedingung der `while`{.java}-Schleife +3. Implementiere den Rumpf der Schleife anhand des Pseudocodes der Breitensuche. +4. \faIcon{earlybirds} **Für Schnelle**: Teste deine Implementierung mit dem Graphen `g1` sowie eigenen Graphen. diff --git a/Info/11/NTG/1/Breitensuche/Uebung/.gitignore b/Info/11/NTG/1/Breitensuche/Uebung/.gitignore new file mode 100644 index 00000000..e9d76483 --- /dev/null +++ b/Info/11/NTG/1/Breitensuche/Uebung/.gitignore @@ -0,0 +1 @@ +AB_Breitensuche_2.pdf diff --git a/Info/11/NTG/1/Breitensuche/Uebung/AB_Breitensuche_2.docx b/Info/11/NTG/1/Breitensuche/Uebung/AB_Breitensuche_2.docx Binary files differnew file mode 100644 index 00000000..73f56d2e --- /dev/null +++ b/Info/11/NTG/1/Breitensuche/Uebung/AB_Breitensuche_2.docx diff --git a/Info/11/NTG/1/Breitensuche/Uebung/img/bfs-pseudocode-qrcode.png b/Info/11/NTG/1/Breitensuche/Uebung/img/bfs-pseudocode-qrcode.png Binary files differnew file mode 100644 index 00000000..9c9c2528 --- /dev/null +++ b/Info/11/NTG/1/Breitensuche/Uebung/img/bfs-pseudocode-qrcode.png diff --git a/Info/11/NTG/1/Breitensuche/Uebung/img/bfs-visualisierung-qrcode.png b/Info/11/NTG/1/Breitensuche/Uebung/img/bfs-visualisierung-qrcode.png Binary files differnew file mode 100644 index 00000000..6c4fdf51 --- /dev/null +++ b/Info/11/NTG/1/Breitensuche/Uebung/img/bfs-visualisierung-qrcode.png diff --git a/Info/11/NTG/1/Breitensuche/Uebung/img/huge_labyrinth.png b/Info/11/NTG/1/Breitensuche/Uebung/img/huge_labyrinth.png Binary files differnew file mode 100644 index 00000000..0574df1e --- /dev/null +++ b/Info/11/NTG/1/Breitensuche/Uebung/img/huge_labyrinth.png diff --git a/Info/11/NTG/1/Breitensuche/Uebung/img/idea-bfs-alpha.png b/Info/11/NTG/1/Breitensuche/Uebung/img/idea-bfs-alpha.png Binary files differnew file mode 100644 index 00000000..f407067f --- /dev/null +++ b/Info/11/NTG/1/Breitensuche/Uebung/img/idea-bfs-alpha.png diff --git a/Info/11/NTG/1/Breitensuche/Uebung/img/idea-bfs.png b/Info/11/NTG/1/Breitensuche/Uebung/img/idea-bfs.png Binary files differnew file mode 100644 index 00000000..8584ab46 --- /dev/null +++ b/Info/11/NTG/1/Breitensuche/Uebung/img/idea-bfs.png diff --git a/Info/11/NTG/1/Breitensuche/Uebung/img/idea-bfs.xcf b/Info/11/NTG/1/Breitensuche/Uebung/img/idea-bfs.xcf Binary files differnew file mode 100644 index 00000000..68e1402a --- /dev/null +++ b/Info/11/NTG/1/Breitensuche/Uebung/img/idea-bfs.xcf diff --git a/Info/11/NTG/1/Breitensuche/Uebung/img/laboscout.png b/Info/11/NTG/1/Breitensuche/Uebung/img/laboscout.png new file mode 120000 index 00000000..d5673ecf --- /dev/null +++ b/Info/11/NTG/1/Breitensuche/Uebung/img/laboscout.png @@ -0,0 +1 @@ +../../../Graphen_Implementierung/img/laboscout.png
\ No newline at end of file diff --git a/Info/11/NTG/1/Breitensuche/Uebung/img/labyrinth.png b/Info/11/NTG/1/Breitensuche/Uebung/img/labyrinth.png Binary files differnew file mode 100644 index 00000000..de69debe --- /dev/null +++ b/Info/11/NTG/1/Breitensuche/Uebung/img/labyrinth.png diff --git a/Info/11/NTG/1/Breitensuche/Uebung/img/manfred_cut_out.png b/Info/11/NTG/1/Breitensuche/Uebung/img/manfred_cut_out.png new file mode 120000 index 00000000..83d00f5d --- /dev/null +++ b/Info/11/NTG/1/Breitensuche/Uebung/img/manfred_cut_out.png @@ -0,0 +1 @@ +../../../ManfredsLabyrinth/manfred_cut_out.png
\ No newline at end of file diff --git a/Info/11/NTG/1/Breitensuche/Uebung/slides.md b/Info/11/NTG/1/Breitensuche/Uebung/slides.md new file mode 100644 index 00000000..3550736d --- /dev/null +++ b/Info/11/NTG/1/Breitensuche/Uebung/slides.md @@ -0,0 +1,297 @@ +--- +header-includes: | + \usepackage{ulem} + \makeatletter + \beamer@ignorenonframefalse + \makeatother + \usetikzlibrary{graphs} + \usetikzlibrary{overlay-beamer-styles} +--- + +## {.standout} +Herzlich Willkommen! + +Du kannst dich schon anmelden + +\texttt{vorname.nachname} + +und den Bildschirm ausschalten. + +## \faIcon{hands-helping} / \faIcon{chalkboard} Arbeitsauftrag: Ungerichtete Graphen \hfill{} 1/3 {.t} + +::: {.columns} +:::: {.column width=50%} +### Diskutiert die Aussage: + +\vspace{0.1cm} + +> Ungerichtete Graphen sind doch Quatsch in der Realität hat alles immer eine Richtung, oder eben zwei. +:::: + +:::: {.column width=50%} +{.center height=40%} +:::: +::: + +\pause + +Die Kanten eines **ungerichteter** Graphens haben nicht **keine** Richtung, sondern sind in **beide** Richtungen gleich. + +\pause +::: {.columns} +:::: {.column width=50%} +```{.graphviz dpi=150 height=2.8cm} +graph { + bgcolor=transparent + layout=circo + node [shape=circle] + nodesep=0.5 + v1 -- v2 + v2 -- v3 +} +``` +:::: + +:::: {.column width=50%} +```{.graphviz dpi=150 height=2.8cm} +digraph { + bgcolor=transparent + layout=circo + node [shape=circle] + nodesep=0.5 + v1 -> v2 [label=7] + v2 -> v1 [label=7] + v2 -> v3 [label=3] + v3 -> v2 [label=3] +} +``` +:::: +::: + +## \faIcon{hands-helping} / \faIcon{chalkboard} Arbeitsauftrag: Wieso Algorithmus? \hfill{} 2/3 + +### Diskutiert die Aussage: + +\vspace{0.2cm} + +> Ich muss mir keinen komplizierten Algorithmus merken, ich sehe doch gleich ob ein Graph zusammenhängend ist oder nicht. + +::: {.columns align=center} +:::: {.column width=50%} +\pause +{.center height=65%} +:::: + +:::: {.column width=50%} +\pause +Bei sehr großen Graphen scheitern wir Menschen. +Der Computer hingegen kann sehr große Probleme lösen aber braucht ein festes Vorgehen, einen **Algorithmus**. +:::: +::: + +## \faIcon{hands-helping} / \faIcon{chalkboard} Arbeitsauftrag: Algorithmus \hfill{} 3/3 + +### Diskutiert die Aussage: + +\vspace{0.3cm} + +> Toll, aber wenn ich irgendwas farblich markiere auf meinem Blatt kann, dass der Computer ja nicht einfach so machen. + +\pause + +Sicher, aber der Computer kann die Information abspeichern. + +## Manfred ist auf einer Labyrinthbesichtigung + +\begin{tikzpicture} +\node {\includegraphics[keepaspectratio, width=\textwidth]{img/laboscout.png}}; +\node at (-5, 0) {\includegraphics[keepaspectratio, height=\textheight]{img/manfred_cut_out.png}}; +\end{tikzpicture} + +## \faIcon{pencil-alt} Arbeitsauftrag: Manfred sucht den Ausgang + +\begin{tikzpicture} +\node at (0, 0) {\includegraphics[keepaspectratio, height=\textheight]{img/manfred_cut_out.png}}; +\node[scale=1.5] at (3, 2.5) {\bfseries\Large ?\Huge ?\Large ?}; +\node at (8, 0.5) {\includegraphics[keepaspectratio, width=6cm]{img/labyrinth.png}}; +\end{tikzpicture} + +## \faIcon{desktop} Arbeitsauftrag: Visualisierung der Breitensuche \hfill 5 min + +Öffne die Visualisierung der Breitensuche und lasse sie einmal durch klicken auf den Playknopf ablaufen. + +::: {.columns align=center} +:::: {.column width=60%} +`\centering`{=latex} +[**https://bycs.link/HMEG2U**](https://bycs.link/HMEG2U) +:::: + +:::: {.column width=40%} +{.center width=4cm} +:::: +::: + +### Achte dabei auf folgende Fragen: + +1. Wann wird ein Knoten in die Warteschlange aufgenommen? +2. Wann wird ein Knoten aus der Warteschlange entfernt? + +## \faIcon{desktop} Arbeitsauftrag: Ordne den Pseudocode \hfill 5min + +::: {.columns align=center} +:::: {.column width=60%} +Öffne die Webseite + +\vspace{0.5cm} +[**https://schule.muhq.space/bfs**](https://schule.muhq.space/bfs) + +\vspace{0.5cm} +und bringe die einzelnen Schritte der Breitensuche in die richtige Reihenfolge. +:::: + +:::: {.column width=40%} +{.center width=4cm} +:::: +::: + + +## \faIcon{pencil-alt} Arbeitsauftrag: Breitensuche made by IDEA + +\begin{tikzpicture} +\node {\includegraphics[keepaspectratio, height=0.9\textheight]{img/idea-bfs-alpha.png}}; +\node[text width=7cm] at (4, -1) {Kommentiere die einzelnen Schritte der graphische Darstellung der Breitensuche.}; +\end{tikzpicture} + + +## \faIcon{comment} Arbeitsauftrag: Breitensuche für den Computer{.t} + +Der Computer hat mit unserem menschlichen Vorgehen noch Probleme, denn er sieht nicht wie wir den ganzen Graphen auf einmal: +\vspace{0.3cm} + +\pause +> Wie kann sich der Computer merken welche Knoten markiert sind? + +\pause +### Lösungen \faIcon[regular]{lightbulb} + +> * Ein neues Attribut `markiert` der Klasse `Knoten` +> * oder ein neues Array um die Markierungen zu speichern + +::: {.columns align=center} +:::: {.column width=40%} +\only<3->{ +\begin{tikzpicture} + \begin{object}[text width=4cm]{Knoten}{0,0} + \attribute{String bezeichnung} + \attribute{boolean markiert} + \end{object} +\end{tikzpicture} +} +:::: + +:::: {.column width=50%} +\only<4->{ +\resizebox{\textwidth}{!}{ +\begin{tikzpicture} + \node at (-3.5, 5) {\textbf{Knotenarray}}; + \node at (.5, 5) {\textbf{Markierungen}}; + + \node[anchor=south west, minimum size=1cm, fill=gray!30] at (-3, 0) {}; + + \foreach \y in {0,...,3} { + \node[anchor=south west, minimum size=1cm, draw] at (-3, \y) {}; + } + + \foreach \y in {0,...,3} { + \node at (-1.75, 3.5 - \y) {\textbf \y}; + } + + \begin{object}[text width=4.7cm]{hbf: Knoten}{-6, 4.5} + \attribute{name = "Hauptbahnhof"} + \end{object} + \node[draw, circle, fill, inner sep=1pt] at (-2.5, 3.5) {}; + \draw[-Triangle, thick] (-2.5, 3.5) -- (-3.5, 4); + + \begin{object}[text width=4.7cm]{ww: Knoten}{-6, 3} + \attribute{name = "Wöhrder Wiese"} + \end{object} + \node[draw, circle, fill, inner sep=1pt] at (-2.5, 2.5) {}; + \draw[-Triangle, thick] (-2.5, 2.5) -- (-3.5, 2.5); + + \begin{object}[text width=4.7cm]{rp: Knoten}{-6, 1.5} + \attribute{name = "Rathenauplatz"} + \end{object} + \node[draw, circle, fill, inner sep=1pt] at (-2.5, 1.5) {}; + \draw[-Triangle, thick] (-2.5, 1.5) -- (-3.5, 1); + + \node[] at (-5.8, -0.25) {\textbf{anzKnoten = 3}}; + + \foreach \y in {0,...,3} { + \node at (-0.25, 3.5 - \y) {\textbf \y}; + } + + \node[anchor=south west, minimum size=1cm, fill=gray!30] at (0, 0) {}; + \foreach \y in {0,...,3} { + \node[anchor=south west, minimum size=1cm, draw] at (0, \y) {}; + } + + \draw[Triangle-Triangle, thick, dashed] (-1.6, 3.5) -- (-0.4, 3.5); + \node at (-1.75, 3.5) {\boldred{0}}; + \node at (-0.25, 3.5) {\textbf{\textcolor{magenta}{0}}}; +\end{tikzpicture} +} +} +:::: +::: + +## \faIcon{comment} Arbeitsauftrag: Breitensuche für den Computer{.t} + +> Wie kann der Computer sicherstellen, dass die Knoten in der richtigen Reihenfolge markiert werden? + +\pause + +Wir brauchen eine \boldred{Warteschlange} der zu bearbeitenden Knoten! + +### \faIcon[regular]{lightbulb} Arten von Warteschlangen +\vspace{0.1cm} + +::: {.columns align=center} +:::: {.column width=50%} +\pause +**Warteschlange** + +\pause +{.center width=80%} + +\pause +"Hinten rein, vorne raus" (FIFO) +:::: + +:::: {.column width=50%} +\pause +**Stapel** + +\pause +{.center height=25%} + +\pause +"Oben drauf, oben runter" (LIFO) +:::: +::: + +## \faIcon{pencil-alt}\faIcon{hands-helping} Arbeitsauftrag: Münchner S-Bahn Netz. + +::: {.columns align=center} +:::: {.column width=50%} +Ermittelt wie viele Stationen auf dem Weg mindestens erreicht werden. +Eine Person führt die Suche durch die andere kontrolliert und stoppt bei Fehlern. +\vspace{0.1cm} + +1. Sendlinger Tor $\rightarrow$ Innsbrucker Ring +2. Sendlinger Tor $\rightarrow$ Moosach +:::: + +:::: {.column width=50%} + +:::: +::: diff --git a/Info/11/NTG/1/Breitensuche/Uebung/slides.tex b/Info/11/NTG/1/Breitensuche/Uebung/slides.tex new file mode 100644 index 00000000..e69de29b --- /dev/null +++ b/Info/11/NTG/1/Breitensuche/Uebung/slides.tex diff --git a/Info/11/NTG/1/Breitensuche/arsnova_click_graphen_und_bfs.json b/Info/11/NTG/1/Breitensuche/arsnova_click_graphen_und_bfs.json index fed51faf..31c67dd1 100644 --- a/Info/11/NTG/1/Breitensuche/arsnova_click_graphen_und_bfs.json +++ b/Info/11/NTG/1/Breitensuche/arsnova_click_graphen_und_bfs.json @@ -1 +1 @@ -{"name":"Graphen und BFS","currentQuestionIndex":-1,"questionList":[{"questionText":"Graphen sind für mich ...","timer":30,"displayAnswerText":true,"tags":[],"requiredForToken":false,"difficulty":5,"answerOptionList":[{"answerText":"einfach","isCorrect":false,"TYPE":"DefaultAnswerOption"},{"answerText":"verständlich ","isCorrect":false,"TYPE":"DefaultAnswerOption"},{"answerText":"schwierig","isCorrect":false,"TYPE":"DefaultAnswerOption"},{"answerText":"schwarze Magie","isCorrect":false,"TYPE":"DefaultAnswerOption"}],"showOneAnswerPerRow":true,"TYPE":"SurveyQuestion"},{"questionText":"Welche Eigenschaft hat folgender Graph? \n\n","timer":30,"displayAnswerText":true,"tags":[],"requiredForToken":true,"difficulty":3,"answerOptionList":[{"answerText":"gerichtet","isCorrect":false,"TYPE":"DefaultAnswerOption"},{"answerText":"gewichtet","isCorrect":true,"TYPE":"DefaultAnswerOption"},{"answerText":"zusammenhängend","isCorrect":false,"TYPE":"DefaultAnswerOption"},{"answerText":"vollständig","isCorrect":false,"TYPE":"DefaultAnswerOption"}],"showOneAnswerPerRow":true,"TYPE":"SingleChoiceQuestion"},{"questionText":"Jeder zusammenhängende Graph ist auch vollständig.","timer":20,"displayAnswerText":true,"tags":[],"requiredForToken":true,"difficulty":3,"answerOptionList":[{"answerText":"Ja","isCorrect":false,"TYPE":"DefaultAnswerOption"},{"answerText":"Nein","isCorrect":true,"TYPE":"DefaultAnswerOption"}],"showOneAnswerPerRow":true,"TYPE":"YesNoSingleChoiceQuestion"},{"questionText":"Bei folgendem Signalfeuernetzwerk dauert es 1 Minute bis alle Nachbarsignalfeuer entzündet sind.\n\nWie viele Minuten dauert es bis, ausgehend vom schwarzen Signalfeuer, alle anderen Signalfeuer brennen?\n\n","timer":40,"displayAnswerText":true,"tags":[],"requiredForToken":true,"difficulty":5,"answerOptionList":[{"answerText":"5","isCorrect":false,"TYPE":"FreeTextAnswerOption","configCaseSensitive":false,"configTrimWhitespaces":false,"configUseKeywords":false,"configUsePunctuation":false}],"TYPE":"FreeTextQuestion"},{"questionText":"Welcher der Pseudocodebeschreibungen der Breitensuche ist korrekt?","timer":60,"displayAnswerText":true,"tags":[],"requiredForToken":true,"difficulty":6,"answerOptionList":[{"answerText":"","isCorrect":false,"TYPE":"DefaultAnswerOption"},{"answerText":"","isCorrect":false,"TYPE":"DefaultAnswerOption"},{"answerText":"","isCorrect":true,"TYPE":"DefaultAnswerOption"}],"showOneAnswerPerRow":true,"TYPE":"SingleChoiceQuestion"},{"questionText":"Die Warteschlange der Breitensuche und die des Dijkstra-Algorithmus verhalten sich gleich.","timer":20,"displayAnswerText":true,"tags":[],"requiredForToken":true,"difficulty":3,"answerOptionList":[{"answerText":"Wahr","isCorrect":false,"TYPE":"DefaultAnswerOption"},{"answerText":"Falsch","isCorrect":true,"TYPE":"DefaultAnswerOption"}],"showOneAnswerPerRow":true,"TYPE":"TrueFalseSingleChoiceQuestion"},{"questionText":"Vervollständige den Javacode, um die Bezeichnung aller Nachbarknoten eines Knotens auszugeben.\n\n```java\nint[][] adjazenzmatrix;\nKnoten knotenfeld[];\nint anzKnoten;\n\nint knotenIndex = 5;\nfor (int i = 0; i < anzKnoten; i++) {\n println(/*FIXME*/);\n}\n```","timer":75,"displayAnswerText":true,"tags":[],"requiredForToken":true,"difficulty":8,"answerOptionList":[{"answerText":"adjazenzmatrix[knotenIndex][i].bezeichnung","isCorrect":false,"TYPE":"FreeTextAnswerOption","configCaseSensitive":false,"configTrimWhitespaces":false,"configUseKeywords":true,"configUsePunctuation":true}],"TYPE":"FreeTextQuestion"}],"sessionConfig":{"theme":"Material","readingConfirmationEnabled":false,"showResponseProgress":true,"confidenceSliderEnabled":false,"music":{"enabled":{"lobby":true,"countdownRunning":true,"countdownEnd":true},"shared":{"lobby":false,"countdownRunning":false,"countdownEnd":false},"volumeConfig":{"global":60,"lobby":60,"countdownRunning":60,"countdownEnd":60,"useGlobalVolume":true},"titleConfig":{"lobby":"Song3","countdownRunning":"Song1","countdownEnd":"Song1"}},"nicks":{"memberGroups":[],"maxMembersPerGroup":10,"autoJoinToGroup":false,"selectedNicks":[],"blockIllegalNicks":true}},"state":"Inactive","currentStartTimestamp":-1}
\ No newline at end of file +{"name":"Graphen und BFS","currentQuestionIndex":-1,"questionList":[{"questionText":"Graphen sind für mich ...","timer":30,"displayAnswerText":true,"tags":[],"requiredForToken":false,"difficulty":5,"answerOptionList":[{"answerText":"einfach","isCorrect":false,"TYPE":"DefaultAnswerOption"},{"answerText":"verständlich ","isCorrect":false,"TYPE":"DefaultAnswerOption"},{"answerText":"schwierig","isCorrect":false,"TYPE":"DefaultAnswerOption"},{"answerText":"schwarze Magie","isCorrect":false,"TYPE":"DefaultAnswerOption"}],"showOneAnswerPerRow":true,"TYPE":"SurveyQuestion"},{"questionText":"Welche Eigenschaft hat folgender Graph? \n\n","timer":30,"displayAnswerText":true,"tags":[],"requiredForToken":true,"difficulty":3,"answerOptionList":[{"answerText":"gerichtet","isCorrect":false,"TYPE":"DefaultAnswerOption"},{"answerText":"gewichtet","isCorrect":true,"TYPE":"DefaultAnswerOption"},{"answerText":"zusammenhängend","isCorrect":false,"TYPE":"DefaultAnswerOption"},{"answerText":"vollständig","isCorrect":false,"TYPE":"DefaultAnswerOption"}],"showOneAnswerPerRow":true,"TYPE":"SingleChoiceQuestion"},{"questionText":"Jeder zusammenhängende Graph ist auch vollständig.","timer":20,"displayAnswerText":true,"tags":[],"requiredForToken":true,"difficulty":3,"answerOptionList":[{"answerText":"Ja","isCorrect":false,"TYPE":"DefaultAnswerOption"},{"answerText":"Nein","isCorrect":true,"TYPE":"DefaultAnswerOption"}],"showOneAnswerPerRow":true,"TYPE":"YesNoSingleChoiceQuestion"},{"questionText":"Bei folgendem Signalfeuernetzwerk dauert es 1 Minute bis alle Nachbarsignalfeuer entzündet sind.\n\nWie viele Minuten dauert es bis, ausgehend vom schwarzen Signalfeuer, alle anderen Signalfeuer brennen?\n\n","timer":40,"displayAnswerText":true,"tags":[],"requiredForToken":true,"difficulty":5,"answerOptionList":[{"answerText":"5","isCorrect":false,"TYPE":"FreeTextAnswerOption","configCaseSensitive":false,"configTrimWhitespaces":false,"configUseKeywords":false,"configUsePunctuation":false}],"TYPE":"FreeTextQuestion"},{"questionText":"Welcher der Pseudocodebeschreibungen der Breitensuche ist korrekt?","timer":60,"displayAnswerText":true,"tags":[],"requiredForToken":true,"difficulty":6,"answerOptionList":[{"answerText":"","isCorrect":false,"TYPE":"DefaultAnswerOption"},{"answerText":"","isCorrect":false,"TYPE":"DefaultAnswerOption"},{"answerText":"","isCorrect":true,"TYPE":"DefaultAnswerOption"}],"showOneAnswerPerRow":true,"TYPE":"SingleChoiceQuestion"},{"questionText":"Vervollständige den Javacode, um die Bezeichnung aller Nachbarknoten eines Knotens auszugeben.\n\n```java\nint[][] adjazenzmatrix;\nKnoten knotenfeld[];\nint anzKnoten;\n\nint knotenIndex = 5;\nfor (int i = 0; i < anzKnoten; i++) {\n println(/*FIXME*/);\n}\n```","timer":75,"displayAnswerText":true,"tags":[],"requiredForToken":true,"difficulty":8,"answerOptionList":[{"answerText":"adjazenzmatrix[knotenIndex][i].bezeichnung","isCorrect":false,"TYPE":"FreeTextAnswerOption","configCaseSensitive":false,"configTrimWhitespaces":false,"configUseKeywords":true,"configUsePunctuation":true}],"TYPE":"FreeTextQuestion"}],"sessionConfig":{"theme":"Material","readingConfirmationEnabled":false,"showResponseProgress":true,"confidenceSliderEnabled":false,"music":{"enabled":{"lobby":true,"countdownRunning":true,"countdownEnd":true},"shared":{"lobby":false,"countdownRunning":false,"countdownEnd":false},"volumeConfig":{"global":60,"lobby":60,"countdownRunning":60,"countdownEnd":60,"useGlobalVolume":true},"titleConfig":{"lobby":"Song3","countdownRunning":"Song1","countdownEnd":"Song1"}},"nicks":{"memberGroups":[],"maxMembersPerGroup":10,"autoJoinToGroup":false,"selectedNicks":[],"blockIllegalNicks":true}},"state":"Inactive","currentStartTimestamp":-1}
\ No newline at end of file diff --git a/Info/25_26/10/22/11a_NTG/schedule.md b/Info/25_26/10/22/11a_NTG/schedule.md new file mode 100644 index 00000000..79087c0a --- /dev/null +++ b/Info/25_26/10/22/11a_NTG/schedule.md @@ -0,0 +1,38 @@ +--- +lang: de +geometry: margin=2cm +--- +# BFS / Implementierung + +* **Klasse**: 11a_NTG +* **Datum**: 22.10 + +## Lernziele + +## Verlaufplan + +--------------------------------------------------------------------------------------------------- +Zeit Phase Unterrichtsgeschehen Ziel Methode Medien +----- --------------- -------------------------------------------- ----------- ---------- --------- +10 PuLS Vorstellung der Inhalte + +5 Wdh Ungerichtete Graphen sind Quatsch \newline + Wieso Algortihmus? \newline + Geht nicht Computer nicht anmalen? \newline + +5 Übung Labyrinth Breitensuche Ausweg + +5 Übung Breitensuche Visualisierung + +5 Übung Breitensuche Pseudocode sortieren + +5 Übung IDEA Breitensuche zu Pseudocode verbinden + +5 Übung Breitensuche für den PC + +5 Übung Warteschlangen + +10 Übung Breitensuche + +20 Übung Implementierung Breitensuche +--------------------------------------------------------------------------------------------------- diff --git a/Info/25_26/10/22/11a_NTG/topic b/Info/25_26/10/22/11a_NTG/topic new file mode 120000 index 00000000..1db61272 --- /dev/null +++ b/Info/25_26/10/22/11a_NTG/topic @@ -0,0 +1 @@ +../../../../11/NTG/1/Breitensuche
\ No newline at end of file |
