Informatik Q 11

aus ZUM-Wiki, dem Wiki für Lehr- und Lerninhalte auf ZUM.de
Wechseln zu: Navigation, Suche
Kurzinfo

Vista-kdmconfig.png
Bei dieser Seite handelt es sich um eine Projekt-, Kurs- oder Klassenseite.

Inhaltsverzeichnis

Hausaufgabe zum Labyrinth

Lies Dir die Aufgabenstellung im Buch S. 115/4 durch. Um einen Weg vom Start (St) zum Ziel (Zi) kann die Tiefensuche verwendet werden. Ergänze die Klasse Graph_Matrix um eine Methode wegSuche(String startKnoten, String Zielknoten), die die Tiefensuche abbricht, sobald der Zielknoten erreicht ist und den Weg ausgibt. Gehe dabei zunächst folgendermaßen vor:

  1. Notiere Dir einzelne Lösungsschritte (ohne das Problem direkt zu bearbeiten!)
  2. Erstelle die dazugehörige Adjazenzmatrix in Excel!
  3. Konvertiere die Matrix in ein Array!
  4. Ergänze die Klasse Graph Matrix um die Methode wegSuche(String,String)!

VERTIEFUNG ZUM THEMA GRAPHENTHEORIE

Gruppe1: Labyrinth: Nils, Antor, Simon, Marcel, Simon

Gruppe2: Damen: Otto, Julian, Simon

Gruppe3: Quinto: Niklas, Peter, Jonathan, Sebastian, André


  1. Lies im Buch die Seiten 126 bis 128 intensiv und notiere Dir Wesentliches zum Thema Backtracking!
  2. Gehe auf die Seite
  3. Gehe die einzelnen angegebenen Seiten durch und löse die interaktiven Aufgaben. Beantworte zu den einzelnen Themenseiten die untenstehenden Fragen schriftlich.


Fragen zum Labyrinth 1, 2, 3

  1. Was versteht man unter dem Begriff „random walks“? Welcher Bezug besteht zwischen diesem Begriff und dem Beispiellabyrinth?
  2. Lege Dir in Robot Karol ein Labyrinth aus Ziegelsteinen und formuliere den Algorithmus 'Im Labyrinth' wie auf der Seite zum Labyrinth 2 beschrieben, in Robot Karol! (Speichere die Robot Karol-Datei ab!)
  3. Was versteht man unter dem „Ariadne-Faden“ und was hat dies mit einem Labyrinth zu tun?
  4. Nach welchem Prinzip arbeitet der Held das Labyrinth durch? Nach welchen Präferenzen arbeitet der Held die Möglichkeiten ab?
  5. Notiere in Robot Karol den Algorithmus 'Zum Ausgang' mit Hilfe von „Marke setzen“

Aufgabe zu Prinzip 1 und 2

Notiere Dir die wesentlichen Informationen schriftlich und bearbeite die Interaktiven Aufgaben!

Aufgaben zu Damen 1 und 2

Notiere und bearbeite zu Damen 1 und 2 folgende Fragen, dazu musst Du die Seiten einschließlich der interaktiven Inhalte durchgearbeitet haben!

Aufgabe 1

Das n-Damen-Problem besitzt in der Regel mehrere Lösungen. Wir nennen zwei Lösungen wesentlich verschieden, wenn sie nicht durch Rotation oder Spiegelung auseinander hervorgehen.

a) Gib alle Lösungen des 4-Damen-Problems an. Gibt es wesentlich verschiedene Lösungen?

b) Gib zwei wesentlich verschiedene Lösungen des 5-Damen-Problems an.

c) Wie muss man den Backtracking-Algorithmus für das n-Damen-Problem modifizieren, damit er alle Lösungen bestimmt? Schreibe dazu den modifizierten Algorithmus (rekursiv oder nicht-rekursiv) im Detail auf.

Aufgabe 2

Mit welchem Wert für i muss man den rekursiven Algorithmus N-DamenRek(i) starten?

Lösungen

Damenproblem Lösungen

Aufgaben zu Quinto 1, 2

Aufgabe 1

Formuliere einen rekursiven und einen nicht-rekursiven Backtracking-Algorithmus für das Spiel Quinto.

Lösung

Für jedes Feld ist eine der beiden Entscheidungen "klicken“ (k) oder ”nicht klicken“ (n)möglich.


