From 93b81eee486d3ddd4c60f335a5bbcc90a577a32c Mon Sep 17 00:00:00 2001 From: Florian Fischer Date: Fri, 27 Sep 2024 20:33:03 +0200 Subject: add my upcoming CS lesson --- Info/11/NTG/1/Adjazenzmatrix/.gitignore | 3 + .../NTG/1/Adjazenzmatrix/AB01 Adjazenzmatrix.pdf | 1 + .../1/Adjazenzmatrix/AdjazenzmatrixLoesung.json | 1 + .../1/Adjazenzmatrix/AdjazenzmatrixVorlage.json | 1 + Info/11/NTG/1/Adjazenzmatrix/graph.tex | 7 + Info/11/NTG/1/Adjazenzmatrix/graph.tikz | 15 + Info/11/NTG/1/Adjazenzmatrix/handout.tex | 29 ++ Info/11/NTG/1/Adjazenzmatrix/handout_print.tex | 6 + .../img/abi2021_burning_man_a4_graph.png | Bin 0 -> 72290 bytes Info/11/NTG/1/Adjazenzmatrix/slides.md | 505 +++++++++++++++++++++ Info/11/NTG/1/Adjazenzmatrix/weighted_graph.tex | 7 + Info/11/NTG/1/Adjazenzmatrix/weighted_graph.tikz | 15 + Info/24_25/09/30/11C/schedule.md | 31 ++ Info/24_25/09/30/11C/topic | 1 + 14 files changed, 622 insertions(+) create mode 100644 Info/11/NTG/1/Adjazenzmatrix/.gitignore create mode 120000 Info/11/NTG/1/Adjazenzmatrix/AB01 Adjazenzmatrix.pdf create mode 100644 Info/11/NTG/1/Adjazenzmatrix/AdjazenzmatrixLoesung.json create mode 100644 Info/11/NTG/1/Adjazenzmatrix/AdjazenzmatrixVorlage.json create mode 100644 Info/11/NTG/1/Adjazenzmatrix/graph.tex create mode 100644 Info/11/NTG/1/Adjazenzmatrix/graph.tikz create mode 100644 Info/11/NTG/1/Adjazenzmatrix/handout.tex create mode 100644 Info/11/NTG/1/Adjazenzmatrix/handout_print.tex create mode 100644 Info/11/NTG/1/Adjazenzmatrix/img/abi2021_burning_man_a4_graph.png create mode 100644 Info/11/NTG/1/Adjazenzmatrix/slides.md create mode 100644 Info/11/NTG/1/Adjazenzmatrix/weighted_graph.tex create mode 100644 Info/11/NTG/1/Adjazenzmatrix/weighted_graph.tikz create mode 100644 Info/24_25/09/30/11C/schedule.md create mode 120000 Info/24_25/09/30/11C/topic diff --git a/Info/11/NTG/1/Adjazenzmatrix/.gitignore b/Info/11/NTG/1/Adjazenzmatrix/.gitignore new file mode 100644 index 00000000..08c99225 --- /dev/null +++ b/Info/11/NTG/1/Adjazenzmatrix/.gitignore @@ -0,0 +1,3 @@ +plots/* +graph.pdf +weighted_graph.pdf diff --git a/Info/11/NTG/1/Adjazenzmatrix/AB01 Adjazenzmatrix.pdf b/Info/11/NTG/1/Adjazenzmatrix/AB01 Adjazenzmatrix.pdf new file mode 120000 index 00000000..f60c20a9 --- /dev/null +++ b/Info/11/NTG/1/Adjazenzmatrix/AB01 Adjazenzmatrix.pdf @@ -0,0 +1 @@ +../../Copyrighted/ECK/1 Graphen/AB01 Adjazenzmatrix.pdf \ No newline at end of file diff --git a/Info/11/NTG/1/Adjazenzmatrix/AdjazenzmatrixLoesung.json b/Info/11/NTG/1/Adjazenzmatrix/AdjazenzmatrixLoesung.json new file mode 100644 index 00000000..8acedff8 --- /dev/null +++ b/Info/11/NTG/1/Adjazenzmatrix/AdjazenzmatrixLoesung.json @@ -0,0 +1 @@ +{"name":"Adjazenzmatrix","modules":[{"name":"Adjazenzmatrix","text":"/**\n * Darstellung eines Graphens als Adjazenzmatrix.\n * Die Gewichte der Kanten werden in einem zweidimensionalen Feld von\n * Typ int gespeichert.\n * \n */\nclass Adjazenzmatrix\n{\n\n int[][] adjazenzmatrix;\n int anzKnoten;\n\n // Konstruktor\n Adjazenzmatrix(int maxAnzKnoten) { \n // Initialisierung des Feld-Attributs\n adjazenzmatrix = new int[maxAnzKnoten][maxAnzKnoten];\n\n anzKnoten = maxAnzKnoten;\n\n for (int i = 0; i < anzKnoten; i++) {\n for (int j = 0; j < anzKnoten; j++) {\n adjazenzmatrix[i][j] = -1;\n }\n }\n }\n\n /*\n * Die Kanten bzw. Adjazenzmatrix ausgeben.\n */\n void matrixAusgeben() {\n println(\"Die Adjazenzmatrix lautet:\");\n\n for (int i = 0; i < anzKnoten; i++) {\n for (int j = 0; j < anzKnoten; j++) {\n print(adjazenzmatrix[i][j] + \", \");\n }\n println(\"\");\n }\n }\n\n /****************************************************************************************************\n * Hinzufuegen von Kanten bzw. Knoten\n ****************************************************************************************************/\n \n /** \n * Eine Kante hinzufuegen.\n * \n * @param start der Startknoten der Kante\n * @param ziel der Zielknoten der Kante\n * @param gewicht das Gewicht der Kante\n */\n void kanteHinzufuegen(int start, int ziel, int gewicht) {\n adjazenzmatrix[start - 1][ziel - 1] = gewicht;\n }\n\n /*\n * Eine ungerichtete Kante hinzufuegen.\n * \n * @param knoten1 der erste der beiden Nachbarknoten\n * @param knoten2 der zweite der beiden Nachbarknoten\n * @param gewicht das Gewicht der ungerichteten Kante\n */\n void ungerichteteKanteHinzufuegen(int knoten1, int knoten2, int gewicht) {\n kanteHinzufuegen(knoten1, knoten2, gewicht);\n kanteHinzufuegen(knoten2, knoten1, gewicht);\n }\n\n /*\n * Die Laenge eines Pfades berechnen.\n * \n * @param pfad Pfad dessen Laenge berechnet werden soll\n * @return die Laenge des Pfades, -1 falls kein gueltiger Pfad uebergeben wurde\n */\n int pfadLaengeGeben(int[] pfad) {\n int laenge = 0;\n \n for (int i = 1; i < pfad.length; i++) {\n int start = pfad[i - 1] ;\n int ziel = pfad[i];\n int gewicht = adjazenzmatrix[start - 1][ziel - 1];\n if(gewicht != -1){\n laenge += gewicht;\n } else {\n return -1;\n }\n }\n\n return laenge; \n }\n}\n\nAdjazenzmatrix matrix = new Adjazenzmatrix(4);\nmatrix.ungerichteteKanteHinzufuegen(1, 2, 1);\nmatrix.ungerichteteKanteHinzufuegen(2, 3, 1);\nmatrix.ungerichteteKanteHinzufuegen(3, 4, 1);\nmatrix.ungerichteteKanteHinzufuegen(4, 1, 1);\nmatrix.matrixAusgeben();\n\nint[] kreis = { 1, 2, 3, 4, 1};\nprintln();\nprintln(\"Die berechnete Laenge des Rundlaufs ist \" + matrix.pfadLaengeGeben(kreis) + \" (Erwartet: 4)\");","identical_to_repository_version":true,"is_copy_of_id":1424357,"repository_file_version":3}],"settings":{"libraries":[]}} \ No newline at end of file diff --git a/Info/11/NTG/1/Adjazenzmatrix/AdjazenzmatrixVorlage.json b/Info/11/NTG/1/Adjazenzmatrix/AdjazenzmatrixVorlage.json new file mode 100644 index 00000000..96865543 --- /dev/null +++ b/Info/11/NTG/1/Adjazenzmatrix/AdjazenzmatrixVorlage.json @@ -0,0 +1 @@ +{"name":"Adjazenzmatrix","modules":[{"name":"Adjazenzmatrix","text":"/**\n * Darstellung eines Graphens als Adjazenzmatrix.\n * Die Gewichte der Kanten werden in einem zweidimensionalen Feld von\n * Typ int gespeichert.\n * \n */\nclass Adjazenzmatrix\n{\n\n int[][] adjazenzmatrix;\n int anzKnoten;\n\n // Konstruktor\n Adjazenzmatrix(int maxAnzKnoten) { \n // Initialisierung des Feld-Attributs\n // TODO 1: Initialisiere adjazenzmatrix mit beiden Dimensionen\n // entsprechen dem Parameter maxAnzKnoten.\n\n // TODO 1: Initialisiere das Attribut anzKnoten, das die maximale Anzahl\n // der Knoten und damit die Groesse der Adjazenzmatrix speichert.\n\n // Die Adjazenzmatrix wird mit dem Wert -1 (\"keine Kante\") vorbelegt.\n // TODO 2: Befuelle die Adjazenzmatrix mit den oben beschriebenen Werten.\n }\n\n /*\n * Die Kanten bzw. Adjazenzmatrix ausgeben.\n */\n void matrixAusgeben() {\n println(\"Die Adjazenzmatrix lautet:\");\n\n for (int i = 0; i < anzKnoten; i++) {\n for (int j = 0; j < anzKnoten; j++) {\n print(adjazenzmatrix[i][j] + \", \");\n }\n println(\"\");\n }\n }\n\n /****************************************************************************************************\n * Hinzufuegen von Kanten bzw. Knoten\n ****************************************************************************************************/\n \n /** \n * Eine Kante hinzufuegen.\n * \n * @param start der Startknoten der Kante\n * @param ziel der Zielknoten der Kante\n * @param gewicht das Gewicht der Kante\n */\n void kanteHinzufuegen(int start, int ziel, int gewicht) {\n // TODO 3: Fuege die Kante von start nach ziel mit ihrem Gewicht in\n // die Adjazenzmatrix ein.\n // ACHTUNG: Start und Ziel werden als Knotennummer nicht als Index angegeben.\n }\n\n /*\n * Eine ungerichtete Kante hinzufuegen.\n * \n * @param knoten1 der erste der beiden Nachbarknoten\n * @param knoten2 der zweite der beiden Nachbarknoten\n * @param gewicht das Gewicht der ungerichteten Kante\n */\n void ungerichteteKanteHinzufuegen(int knoten1, int knoten2, int gewicht) {\n // TODO 4: Fuege die ungerichtete Kante in die Adjazenmatrix ein.\n // Tipp: Du kannst die Methode kanteHinzufuegen verwenden.\n }\n\n /*\n * Die Laenge eines Pfades berechnen.\n * \n * @param pfad Pfad dessen Laenge berechnet werden soll\n * @return die Laenge des Pfades, -1 falls kein gueltiger Pfad uebergeben wurde\n */\n int pfadLaengeGeben(int[] pfad) {\n // TODO 5 - FUER SCHNELLE: Implementiere die Methode\n\n return 0 /* FIXME 5 */; \n }\n}\n\nAdjazenzmatrix matrix = new Adjazenzmatrix(4);\nmatrix.ungerichteteKanteHinzufuegen(1, 2, 1);\nmatrix.ungerichteteKanteHinzufuegen(2, 3, 1);\nmatrix.ungerichteteKanteHinzufuegen(3, 4, 1);\nmatrix.ungerichteteKanteHinzufuegen(4, 1, 1);\nmatrix.matrixAusgeben();\n\nint[] kreis = { 1, 2, 3, 4, 1 };\nprintln();\nprintln(\"Die berechnete Laenge des Rundlaufs ist \" + matrix.pfadLaengeGeben(kreis) + \" (Erwartet: 4)\");","identical_to_repository_version":true,"is_copy_of_id":1424357,"repository_file_version":2}],"settings":{"libraries":[]}} \ No newline at end of file diff --git a/Info/11/NTG/1/Adjazenzmatrix/graph.tex b/Info/11/NTG/1/Adjazenzmatrix/graph.tex new file mode 100644 index 00000000..ecfbc78f --- /dev/null +++ b/Info/11/NTG/1/Adjazenzmatrix/graph.tex @@ -0,0 +1,7 @@ +\documentclass{standalone} +\usepackage{tikz} +\usetikzlibrary{positioning} +\begin{document} +\tikzstyle{edge} = [] +\input{graph.tikz} +\end{document} diff --git a/Info/11/NTG/1/Adjazenzmatrix/graph.tikz b/Info/11/NTG/1/Adjazenzmatrix/graph.tikz new file mode 100644 index 00000000..0d06cf44 --- /dev/null +++ b/Info/11/NTG/1/Adjazenzmatrix/graph.tikz @@ -0,0 +1,15 @@ +\begin{tikzpicture}[node/.style={circle, thick, draw, inner sep=1pt}] +\node[node] (v1) {v1}; +\node[node, right= of v1] (v2) {v2}; +\node[node, below left=of v1] (v3) {v3}; +\node[node, below right=of v2] (v4) {v4}; +\node[node, below left=of v4] (v5) {v5}; + +\draw[edge] (v1) -- (v2); +\draw[edge] (v1) -- (v5); +\draw[edge] (v2) -- (v3); +\draw[edge] (v2) -- (v5); +\draw[edge] (v3) -- (v4); +\draw[edge] (v3) -- (v5); +\draw[edge] (v4) -- (v5); +\end{tikzpicture} diff --git a/Info/11/NTG/1/Adjazenzmatrix/handout.tex b/Info/11/NTG/1/Adjazenzmatrix/handout.tex new file mode 100644 index 00000000..ddefb656 --- /dev/null +++ b/Info/11/NTG/1/Adjazenzmatrix/handout.tex @@ -0,0 +1,29 @@ +\documentclass[a5paper]{handout} +\csname endofdump\endcsname + +\title{Abitur 2021 Teil A Aufgabe I.4} + +\begin{document} +\thispagestyle{empty} +\makedate + +Aufgrund der großen Distanzen zwischen den Orten des Festivals nutzen viele Besucher Fahrräder als Transportmittel. +Der nachfolgende Graph G enthält als Knoten die Orte mit den Camps $C_1$ bis $C_7$, mit dem Burning Man B sowie mit den besonders bedeutenden Kunstwerken $K_1$ bis $K_3$. +Die Kantengewichte geben die durchschnittliche Fahrtdauer in Minuten an. + +\begin{center} +\includegraphics[keepaspectratio, width=0.7\textwidth]{img/abi2021_burning_man_a4_graph.png} +\end{center} + +Im Folgenden werden Teilgraphen dieses Graphen betrachtet. +Ein Teilgraph von G ist ein Graph, dessen sämtliche Knoten und Kanten auch in G enthalten sind. + +\begin{enumerate}[a)] +\item Die Besucher wünschen sich, dass jeder der gegebenen elf Orte von jedem anderen Ort über einen direkten Radweg erreichbar ist. +Den dazugehörigen ungerichteten Graphen bezeichnet man als vollständig. +Zeichnen Sie einen Teilgraphen von G mit drei Knoten, der vollständig ist. \\[0.2cm] +Zeichnen Sie außerdem einen Teilgraphen von G mit fünf Knoten, der mit möglichst wenig weiteren Kanten zu einem vollständigen Graphen ergänzt werden kann. +Geben Sie an, wie viele Kanten dafür hinzugefügt werden müssen. \\[0.2cm] +Bestimmen Sie darüber hinaus, wie viele Radwege zusätzlich zu den 19 vorhandenen noch gebaut werden müssen, um den Wunsch der Besucher zu erfüllen. +\end{enumerate} +\end{document} diff --git a/Info/11/NTG/1/Adjazenzmatrix/handout_print.tex b/Info/11/NTG/1/Adjazenzmatrix/handout_print.tex new file mode 100644 index 00000000..09bbda66 --- /dev/null +++ b/Info/11/NTG/1/Adjazenzmatrix/handout_print.tex @@ -0,0 +1,6 @@ +\documentclass[landscape]{article} +\usepackage{pdfpages} +\begin{document} +\pagestyle{empty} +\includepdf[pages={1,1}, nup=2x1]{handout.pdf} +\end{document} diff --git a/Info/11/NTG/1/Adjazenzmatrix/img/abi2021_burning_man_a4_graph.png b/Info/11/NTG/1/Adjazenzmatrix/img/abi2021_burning_man_a4_graph.png new file mode 100644 index 00000000..a08425b3 Binary files /dev/null and b/Info/11/NTG/1/Adjazenzmatrix/img/abi2021_burning_man_a4_graph.png differ diff --git a/Info/11/NTG/1/Adjazenzmatrix/slides.md b/Info/11/NTG/1/Adjazenzmatrix/slides.md new file mode 100644 index 00000000..040e3311 --- /dev/null +++ b/Info/11/NTG/1/Adjazenzmatrix/slides.md @@ -0,0 +1,505 @@ +--- +header-includes: | + \makeatletter + \beamer@ignorenonframefalse + \makeatother + \usepackage[most]{tcolorbox} + \usetikzlibrary {decorations.markings} +--- + +## {.standout} +Herzlich Willkommen! + +Du kannst dich schon anmelden + +\texttt{vorname.nachname} + +und den Bildschirm ausschalten. + +## \faIcon{hands-helping} / \faIcon{chalkboard} Arbeitsauftrag: Fachbegriffe \hfill{} 1/5 + +### Diskutiert folgende Aussage: + +\vspace{0.3cm} +`\only<1>{`{=latex} + +> Folgender \boldred{Graf} ist \boldred{gerichtet}, da die \boldred{Punkte} mit gerichteten \boldred{Connections} verbunden sind. + +`}`{=latex} + +`\only<2>{`{=latex} + +> Folgender \boldred{Graph} ist \boldred{gerichtet}, da die \boldred{Knoten/vertices} mit gerichteten \boldred{Kanten/edges} verbunden sind. + +`}`{=latex} + +\hspace{1cm} +\begin{tikzpicture} +\node[draw, circle] (a) at (0, -1) {A}; +\node[draw, circle] (b) at (2, -1) {B}; +\node[draw, circle] (c) at (2, 1) {C}; +\node[draw, circle] (d) at (2, 2.5) {D}; +\draw[-Triangle] (a) -- (b); +\draw[-Triangle] (b) -- (c); +\draw[-Triangle] (c) -- (a); +\draw[-Triangle] (c) -- (d); + +\only<1> { + \node[opacity=0] at (13.5, 3.25) {foo}; +} +\only<2> { + \node[rotate=3] at (9, 1) {\includegraphics[keepaspectratio, width=4.5cm]{../Intro/img/vlad_tepes_002.jpg}}; + \draw[red, line width=2pt] (6cm, -2cm) -- (12cm, 3.5cm) (12cm, -2cm) -- (6cm, 3.5cm); +} +\end{tikzpicture} + +:::: +::: + +## \faIcon{hands-helping} / \faIcon{chalkboard} Arbeitsauftrag: Wege durch Graphen \hfill{} 2/5 + +### Diskutiert folgende Aussage: + +\vspace{0.2cm} +> Ein Graph heißt \boldred{zusammenhängend}, wenn jeder Knoten mit jedem anderen Knoten verbunden ist. +> Ein derartiger Graph hat immer $n^2$ Kanten, wenn n die Anzahl der Knoten ist. + +`\begin{center}`{=latex} +```{.graphviz dpi=150 height=5cm} +digraph { + bgcolor=transparent + node [shape=circle] + layout=circo + A -> B + A -> C + A -> D + A -> E + B -> C + B -> D + B -> E + C -> D + C -> E + D -> E +} +``` +`\end{center}`{=latex} + +## \faIcon{hands-helping} / \faIcon{chalkboard} Arbeitsauftrag: Wege durch Graphen \hfill{} 3/5 + +### Diskutiert folgende Aussage: + +\vspace{1cm} +> Der \boldred{Pfad} `A/B/D` ist kürzer als der Pfad `A/B/C/D`, weil er [weniger]{.underline} Knoten enthält. + +```{.graphviz dpi=150} +digraph { + bgcolor=transparent + rankdir=LR + node [shape=circle] + A -> B [label=2] + B -> C [label=1] + B -> D [label=3] + C -> D [label=1] +} +``` + +## \faIcon{hands-helping} / \faIcon{chalkboard} Arbeitsauftrag: Arrays initialisieren \hfill{} 4/5 + +### Diskutiert folgende Aussage: + +```java +int[] zahlen; +zahlen = new zahlen[10]; +verwende(zahlen); + +Knoten[] knoten = new Knoten[42]; +verwende(knoten); +``` +\vspace{1cm} +> Um die Werte eines Array verwenden zu können, reicht es aus das Array zu deklarieren und dieses anschließend zu initialisieren. + + +## \faIcon{hands-helping} / \faIcon{chalkboard} Arbeitsauftrag: Graphendarstellung \hfill{} 5/5 + +### Diskutiert folgende Aussage: + +\vspace{0.2cm} +> Alle vier Graphen sind identisch! + +![](img/Copyrighted/Cornelsen_S11_A6.png){.center} + +## + +![](../Intro/img/bike.png) + +## \faIcon{pencil-alt} Arbeitsauftrag: Abitur 2021 Burning Man - 10min + +[...] Aufgrund der großen Distanzen zwischen den Orten des Festivals nutzen viele Besucher Fahrräder als Transportmittel. + + +::: {.columns} +:::: {.column width=50%} +![](img/abi2021_burning_man_a4_graph.png){.center} + +*Die Besucher wollen ein [vollständiges]{.underline} Radwege-Netz.* +:::: + +:::: {.column width=50%} +1. Zeichne einen Teilgraphen von G mit drei Knoten, der vollständig ist. +2. Zeichne außerdem einen Teilgraphen von G mit fünf Knoten, der mit möglichst wenig weiteren Kanten zu einem vollständigen Graphen ergänzt werden kann. + Gib an, wie viele Kanten hinzugefügt werden müssten. +3. Bestimme darüber hinaus, wie viele Radwege zusätzlich zu den 19 vorhandenen noch gebaut werden müssen. + +:::: +::: + + +## + +\begin{center} +\begin{tikzpicture}[] + \node[draw, thick] at (0, 0) {% + \includegraphics[keepaspectratio=FALSE, height=8cm, width=4.5cm]{../Intro/img/Copyrighted/navi.png}}; + \node[draw, thick] at (4.75, 0) {% + \includegraphics[keepaspectratio=FALSE, height=8cm, width=4.5cm]{../Intro/img/Copyrighted/route.png}}; + \node[draw, thick] at (9.5, 0) {% + \includegraphics[keepaspectratio=FALSE, height=8cm, width=4.5cm]{../Intro/img/Copyrighted/graph.png}}; +\end{tikzpicture} +\end{center} + +## + +\vfill{} +![](img/Copyrighted/bike_matrix.png){.center} +\vfill{} + +## Darstellung von Graphen + +::: {.columns} +:::: {.column width=50%} +![](../Intro/img/Copyrighted/graph.png){height=90%} +:::: + +:::: {.column width=50%} +![](img/Copyrighted/bike_adj_matrix.png) +:::: +::: + +## Adjazenzmatrix + +::: {.columns align=center} +:::: {.column width=50%} +\resizebox{0.9\textwidth}{!}{ + \tikzstyle{edge} = [thick] + \input{graph.tikz} +} +:::: + +:::: {.column width=50%} +\begin{tabular}{c | c | c | c | c | c} +\rowcolor{gray!30} & v1 & v2 & v3 & v4 & v5 \\ +\hline +\cellcolor{gray!30} v1 & \only<3>{0} & \only<2->{\textbf 1} & \only<3>{0} & \only<3>{0} & \only<2->{\textbf 1} \\ +\hline +\cellcolor{gray!30} v2 & \only<2->{\textbf 1} & \only<3>{0} & \only<2->{\textbf 1} & \only<3>{0} & \only<2->{\textbf 1} \\ +\hline +\cellcolor{gray!30} v3 & \only<3>{0} & \only<2->{\textbf 1} & \only<3>{0} & \only<2->{\textbf 1} & \only<2->{\textbf 1} \\ +\hline +\cellcolor{gray!30} v4 & \only<3>{0} & \only<3>{0} & \only<2->{\textbf 1} & \only<3>{0} & \only<2->{\textbf 1} \\ +\hline +\cellcolor{gray!30} v5 & \only<2->{\textbf 1} & \only<2->{\textbf 1} & \only<2->{\textbf1} & \only<2->{\textbf 1} & \only<3>{0} \\ +\end{tabular} +:::: +::: + +## Adjazenzmatrix - gerichtet + +::: {.columns align=center} +:::: {.column width=50%} +\resizebox{0.9\textwidth}{!}{ + \tikzstyle{edge} = [thick, -Triangle] + \input{graph.tikz} +} +:::: + +:::: {.column width=50%} +\begin{tikzpicture} +\node { +\begin{tabular}{c | c | c | c | c | c} +\cellcolor{gray} & \only<-2>{\cellcolor{gray!30}} \only<3>{\cellcolor{teal!30}}v1 & \only<-2>{\cellcolor{gray!30}} \only<3>{\cellcolor{teal!30}}v2 & \only<-2>{\cellcolor{gray!30}} \only<3>{\cellcolor{teal!30}}v3 & \only<-2>{\cellcolor{gray!30}} \only<3>{\cellcolor{teal!30}}v4 & \only<-2>{\cellcolor{gray!30}} \only<3>{\cellcolor{teal!30}}v5 \\ +\hline +\only<-2>{\cellcolor{gray!30}}\only<3>{\cellcolor{yellow!30}} v1 & \only<2->{0} & \only<2->{\textbf 1} & \only<2->{0} & \only<2->{0} & \only<2->{\textbf 1} \\ +\hline +\only<-2>{\cellcolor{gray!30}}\only<3>{\cellcolor{yellow!30}} v2 & \only<2->{0} & \only<2->{0} & \only<2->{\textbf 1} & \only<2->{0} & \only<2->{\textbf 1} \\ +\hline +\only<-2>{\cellcolor{gray!30}}\only<3>{\cellcolor{yellow!30}} v3 & \only<2->{0} & \only<2->{0} & \only<2->{0} & \only<2->{\textbf 1} & \only<2->{\textbf 1} \\ +\hline +\only<-2>{\cellcolor{gray!30}}\only<3>{\cellcolor{yellow!30}} v4 & \only<2->{0} & \only<2->{0} & \only<2->{0} & \only<2->{0} & \only<2->{\textbf 1} \\ +\hline +\only<-2>{\cellcolor{gray!30}}\only<3>{\cellcolor{yellow!30}} v5 & \only<2->{0} & \only<2->{0} & \only<2->{0} & \only<2->{0} & \only<2->{0} \\ +\end{tabular} +}; +\only<-2> { + \node[opacity=0, fill=yellow!30, rotate=90] at (-3.2, 0) {Startknoten}; + \node[opacity=0, fill=teal!30] at (1, 2.1) {Zielknoten}; +} +\only<3> { + \node[fill=yellow!30, rotate=90] at (-3.2, 0) {Startknoten}; + \node[fill=teal!30] at (1, 2.1) {Zielknoten}; +} +\end{tikzpicture} +:::: +::: + +## Adjazenzmatrix - gewichtet + +::: {.columns align=center} +:::: {.column width=50%} +\resizebox{0.9\textwidth}{!}{ + \input{weighted_graph.tikz} +} +:::: + +:::: {.column width=50%} +\begin{tabular}{c | c | c | c | c | c} +\rowcolor{gray!30} & v1 & v2 & v3 & v4 & v5 \\ +\hline +\cellcolor{gray!30} v1 & \only<2->{\boldred{-1}} & \only<2->{\textbf{10}} & \only<2->{\boldred{-1}} & \only<2->{\boldred{-1}} & \only<2->{\textbf{30}} \\ +\hline +\cellcolor{gray!30} v2 & \only<2->{\textbf{10}} & \only<2->{\boldred{-1}} & \only<2->{\textbf{40}} & \only<2->{\boldred{-1}} & \only<2->{\textbf{50}} \\ +\hline +\cellcolor{gray!30} v3 & \only<2->{\boldred{-1}} & \only<2->{\textbf{40}} & \only<2->{\boldred{-1}} & \only<2->{\textbf{10}} & \only<2->{\textbf{30}} \\ +\hline +\cellcolor{gray!30} v4 & \only<2->{\boldred{-1}} & \only<2->{\boldred{-1}} & \only<2->{\textbf{10}} & \only<2->{\boldred{-1}} & \only<2->{\textbf{20}} \\ +\hline +\cellcolor{gray!30} v5 & \only<2->{\textbf{30}} & \only<2->{\textbf{50}} & \only<2->{\textbf{30}} & \only<2->{\textbf{20}} & \only<2->{\boldred{-1}} \\ +\end{tabular} + + +\vspace{0.5cm} +\only<-2>{ +\phantom{Der Eintrag \boldred{-1} symbolisiert \textit{"keine Kante"}, um das Kantengewicht 0 zu ermöglichen.} +} +\only<3>{ +Der Eintrag \boldred{-1} symbolisiert \textit{"keine Kante"}, um das Kantengewicht 0 zu ermöglichen. +} +:::: +::: + +## \faIcon{pencil-alt} Arbeitsauftrag - Arbeitsblatt 10min + +### Arbeitsauftrag 1: Graph $\rightarrow$ Adjazenzmatrix + +### Arbeitsauftrag 2: Adjazenzmatrix $\rightarrow$ Graph + +## {.standout} + +So jetzt für den Computer! + +\Huge \faIcon{java} + +## Implementierung einer Adjazenzmatrix + +::: {.columns} +:::: {.column width=50%} +`\begin{center}`{=latex} +```{.graphviz dpi=150 height=3.5cm} +graph { + bgcolor=transparent + layout=circo + node [shape=circle] + nodesep=0.5 + v1 -- v2 + v2 -- v3 + v3 -- v4 + v4 -- v1 +} +``` +`\end{center}`{=latex} + +\pause +\begin{center} +\begin{tabular}{c|c|c|c|c} +\rowcolor{gray!30}\cellcolor{gray} & v1 & v2 & v3 & v4 \\ +\hline +\cellcolor{gray!30} v1 & 0 & 1 & 0 & 1 \\ +\hline +\cellcolor{gray!30} v2 & 1 & 0 & 1 & 0 \\ +\hline +\cellcolor{gray!30} v3 & 0 & 1 & 0 & 1 \\ +\hline +\cellcolor{gray!30} v4 & 1 & 0 & 1 & 0 \\ +\end{tabular} +\end{center} +:::: + +:::: {.column width=50%} +\pause +Welche Datenstruktur ist geeignet? + +\begin{tikzpicture} + \foreach \y in {0,...,3} { + \node at (-0.25, 3.5 - \y) {\textbf \y}; + } + + \foreach \y in {0,...,3} { + \node[anchor=south west, minimum size=1cm, draw] at (0, \y) {}; + } + + \node[opacity=0] at (5, 4.5) {3}; + \node[opacity=0, anchor=south west, minimum size=1cm, draw] at (4.5, 3.5) {}; + \node[opacity=0, anchor=south west, minimum size=1cm, draw] at (4.5, -0.5) {}; +\end{tikzpicture} + +```java +int[] matrix = new int[4]; ? +``` +:::: +::: + + +## Implementierung einer Adjazenzmatrix + +::: {.columns} +:::: {.column width=50%} +`\begin{center}`{=latex} +```{.graphviz dpi=150 height=3.5cm} +graph { + bgcolor=transparent + layout=circo + node [shape=circle] + nodesep=0.5 + v1 -- v2 + v2 -- v3 + v3 -- v4 + v4 -- v1 +} +``` +`\end{center}`{=latex} + +\begin{center} +\begin{tabular}{c|c|c|c|c} +\rowcolor{gray!30}\cellcolor{gray} & v1 & v2 & v3 & v4 \\ +\hline +\cellcolor{gray!30} v1 & 0 & 1 & 0 & 1 \\ +\hline +\cellcolor{gray!30} v2 & 1 & 0 & 1 & 0 \\ +\hline +\cellcolor{gray!30} v3 & 0 & 1 & 0 & 1 \\ +\hline +\cellcolor{gray!30} v4 & 1 & 0 & 1 & 0 \\ +\end{tabular} +\end{center} +:::: + +:::: {.column width=50%} +Welche Datenstruktur ist geeignet? + +\begin{tikzpicture} + \foreach \y in {0,...,3} { + \node at (-0.25, 3.5 - \y) {\textbf \y}; + } + + \foreach \y in {0,...,3} { + \node[anchor=south west, minimum size=1cm, draw] at (0, \y) {}; + } + + \foreach \x in {0,...,3} + \node at (\x + 2, 4.5) {\textbf \x}; + + \foreach \y in {0,...,3} { + \foreach \x in {0,...,3} { + \node[anchor=south west, minimum size=1cm, draw] at (1.5 + \x , -0.5 + \y + \y*0.25) {}; + } + + \node[draw, circle, fill, inner sep=1pt] at (0.5, \y + 0.5) {}; + \draw[-Triangle, thick] (0.5, \y + 0.5) -- (1.5, \y + \y*0.25); + } +\end{tikzpicture} + +```java +int[][] matrix = new int[4][4]; +``` +:::: +::: + + +## Implementierung einer Adjazenzmatrix + +::: {.columns} +:::: {.column width=50%} +`\begin{center}`{=latex} +```{.graphviz dpi=150 height=3.5cm} +graph { + bgcolor=transparent + layout=circo + node [shape=circle] + nodesep=0.5 + v1 -- v2 + v2 -- v3 + v3 -- v4 + v4 -- v1 +} +``` +`\end{center}`{=latex} + +\begin{center} +\begin{tabular}{c|c|c|c|c} +\rowcolor{gray!30}\cellcolor{gray} & v1 & \cellcolor{teal!30} v2 & v3 & v4 \\ +\hline +\cellcolor{gray!30} v1 & 0 & 1 & 0 & 1 \\ +\hline +\cellcolor{gray!30} v2 & 1 & 0 & 1 & 0 \\ +\hline +\cellcolor{yellow!30} v3 & 0 & \boldred{1} & 0 & 1 \\ +\hline +\cellcolor{gray!30} v4 & 1 & 0 & 1 & 0 \\ +\end{tabular} +\end{center} +:::: + +:::: {.column width=50%} +Welche Datenstruktur ist geeignet? + +\begin{tikzpicture} + \foreach \y in {0,...,3} { + \node at (-0.25, 3.5 - \y) {\textbf \y}; + } + + \foreach \y in {0,...,3} { + \node[anchor=south west, minimum size=1cm, draw] at (0, \y) {}; + } + + \foreach \x in {0,...,3} + \node at (\x + 2, 4.5) {\textbf \x}; + + \foreach \y in {0,...,3} { + \foreach \x in {0,...,3} { + \node[anchor=south west, minimum size=1cm, draw] at (1.5 + \x , -0.5 + \y + \y*0.25) {}; + } + + \node[draw, circle, fill, inner sep=1pt] at (0.5, \y + 0.5) {}; + \draw[-Triangle, thick] (0.5, \y + 0.5) -- (1.5, \y + \y*0.25); + } + + \node[fill=teal!30] at (3, 4.5) {1}; + \node[fill=yellow!30] at (-0.25, 1.5) {2}; + \node at (3, 1.25) {\boldred{1}}; +\end{tikzpicture} + +```java +int[][] matrix = new int[4][4]; +matrix[2][1] = 1; +``` +:::: +::: + +## \faIcon{desktop} Arbeitsauftrag: Implementierung \hfill Rest der Stunde + +Öffne die Online-IDE ([https://online-ide.de](https://online-ide.de)) und das *Adjazenzmatrix*-Projekt. + +1. Ergänze die nötige Initialisierung der Attribute `adjazenzmatrix` und `anzKnoten`, im Konstruktor. +2. Befülle die Matrix, sodass sie keine Kanten enthält (`-1`). +3. Implementiere die Methode `kanteEinfuegen(int start, int ziel, int gewicht)`{.java}. +3. Implementiere die Methode `ungerichteteKanteEinfuegen(int knoten1, int knoten2, int gewicht)`{.java}. +5. \faIcon{earlybirds} **Für Schnelle**: Schreibe eine Methode `int pfadLaengeGeben(int[] pfad)`{.java}, die die Länge des Pfades zurückgibt. diff --git a/Info/11/NTG/1/Adjazenzmatrix/weighted_graph.tex b/Info/11/NTG/1/Adjazenzmatrix/weighted_graph.tex new file mode 100644 index 00000000..f7096dee --- /dev/null +++ b/Info/11/NTG/1/Adjazenzmatrix/weighted_graph.tex @@ -0,0 +1,7 @@ +\documentclass{standalone} +\usepackage{tikz} +\usetikzlibrary{positioning} +\begin{document} +\tikzstyle{edge} = [] +\input{weighted_graph.tikz} +\end{document} diff --git a/Info/11/NTG/1/Adjazenzmatrix/weighted_graph.tikz b/Info/11/NTG/1/Adjazenzmatrix/weighted_graph.tikz new file mode 100644 index 00000000..cde76692 --- /dev/null +++ b/Info/11/NTG/1/Adjazenzmatrix/weighted_graph.tikz @@ -0,0 +1,15 @@ +\begin{tikzpicture}[node/.style={circle, thick, draw, inner sep=1pt}] +\node[node] (v1) {v1}; +\node[node, right= of v1] (v2) {v2}; +\node[node, below left=of v1] (v3) {v3}; +\node[node, below right=of v2] (v4) {v4}; +\node[node, below left=of v4] (v5) {v5}; + +\draw[thick] (v1) edge node[above] {10} (v2); +\draw[thick] (v1) edge node [above left, xshift=-13, yshift=20]{30} (v5); +\draw[thick] (v2) edge node[right, xshift=23, yshift=7] {40} (v3); +\draw[thick] (v2) edge node[above right, yshift=10] {50} (v5); +\draw[thick] (v3) edge node[above left, xshift=-20, yshift=-2] {10} (v4); +\draw[thick] (v3) edge node[below] {30} (v5); +\draw[thick] (v4) edge node[below right] {20} (v5); +\end{tikzpicture} diff --git a/Info/24_25/09/30/11C/schedule.md b/Info/24_25/09/30/11C/schedule.md new file mode 100644 index 00000000..4bd13391 --- /dev/null +++ b/Info/24_25/09/30/11C/schedule.md @@ -0,0 +1,31 @@ +--- +lang: de +geometry: margin=2cm +--- +# Adjazenzmatrix + +* **Klasse**: 11C +* **Datum**: 30.09 + +## Lernziele + +## Verlaufplan + +--------------------------------------------------------------------------------------------------- +Zeit Phase Unterrichtsgeschehen Ziel Methode Medien +----- --------------- -------------------------------------------- ----------- ---------- --------- +15 Wdh SuS diskutieren Aussagen PA, UG BE + Gleichheit von Graphen + Cornelsen S11 A6 + +15 Übung Abi 2021 Burning Man PA BE + +10 Erarbeitung Darstellung als Adjazenzmatrix UG BE, AB + +15 Übung SuS leiten aus einem Graphen die PA AB + Adjazenzmatrix ab + +5 Erarbeitung Zweidimensionales Array UG BE + +35 Übung SuS implementieren eine Adjazenzmatrix PA O-IDE +--------------------------------------------------------------------------------------------------- diff --git a/Info/24_25/09/30/11C/topic b/Info/24_25/09/30/11C/topic new file mode 120000 index 00000000..043f1b9b --- /dev/null +++ b/Info/24_25/09/30/11C/topic @@ -0,0 +1 @@ +../../../../../Info/11/NTG/1/Adjazenzmatrix/ \ No newline at end of file -- cgit v1.2.3