Informatik ohne Stecker

Modul 2 - Algorithmen

Dieses Modul beschäftigt sich mit dem Thema Algorithmen, welches eines der fundamentalen Grundlagen der Informatik darstellt. Bei der initialen Diskussion des Begriffs Informatik wurde bereits die Verarbeitung von Informationen als Kern von Computern und deren Funktionalität diskutiert. Dieser Punkt kann hier erneut aufgegriffen werden, da die Algorithmen die Handlungsanweisungen zur Verarbeitung in strukturierter Form kennen müssen.

  • "Computer sind keine intelligenten Wesen. Sie arbeiten stupide eine Folge von Befehlen ab, um Informationen zu empfangen, zu verarbeiten und dann wieder in neuer Form auszugeben. Wie nennt man solche Befehlsfolgen typischerweise ? Welche Beispiele gibt es im Alltag ?" (Programm, Applikation; Ampelsteuerung, Digitalkamera, Schreibprogramm im Computer, Regensensor im Auto)
  • "Eine Folge von Aktivitäten, die ein bestimmtes Problem lösen, nennt man Algorithmus. Viele Menschen haben ihre ganz eigenen Algorithmen, ein Beispiel ist das Einkaufen im Lieblingsladen in minimaler Zeit ein selbstentwickelter Algorithmus. Ein weiteres Beispiel ist das Packen einer Reisetasche oder das Befüllen des Geschirrspülers."
  • "Ein Computer führt zur Verarbeitung von Informationen eine Vielzahl von Algorithmen aus. In der Informatik interessieren wir uns sehr dafür, wie man Algorithmen schaffen kann, die entweder mehr Informationen in gleicher Zeit oder die gleichen Informationen schneller verarbeiten können."
  • "Welche Beispiele kennt ihr für beeindruckende Algorithmen in Computern ?" (Google-Suche, Pi auf einge Millionen Stellen ausrechnen, Pakete platzsparend in einem Container verstauen, Auto-Navigationssystem)

Suchalgorithmen

  • "Computer werden sehr oft benutzt, um Informationen in großen Datenmengen zu finden. Ein Beispiel ist das Kassensystem in einem Laden, welches aufgrund der Informationen aus dem Barcode sofort den Titel und Preis des Artikels ermittelt. Ein anderes Beispiel sind Suchmaschinen im Internet. Das zu suchende Element nennt man typischerweise Suchschlüssel."
  • "Google hat im Jahr 2008 bekanntgegeben, das sie eine Trillion Seiten (12 Nullen) indiziert haben. Eine Suchanfrage an Google wird in ca. 0.25 Sekunden für all diese Seiten beantwortet. Wie geht das ?" (Für ältere Schüler mit Englisch-Kenntnissen könnte diese Infotafel bei der Diskussion interessant sein -  googleinfograph.jpg)

Aktivität - Zahlensuche

Bei dieser Aktivität werden drei grundlegende Suchverfahren erläutert. Neben der spielerischen Einführung der Verfahren sollte im Laufe der Erklärung immer wieder erwähnt werden, das es sich hier um Algorithmen, also Handlungsanweisungen für den Computer, handelt.

