Lernziel · Gymnasiallehrplan
GYM INF 3 — Ergänzungsfach: Informatik.
Vorschau der Fragen
1Wenn ein Algorithmus immer das richtige Ergebnis liefert, ist er zwingend effizient (schnell).
RichtigFalsch
2Bei der binären Suche halbiert jeder Schritt die Zahl der verbleibenden Kandidaten. Wie viele Schritte braucht es höchstens, um einen Namen in einer sortierten Liste von 1024 Namen zu finden?
Zahl als Antwort eingeben.
3Was braucht es UNBEDINGT, um die binäre Suche auf eine Liste anwenden zu können?
Alle Elemente der Liste müssen Zahlen sein, niemals TextDie ganze Liste muss am Stück in den Arbeitsspeicher passenDie Liste muss bereits sortiert seinDie Liste darf höchstens knapp tausend Elemente enthalten
4Ein Algorithmus vergleicht jedes Element einer Liste mit allen anderen. Bei 10 Elementen sind das etwa 10 × 10 = 100 Vergleiche. Wie viele sind es etwa bei 100 Elementen?
Zahl als Antwort eingeben.
5Bleibt jede Komplexität bei grossen Daten MACHBAR, oder wird sie schnell UNMACHBAR?
Kategorien:
Bleibt machbarWird unmachbar
Zu ordnende Begriffe:
Alle Kombinationen ausprobieren (2ⁿ)Alle möglichen Reihenfolgen testen (n!)Alle Paare vergleichen (n²)Binäre Suche (log n)Direkter Zugriff per Kennung (konstante Zeit)Einfacher Durchlauf der Liste (n)
6Den kürzesten Weg durch 20 Städte zu finden, indem man alle Reihenfolgen testet, ist selbst für einen Supercomputer unmöglich. Warum?
Weil Supercomputer leider keine Distanzen zwischen Städten berechnen könnenWeil die Zahl der möglichen Wege astronomisch ist: Milliarden von MilliardenWeil es keine bekannte Formel gibt, um eine Distanz auf einer Karte zu messenWeil der Speicher sich nicht mehr als zehn Städtenamen auf einmal merken kann
7Ordne diese Komplexitäten von der SCHNELLSTEN zur LANGSAMSTEN (bei grossen Daten).
In die richtige Reihenfolge bringen:
Konstante Zeit: eine einzige Operation, was auch geschiehtLinear (n): die Zeit folgt der DatenmengeLogarithmisch (log n): die Zeit steigt sehr langsamQuadratisch (n²): die Zeit schiesst in die Höhe
8Manche Probleme kann ein Computer nicht lösen, egal wie leistungsfähig er ist, nicht einmal in unendlicher Zeit.
RichtigFalsch
9Was bedeutet es, dass ein Algorithmus in «linearer Zeit» (Komplexität n) läuft?
Seine Laufzeit hängt überhaupt nicht von der Menge der Daten abVerdoppelt man die Datenmenge, verdoppelt sich auch die RechenzeitDer Algorithmus endet in jeder Situation immer nach genau einer SekundeVerdoppelt man die Datenmenge, wird die Rechenzeit sofort vervierfacht
10Was kann eine Informatikerin tun, wenn die exakte Lösung eines Problems unvernünftig lange dauern würde? (mehrere Antworten)
Eine Heuristik nutzen: eine Methode mit angenäherter, aber schneller LösungSich mit einer «genügend guten» Antwort begnügen statt der allerbestenDie Grösse des Problems begrenzen oder seine Daten vereinfachenEinfach warten, bis Computer eines Tages stark genug für alles sind
11Ein Brute-Force-Algorithmus braucht 2ⁿ Versuche. Mit welchem Faktor wird die Zahl der Versuche multipliziert, wenn n von 10 auf 20 steigt?
Zahl als Antwort eingeben.
Die richtigen Antworten entdeckst du beim Spielen.
