 |
Seit nunmehr 25 Jahren
besticht der Bundeswettbewerb Informatik mit einem wohldurchdachten
Aufgabenblock. Die Probleme sollten nicht zu einfach, aber wiederum vom
talentierten Programmierern prinzipiell lösbar sein. In sich gibt es im
Schwierigkeitsgrad wiederum Abstufungen. Nicht alle Aufgaben sind
gleichwertig. |
 |
hier
bekommt man das zentrale Aufgabenblatt für die 1. Runden des Jahres 2007
|
|
|
Aufgabe 1 |
Prämienjagd (Eric Kreller, Richard Friedrich)
Supermärkte geben oft Prämien. Eine oft gesehene Möglichkeit ist
„drei kaufen – eins umsonst”, was aber auch als „weniger als vier kaufen
– mehr zahlen” interpretiert werden kann. Im vorliegenden Fall sind die
Regeln aber viel komplizierter:
Liebe Kundschaft,
wenn Sie an der Kasse zwei Gegenstände, die Sie kaufen wollen,
nebeneinander hinlegen und der Centbetrag der Summe beider Preise 11,
33, 55, 77 oder 99 betragen sollte, dann erhalten Sie eine Prämie in
Form eines kleinen Geschenks. Sie können Ihr Geschenk aus einem
reichhaltigen Angebot auswählen. Selbstverständlich können Sie bei einem
Einkauf mehrere Prämien einfordern. Jeder Gegenstand kann aber nur zur
Erlangung einer Prämie verwendet werden. Wir freuen uns, wenn Sie die
Herausforderung annehmen, Ihren Einkauf entsprechend auf dem Band
anzuordnen.
Will man tatsächlich die Anzahl der Prämien maximieren, wenn man mit
gefülltem Einkaufswagen an die Kasse kommt, dann lohnt es sich, ein
wenig nachzudenken: Hat man Gegenstände mit den Preisen c 4,13, c 6,64,
c 8,98 und c 9,91, ist es keine gute Idee, die ersten beiden zu paaren,
da dann nur eine Prämie winkt. Aufgabe:
Schreibe ein Programm, das hilft, dieses verflixte Problem zu lösen. Es
sollte die Preise einlesen und dann die entsprechenden Paarungen
ausgeben.
Für die Eingabe 1.99 4.13 6.64 8.98 9.91 1.99 wäre beispielsweise die
Ausgabe ( 4.13 8.98 ) ( 6.64 9.91 ) angemessen. Das genaue Format der
Ausgabe kannst du auch selbst wählen. Du solltest aber unbedingt darauf
achten, dass deine Lösung immer so viele Prämien wie möglich erwirkt.
Demonstriere dein Programm an aussagekräftigen, selbst gewählten Fällen
und teste es auch an den auf der Webseite des BWINF vorgegebenen
Beispieldaten.
http://www.bwinf.de/aufgaben/material/ |
|
|
|
Aufgabe 2 |
Perlenketten (Bennet Berger) Eine Schulklasse möchte eine
Spende von Geld machen, das sie mit dem Verkauf von Perlenketten
verdient. Eine Perlenkette ist eine geschlossene Folge von farbigen
Holzperlen. Es gibt nur Perlen von sechs verschiedenen Farben; aber
dafür reichen die längsten Ketten den Leuten vom Hals viermal hinunter
bis zum Bauchnabel. Der Verkauf läuft gut.
Eine etwas spleenige Stammkundin ist aber unglücklich.
Sie hat die beiden Ketten gekauft und erst hinterher festgestellt, dass
sie in Wirklichkeit „gleich” sind, d. h. dieselbe Folge von Farben
aufweisen, wenn man nur richtig anfängt und die richtige
Durchlaufrichtung wählt – sie wollte aber immer nur verschiedene Ketten
kaufen.
Nun gut, sie kann eine ihrer Ketten umtauschen.
Aber um zu verhindern, dass so etwas noch einmal passiert, soll jede
Kette von nun an mit einem Schaubild verkauft werden, das die Kette in
einer „Normalform” zeigt, und zwar so, dass zwei Ketten genau dann
dieselbe Normalform haben, wenn sie dieselbe Farbenfolge besitzen. Zum
Beispiel könnten die obigen Ketten beide durch die folgende Normalform
dargestellt werden:
Aufgabe:
Überlege dir und beschreibe, wie die Normalformen beschaffen sein
könnten, und schreibe ein Programm, das die Normalform einer beliebigen
Perlenkette berechnen kann. Zeige die Ausgabe deines Programms für
sinnvoll gewählte Beispielketten. |
|
|
|
Aufgabe 3 |
Winddiagramme (Erik Voigt)
Wetterstationen erfassen unter anderem Windrichtungen und
Windgeschwindigkeiten. Die Windrichtungen werden in Grad angegeben: 0°
steht für Wind aus Nord, 90° für Ostwind, 180° für Südwind, 270° für
Westwind. Die Windgeschwindigkeiten werden in Meter pro Sekunde
angegeben. Die Wetterdaten liegen in Tabellenform vor.
Zur Darstellung der Winddaten sollen Windrichtungsdiagramme erstellt
werden, die einerseits die Häufigkeiten bestimmter Windrichtungen
verdeutlichen und andererseits die bei den jeweiligen Windrichtungen
aufgetretenen Windgeschwindigkeiten veranschaulichen.
Aufgabe:
Formuliere zwei Fragestellungen, die mit Hilfe der Winddaten aus der
Tabelle beantwortet werden können, die auf den Webseiten des BWINF
vorliegt. Finde jeweils grafische Darstellungen, welche die Beantwortung
der Fragen gut unterstützen. In mindestens einer der Grafiken sollen die
Windrichtungen als von einem gemeinsamen Punkt ausgehende Strahlen
dargestellt werden, wie in einer Wind- oder Kompassrose.
- Stunde
- Windrichtung
- Windgeschwindigkeit
- Außentemperatur
- Luftfeuchtigkeit
- Luftdruck
- ...
- Datum
|
|
|
|
Aufgabe 4 |
Pass-Algorithmen (Marcel
Pfeifer, André Neubert)
Zugriffe zu technischen Geräten werden oft erst nach einer
Authentifizierung gewährt. Beispiele sind der Passwortschutz eines
Schulcomputers oder die PIN-Eingabe in Verbindung mit einer Magnetkarte
am Geldautomaten.
Ein Sicherheitsnachteil dieser Zugriffsschutzverfahren ist ihre
Wiederholbarkeit: Wird das Eingeben des Passworts oder der PIN
beobachtet (und die Magnetkarte entwendet), kann auch eine unbefugte
Person Zugang erhalten.
Entwirf ein System, das diesen Nachteil vermeidet.
Anstatt eines statischen Passworts aus einer großen Menge möglicher
Passwörter soll ein Pass-Algorithmus aus einer großen Menge möglicher
Pass-Algorithmen als Nachweis der Identität vergeben werden. Dieser
Pass-Algorithmus kann eine Eingabe eindeutig in eine Ausgabe überführen,
berechnet also eine Funktion f: X Y. Eine Authentifizierung läuft nun so
ab: Das System bietet ein zufälliges x X an, und der Benutzer oder die
Benutzerin muss selbst f(x) berechnen und dem System mitteilen. Ist das
Ergebnis korrekt, dann geht das System davon aus, dass er oder sie im
Besitz des korrekten Algorithmus f ist, und gewährt den Zugang.
Beobachtet jemand den Vorgang, werden im schlimmsten Fall x und f(x)
bekannt, aber nicht f. Eine gute Klasse von Pass-Algorithmen sollte
mindestens folgende Eigenschaften haben:
- die Anzahl möglicher Pass-Algorithmen ist groß
- ein Pass-Algorithmus kann mit wenig Mühe im Kopf in kurzer Zeit
ausgeführt werden
- die Beobachtung weniger Paare (x,f(x)) erlaubt kaum Rückschlüsse
auf den benutzten Pass-Algorithmus f
- welche dieser Punkte am wichtigsten sind, hängt sehr vom Kontext
ab
Hier ein (sicher nicht perfektes) Beispielsystem: Die Eingabe ist ein
5 x 5 Feld von zweistelligen Zahlen.
Ein Pass-Algorithmus sieht so aus: „Addiere die Zahlen an den Positionen
(a,b) und (c,d) zu einer Zahl n”.
Hierbei gilt 1 <_ a,b,c,d <_ 5, und 1 <_ n <_ 99.
Konkret könnte ein Pass-Algorithmus also „Addiere die Zahlen an den
Positionen (3,4) und (1,5) zur Zahl 42” lauten.
Das konkrete System könnte
23 34 23 89 45
10 23 64 74 87
38 93 52 97 47
32 98 23 29 31
87 38 97 12 32
präsentieren, wobei mit 97 + 45 + 42 = 184 geantwortet werden muss.
Aufgabe:
- Überlege, warum die genannten Eigenschaften wünschenswert sind.
Welche weiteren Eigenschaften sollte ein solches System haben?
- Wie bewertest du das Beispielsystem?
- Entwirf selbst zwei solche Systeme für zwei unterschiedliche
Szenarien, implementiere eines davon und beurteile kritisch die
Vorteile und Nachteile beider. Erläutere auch, in welchen Situationen
deine Systeme gut eingesetzt werden können.
|
|
|
|
Aufgabe 5 |
Kosmischer Tanz (Johannes
Uhlig, Friedrich Salzer)
Ein Stern S mit Masse M kann als punktförmig und unbeweglich
angesehen werden. Ein kleinerer punktförmiger Himmelskörper K mit Masse
m in Abstand r von S wird von S mit einer Kraft der Größe G M m/ r 2
angezogen, wobei G eine Gravitationskonstante ist. Außerdem gilt das
zweite Newtonsche Gesetz
Beschleunigung = Kraft /Masse.
Aufgabe:
Erstelle ein Simulationssystem, das geeignet ist, experimentell zu
untersuchen, wie sich K unter dem Einfluss der Anziehung durch S bewegen
kann (andere Himmelskörper werden außer Acht gelassen).
Es soll dabei möglich sein, die Masse des Körpers K sowie seine
Anfangsposition und Anfangsgeschwindigkeit zu variieren. Finde eine gute
Art, wie man das Ergebnis einer Simulation auf einem Blatt Papier
darstellen kann, und zeige das Ergebnis von mindestens zwei möglichst
unterschiedlichen und interessant verlaufenden Simulationen.
|
|