Für die Aktivität werden kleine 'Bezahlungen' benötigt, wie z.B. Bonbons. Je nach Schülergruppe kann man auch auf andere Naturalien zurückgreifen, bis hin zu virtueller Bezahlung in Form von Spielmünzen.

  • 15 Kinder auswählen, die Zahlenkarten an die Schüler verdeckt verteilen und aufstellen lassen ( zahlenkarten.pdf).
  • Der Dozent wählt jetzt eine der Zahlen aus und notiert sie für alle sichtbar an der Tafel, verrät aber nicht den Standort.
  • Ein weitere Schüler bekommt die 'Bezahlungen' und kann jeweils einen Schüler nach seiner Karte befragen. Dafür muss er eine Bezahlung abgeben. Die Suche ist beendet, wenn die gewählte Zahl gefunden wurde. Die Aktivität kann mehrfach durchgeführt werden, wobei jedes mal die Karten neu verteilt werden sollten.
  • "Wie viele Versuche braucht man im Durchschnitt, um die fragliche Zahl zu finden ?" (ggf. Vergleich zum fairen Würfel ziehen, wenn die entsprechenden Grundlagen der Statistik schon in der Schule Thema waren)
  • "Dieses Prinzip nennt man lineare Suche. Es funktioniert auf jeder Art von Daten, wird aber mit zunehmender Datenmenge ziemlich unpraktisch." (Eventuell noch mal den Vergleich zu Google ziehen)
  • "Im nächsten Schritt ändern wir die zu durchsuchenden Daten etwas, indem wir sie vorher der Größe nach sortieren." (neue Kinder für die Tafeln wählen, sollen sich nicht sichtbar für die anderen entsprechend ihrer Zahl sortieren.)
  • "Wer hat eine Idee, wie man in sortierten Daten schneller suchen kann ?"
  • "Ein Suchverfahren für derart sortierte Daten ist die binäre Suche. Dabei wählt man aus einer sortierten Menge die mittlere Position aus und überprüft, ob das gefundene Element größer oder kleiner als das Suchelement ist. Je nach Ergebnis setzt man dann auf die gleiche Weise mit der Teilmenge links oder rechts von der Position fort." (Je nach Schülergruppe ist dies schon im vorherigen Schritt von Schülern ermittelt worden, dann muss man nur noch das Prinzip klar formulieren. Ansonsten führt man an dieser Stelle das Spiel mit dem gerade erlernten Prinzip noch mal durch).
  • "Das darunterliegende Konzept nennt man teile-und-Herrsche, auf lateinisch 'Divide et impera'. Es ist eine sehr alte Redensart, welche schon im römischen Reich in der Politik verwendet wurde. Warum kann man 'teile-und-herrsche' in der Informatik auch als Grundlage für einen Algorithmus verstehen ?" (Hinführung zum Prinzip des Suchalgorithmus - welche Elemente werden in welcher Reihenfolge geprüft)
  • "Teile-und-herrsche ist bei Informatikern extrem beliebt. Es findet sich nicht nur bei verschiedenen Suchverfahren, sondern beispielsweise auch bei der Speicherung großer Datenmengen, bei der Umsetzung von großen Internetpräsenzen oder bei der Beschleunigung von Berechnungen."

Aktivität - Schiffe versenken

Im nächsten Schritt wird der Unterschied zwischen linearer Suche und binärer Suche anhand eines Übungsblattes wiederholt. Zudem wird Hashing als drittes Suchverfahren eingeführt.

Die Schüler werden in Pärchen aufgeteilt. Ein Partner erhält  uebung_schiffe1a.pdf, der andere  uebung_schiffe1b.pdf als Übungsblatt. Beide dürfen sich ihre Blätter nicht zeigen.

  • "Wir wollen jetzt den Unterschied zwischen verschiedenen Suchverfahren anhand von 'Schiffe versenken' ausprobieren. Jedes Schiff wird durch eine Zahl identifiziert und befindet sich an einem bestimmten Ort, der durch einen Buchstaben gekennzeichnet ist. Das Ziel des Spiel ist es, den Ort eines bestimmten Schiffes zu finden, also eine Suche nach dem Schiff durchzuführen."
  • "Jeder kreist auf seinem Blatt verdeckt eines der Schiffe mit den Zahlen ein und nennt seinem Partner die Zahl. Die Zahl entspricht dabei dem Suchbegriff und der Buchstabe ist der zu ermittelnde Ort. Nun wird abwechselnd an den Orten nachgeschaut - also nach einem Buchstaben gefragt -, für den dann der Partner die Zahl nennen muss." (Die Schüler verstehen meist sehr schnell, das hier wieder lineare oder zufällige Suche zum Einsatz kommt.)
  • "Das Spielergebnis pro Teilnehmer ist die benötigte Anzahl an Versuchen." (Spielen lassen, es kann das gleiche Blatt mehrfach verwendet werden, wenn der Fragende die Antworten nicht mitgeschrieben hat. Als Alternative können auch  uebung_schiffe1a_2.pdf und  uebung_schiffe1b_2.pdf verwendet werden.)
  • "Wer hat die wenigsten Versuche ? Gibt es eine Strategie, welche die Erfolgswahrscheinlichkeiten verbessert ?" (Viele Schüler sind hier kreativ bei Ideen zum Schummeln. Es lohnt sich immer, den Vergleich zu gespeicherten Daten im Computer zu ziehen, um die guten Ideen zu identifizieren. Ein typisches Beispiel ist das Merken der Antworten, was zwar die spätere Suche beschleunigt, beim anfragenden Partner aber zusätzlichen 'Speicherplatz' benötigt. Die Informatik spricht hierbei von caching).
  • "Was ist die minimale und maximale Anzahl von notwendigen Versuchen ? Inwiefern hängt dies von der Anzahl an unterschiedlichen Schiffen ab ?" (gleiche Erklärung wie oben, man kann hier schon die Idee von algorithmischer Komplexität anklingen lassen)