Der Algorithmus beginnt mit dem Feld oben links und arbeitet sich dann von links nach rechts und von oben nach unten durch das Quinto-Feld wobei für die zu treffenden Entscheidungen gilt:

Für die Felder ab Zeile 2 gibt es höchstens eine nicht erkennbar falsche Entscheidung:

  • Ist das darüberliegende Feld rot, so ist die Entscheidung 'klicken' falsch, denn das darüberliegende Feld wird dann blau und ändert seine Farbe nie mehr.
  • Ist das darüberliegende Feld blau, so ist die Entscheidung, nicht zu klicken, falsch.

Für die Felder der letzten Zeile gilt zusätzlich:

  • Beide möglichen Entscheidungen ('klicken' oder 'nicht klicken'), sind falsch, wenn das Feld zwei Positionen weiter links blau ist.
  • Für das letzte Feld (unten rechts) ist eine Entscheidung außerdem dann falsch, wenn durch sie nicht alle Felder rot werden.

Das folgende Gerüst eines Algorithmus formuliert einen Ansatz, bei der eine Folge solcher Entscheidungen schrittweise aufgebaut wird:

Algorithmus fortsetzen(f,i)

{f ist eine Folge von Entscheidungen für die Felder 0 bis i − 1,es wird eine Entscheidung für Feld i getroffen}
falls i+1=n*n
falls durch fortsetzen((f,'k'),i+1) nicht alle Felder rot werden
Beginne von vorne, wobei das letzte rote Feld der ersten Reihe dieses mal nicht gefärbt wird.
falls (i>n*n-n)
falls Feld i-2 blau ist
'n' und 'k' für Feld i falsch
Beginne von vorne, wobei das letzte rote Feld der ersten Reihe dieses mal nicht gefärbt wird.
falls das darüberliegende Feld rot ist,
fortsetzen ( (f,'n'),i+1 )

Aufgabe 2

Wir haben uns bei den hier behandelten Aufgaben nie überlegt, ob es überhaupt eine Lösung gibt.

a) Hat das n-Damen-Problem für n=3 eine Lösung? (Begründung!)

b) Hat Quinto für die Größe 3 eine Lösung?

c) Wie muss man die Backtracking-Algorithmen (nicht-rekursiv und rekursiv) abändern, dass sie die Information 'es gibt keine Lösung' ausgeben?


Lösung

a)Nein!
Bereits nach Platzierung einer Dame auf einem 3*3 Feld sind nur noch 2 Felder frei. Diese beiden Felder sind jedoch zwingend in einer Reihe!
b)Ja.
c) Es muss überprüft werden, ob der Algorithmus bereits beide möglichen Entscheidungen 'n' und 'k' für das erste Feld ausprobiert hat.

Für besonders Schnelle:

Falls Du noch Zeit hast, beschäftige Dich mit dem Vierfarbenproblem. Beschreibe (schriftlich) in eigenen Worten eine rekursive Variante eines Backtracking-Algorithmus, welcher für eine gegebene Karte eine gesuchte Einfärbung findet.

Graphendurchlauf - Tiefensuche

Pdf20.gif Tiefensuche

Übersicht über die Klausurthemen für die Klausur am 19.04.2010

II. Die rekursive Datenstruktur Baum (S. 49-92)

6. Eine Liste umstrukturieren

  • Definitionen: Baum, Höhe, Tiefe, Bestandteile
  • Klassendiagramm und Attribute der Klassen
  • Aufgaben: Liste umstrukturieren (A 2), Vergleichoperationen (A 3), Implentieren (A1) und Aufgaben S. 57/58

7. Geordneter Binärbaum

Interaktives Applet zum Binärbaum zum besseren Verständnis

Kompakte Erklärungen zum Binärbaum

BaumVisualisierungsTool (BVT), das wir im Unterricht verwendet haben

  • Definition
  • Implementierung des Binärbaums, insbesondere Angabe eines Klassendiagramms (vgl. S. 67)
  • Methoden: istVorhanden, suchen und einfügen (nicht die Methode löschen!)

8. Baum in perfekter Komposition (S. 75-82)

9. Bäume mit rekursiven Aufrufen durchlaufen

III. Die Datenstruktur Graph (S. 96-105)

10. Kennzeichen von Graphen

  • Definitionen
  • Klassendiagramm
  • Typische Aufgabenstellung für Graphen
  • Aufgabe als Graph darstellen
  • Aufgaben anschauen!

(Nicht primär: 11. Darstellung von Graphen)

NICHT: Adjazenzlisten!