Im nächsten Schritt werden  uebung_schiffe2a.pdf und  uebung_schiffe2b.pdf als Blätter eingesetzt, bei denen die Schiffnummern absteigend sortiert sind. Somit können die Schüler hier teile-und-herrsche direkt einsetzen, um schneller zur Lösung zu kommen. Für besonders schnelle Gruppen gibt es auch wieder die abgewandelten Varianten ( uebung_schiffe2a_2.pdf und  uebung_schiffe2b_2.pdf) der Übungsblätter.

  • "Wieviele Versuche habt ihr benötigt ? Was war eure Strategie, um möglichst wenig Versuche zu benötigen ? Was ist die maximale Anzahl von Versuchen beim Einsatz von binärer Suche für 2, 4 oder 8 Schiffe ?" (1, 2, 3 - den quadratischen Zusammenhang zwischen der Anzahl der Versuche und der Anzahl an Schiffen verdeutlichen. Eventuell ist schon der Logarithmus als mathematisches Konzept bekannt, dann kann die notwendige Anzahl der Versuche direkt berechnet werden.)
  • "Wie viele Versuche braucht man höchstens bei binärer Suche in 1.000.000 Schiffen ?" (log(2)1.000.000 = 20)
  • Zur weiteren Erheiterung kann man  logtafel.pdf zeigen und wieder das Google-Beispiel bemühen.
  • "Ein weiteres Beispiel für die Leistung von Algorithmen ist ein Kassensystem. Stellen wir uns vor, das aus 10.000 Artikeln ein Preis ermittelt werden soll. Jeder Eintrag in der Artikeldatenbank kann in 1/100s überprüft werden. Wie lange bräuchten lineare und binäre Suche im schlechtesten Fall ?" (10s vs. 7 Vergleiche)

Nun werden die Blätter  uebung_schiffe3a.pdf und  uebung_schiffe3b.pdf eingesetzt. Auch hier gibt es wieder entsprechende Varianten ( uebung_schiffe3a_2.pdf und  uebung_schiffe3b_2.pdf) für besonders schnelle Schüler.

  • "Auf diesen Übungsblättern setzen wir eine neue Suchstrategie ein, die sich 'Hashing' nennt. Das Wort leitet sich aus dem englischen Begriff 'to hash' (zusammenquetschen) ab."
  • "Die Schiffe sind hier in Gruppen aufgeteilt, welche durch die verschiedenen Spalten symbolisiert werden. Die letzte Stelle der Quersumme von jeder Schiffsnummer entspricht der Spalte bzw. Gruppe, zu der das Schiff gehört. Jetzt wiederholen wir das Spiel." (Damit das Spiel funktioniert, sind alle Schiffe weiterhin in den Reihenfolge ihrer Buchstaben angeordnet. Somit müssen die Schüler lediglich einen abgegrenzten Bereich des Suchraums abdecken, wenn sie den Hash-Schlüssel aus der genannten Zahl ermittelt haben. Dies entspricht ungefähr dem Prinzip der linearen Suche für einen Hash-Schlüssel entspricht.)
  • "Das 'hashing' besteht hier darin, das die Ziffern eines Schiffes auf eine einzige Ziffer zusammengequetscht werden. Dadurch hat man zwar noch mehrere Schiffe pro Spalte / Hashwert zu überprüfen, dies sind aber wesentlich weniger als beim gesamten Suchraum."
  • "Wie viel Versuche habt ihr gebraucht ? Was ist die maximal nötige Anzahl an Versuchen ?"
  • "Welche Schiffe kann man besonders schnell finden ? Für welche braucht man am längsten ? Wie könnte man die durchschnittliche Anzahl an Versuchen so klein wie möglich halten ?" (Ideal wäre eine Gleichverteilung aller Schiffe über die verfügbaren Spalten. Diese Diskussion ist sehr wichtig, weil sie die Grundidee einer 'guten' Hashfunktion klar verdeutlicht.)
  • "Wir haben jetzt drei Suchverfahren kennengelernt. Welches ist das bessere Verfahren ?" (Die Schüler kommen hier natürlicherweise auf Hashing. Man sollte dann in der Diskussion darauf hinführen, das Hashing und binäre Suche eine Vorverarbeitung der Daten benötigen, welche ebenfalls Zeit kostet. Eine schlechte Hashing-Funktion kann das Verfahren sogar langsamer als lineare Suche machen, wenn alle Elemente in den gleichen Hashwert einsortiert werden.)
  • "Wenn das gesuchte Schiff gar nicht vorhanden ist, wie lange bräuchte man, um das herauszufinden ?" (26, 5, kommt auf Verteilung an)
  • "Computer setzen typischerweise Hashing ein, wenn die Sortierung für die binäre Suche ansonsten nicht benötigt wird (z.B. zur Anzeige)."

Eine weitere nette Abwandlung von teile-und-herrsche findet sich in dieser CSUnplugged Aktivität, welche speziell in der Weihnachtszeit gut funktioniert.

Sortieralgorithmen

Im nächsten Abschnitt geht es um eine zweite elementare Klasse von Algorithmen in der Informatik, die Sortierverfahren. Im Gegensatz zum Suchen als offensichtliches Problem von IT-Systemen ist Sortieren ein wenig schwieriger zu motivieren.

  • "Wie wir schon bei der binären Suche gesehen haben, kann man in mit sortierten Dinge wesentlich effizienter arbeiten und einzelne Elemente identifizieren. Welche Beispiele dafür kennt ihr aus dem Alltag ?" (Telefonbuch, Wörterbuch, Index-Abschnitt in einem Buch, Terminkalender, Aktenablage, Bibliothek)
  • "Die Sortierung von Daten kann dabei helfen, Extreme und Duplikate besser zu identifizieren. Ausserdem vereinfach es erheblich das Durchsuchen großer Datenmengen. Computer sind daher überraschend häufig damit beschäftigt, Daten zu sortieren. Aus diesem Grund gibt es in der Informatik eine Vielzahl von Sortieralgorithmen."

Aktivität - Sortieren ohne Plan

Bei dieser Aktivität wählt man zwei Gruppen von jeweils ca. 8 Schülern aus und gibt ihnen  zahlenkarten.pdf bzw.  wortkarten.pdf und zufälliger Verteilung. Anschließend lässt man sie um die Wette die Karten sortieren und in der richtigen Reihenfolge dem Publikum zeigen (2 Karten pro Schüler). Die Aktivität kann mehrfach durchgeführt werden. Wichtig ist die Erkenntnis, das ein kooperativer Sortiervorgang ohne vorherige Festlegung eines Algorithmus sehr ineffizient ist. Eventuell können hier auch schon verschiedene Vorschläge für Sortierstrategien von den Schülern diskutiert werden.

Aktivität - Sortieren durch Wiegen

Für diese Aktivität werden zwei Waagen und eine Menge von Dosen mit unterschiedlich schwerem Inhalt benötigt. In meiner Veranstaltung setze ich zwei billige Küchenwaagen und 8 Playdoh-Dosen mit unterschiedlich viel Knete ein. Die Dosen müssen so präpariert sein, dass die Reihenfolge der Gewichte nachträglich ermittelt werden kann. Eine Möglichkeit sind Zahlen oder Punkte-Markierungen auf der Unterseite der Dose.

  • "Computer treffen typischerweise Entscheidungen durch Vergleich von zwei Datenwerten. Somit müssen Sortieralgorithmen typischerweise auf paarweisen Vergleich aufbauen. Wir wollen diese Funktionsweise mit den zwei Waagen simulieren, welche uns erlauben, die leichtere von zwei Dosen zu identifizieren. Die Aufgabe besteht darin, alle Dosen nach ihrem Gewicht zu sortieren." (Es kommt vor, das Schülern hier das Notieren aller Gewichte und die Sortierung der Zahlen als Verfahren vorschlagen. In diesem Fall muss man den Schülern klar machen, das hier 'doppelter Speicherplatz' verbraucht wird und das Sortierproblem noch immer nicht gelöst ist.)
  • "Wie kann man die leichteste Dose finden ?" (Ein Schüler führt durch, die anderen diskutieren mit. Die übliche Strategie ist das 'Festhalten' der leichtesten Dose, bis alle überprüft wurde.)
  • "Wie kann man drei der Dosen mit zwei Waagen sortieren ? Was ist die minimale Anzahl an Vergleichen ?" (Neuer Schüler führt durch)

An dieser Stelle erklärt man das Prinzip von Selection Sort. Wenn ein Beamer zur Verfügung steht, kann zur allgemeinen Erheiterung auch selection sort als Tanz vorgeführt werden.

  • "Sortiere nun alle Dosen mit Hilfe von 'selection sort'. Das Auditorium zählt dabei die Anzahl der Versuche."
  • "Was ist die größte Anzahl an Schritten, die man zum Sortieren nach diesem Verfahren braucht ?" (den schlimmsten Fall der Anordnung der Dosen - sortiert in umgekehrter Reihenfolge - diskutieren. Dabei lässt sich auch gut die Geschichte vom kleinen Gauß anbringen, um die Summenformel zur Ermittlung der maximal notwendigen Schritte zu erklären. Wichtig ist dabei eine ausführliche Klärung des Unterschiedes zwischen 'best-case', 'average-case' und 'worst-case', ohne aber näher auf die Details für bestimmte Verfahren einzugehen.)
  • "Dieses Verfahren gehört zur Gruppe der 'in-place' Sortieralgorithmen, da es keinen zusätzlichen Speicherplatz benötigt. Leider braucht es auch im durchschnittlichen, und selbst im besten, Fall genauso viele Vergleiche wie im schlechtesten Fall und ist damit ziemlich ineffizient."

Im nächsten Schritt wird nun Bubble Sort als verbessertes Prinzip erläutert. Auch hier gibt es wieder eine Tanzvariante als Video. Man lässt einen neuen Schüler das Verfahren anhand der Dosen durchführen.

  • "Warum kann Bubble Sort besser als Selection Sort sein ? Was ist die Anzahl an Vergleichen im besten und im schlechtesten Fall ?" (Wichtig ist hier die erneute Verdeutlichung des Abbruchkriteriums von Bubble Sort, welches den eigentlichen Vorteil ausmacht. Der schlechteste Fall ist genauso wie bei Selection Sort, die sortierten Elemente bauen sich lediglich von hinten auf.)

Nun wird Quick Sort als dritte Möglichkeit vorgestellt. Auch hier sollte wieder der vorführende Schüler für die Sortierung mit den Waagen ausgetauscht werden. Die Diskussion der worst-case Komplexität ist hier eher schwierig, da diese zu sehr vom Verfahren zur Auswahl des Pivot-Elementes abhängt.

  • "Das Quick Sort - Verfahren basiert auf der Auswahl eines sog. Pivot-Elements. In jeder Runde wird eine Dose als Pivot-Element ausgewählt. Alle Dosen, die leichter als die Pivot-Dose sind, kommen auf deren linke Seite. Alle schwereren Dosen kommen auf die rechte Seite der Pivot-Dose. Die Pivot-Dose wird danach nicht mehr angefasst. Was wissen wir jetzt über jede der Seiten ?"
  • "Wie könnte der nächste Schritt aussehen ?" (Teilgruppen wieder sortieren, auf Prinzip der Rekursion hinführen)
  • "Quick Sort ist in vielen Fällen der schnellste Algorithmus zum Sortieren von Dosen bzw. Daten. Quick Sort ist niemals langsamer als Selection Sort."
  • "Warum ist Quick Sort eine weitere Anwendung von teile-und-herrsche ?"

Je nach verbleibender Zeit kann jetzt das Sortieren der Zahlen- und Wortkarten wiederholt werden, wobei jede Gruppe sich ein beliebiges der Verfahren aussuchen kann.

Aktivität - Sortiernetze

  • "Computer sind eigentlich ziemlich schnell, z.B. beim Sortieren, aber manchmal reicht die Geschwindigkeit trotzdem nicht aus. Was könnten wir in solch einem Fall machen ?"
  • "Gregory F. Pfister hat mal gesagt: Es gibt drei Wege, um jede Art von Problem schneller zu lösen - arbeite härter, arbeite schlauer oder hole dir Hilfe. Wie lässt sich das auf Computer übertragen ?" (Die Idee ist hier, die parallele Verarbeitung von Problemen durch mehrere Prozessoren / Computer als weitere Möglichkeit neben dem Einsatz von besseren Algorithmen zu identifizieren.)
  • "Welche Alltagsbeispiele kennt ihr für Parallelisierung ?" (kochen, jede Art von Bauaktivität, mehrere Kassen im Supermarkt)
  • "Welche Jobs können nicht oder nur schwer parallelisiert werden ?" (Probleme mit jeder Art von Abhängigkeit / Synchronisation)
  • "Ist die Parallelisierung von Webseitensuche eher schwierig oder eher einfach ?" (Das Grundproblem ist überraschend einfach, da jede Webseitenkopie von Google gleichzeitig auf den Suchbegriff überprüft werden kann. In der realen Welt hat man allerdings keine trillionen Rechner zur Verfügung ...)
  • "Ein Beispiel für die Beschleunigung von Sortiervorgängen sind Sortiernetze."

An dieser Stelle kommt ein Sortiernetz zum Einsatz, wie es beispielsweise im Dokument  sortiernetz.pdf skizziert ist. In meinem Kurs kommt ein bemaltes Ikea-Laken zum Einsatz, es ist aber beispielsweise auch eine Variante mit Kreide im Freien möglich. Die CS Unplugged - Seite mit der Originalversion der Aktivität bietet hier viele Ideen für Umsetzungsmöglichkeiten (www.csunplugged.org/sorting-networks).

  • "Bildet eine Gruppe von 6 Leuten. Jeder Teilnehmer zieht zufällig eine der Zahlenkarten." (Hier kommen die  zahlenkarten.pdf vom Anfang wieder zum Einsatz.)
  • "Jeder stellt sich in einen Kasten. Auf den Kreisen treffen sich immer zwei Personen, die ihre Zahlen vergleichen. Die kleiner Zahl geht nach links, die größere Zahl geht nach rechts. Alle Vergleiche finden gleichzeitig statt."
  • Nach mehreren Versuchen mit verschiedenen Schülern und verschiedener Startreihenfolge kann man das Spiel auch mit den Wortkarten vom Anfang ( wortkarten.pdf) wiederholen. Hierbei erklärt man den lexikographischen Vergleich von Zeichenketten. Ein typisches Beispiel dafür sind die sortierbaren Spalten im Windows-Explorer oder Auswahllisten auf Webseiten.
  • "Was passiert, wenn man die Richtungen an den Entscheidungskreisen austauscht ?" (ausprobieren lassen)
  • "Funktioniert das Netz auch, wenn man es rückwärts ausführt ?" (nicht immer)
  • "Welches dieser Sortiernetze funktioniert schneller ?" ( sortiernetze_vergleich.pdf)
  • "Hier noch ein Beispiel für ein Sortiernetz, mit dem man parallelisiert das Minimum einer Zahlenfolge ermitteln kann." ( sortiernetz_minimum.pdf)

Die Aktivität macht den Schülern typischerweise viel Spaß, daher kann das Übungsblatt ( uebung_sortiernetze.pdf) mit nach Hause gegeben werden. Bei Bedarf gibt es auch die fertige Lösung ( uebung_sortiernetze_loesung.pdf) zum Herunterladen.

http://csunplugged.org/line-drawing

Materialiensammlung

 googleinfograph.jpg
 zahlenkarten.pdf
 uebung_schiffe1a.pdf
 uebung_schiffe1b.pdf
 uebung_schiffe1a_2.pdf
 uebung_schiffe1b_2.pdf
 uebung_schiffe2a.pdf
 uebung_schiffe2b.pdf
 uebung_schiffe2a_2.pdf
 uebung_schiffe2b_2.pdf
 logtafel.pdf
 uebung_schiffe3a.pdf
 uebung_schiffe3b.pdf
 uebung_schiffe3a_2.pdf
 uebung_schiffe3b_2.pdf
 wortkarten.pdf
 sortiernetz.pdf
 sortiernetze_vergleich.pdf
 sortiernetz_minimum.pdf
 uebung_sortiernetze.pdf
 uebung_sortiernetze_loesung.pdf