Einführung in Suchalgorithmen: Version mit Programmierung

Vermutlich sind Sie so vorgegangen, dass Sie beim ersten Element begonnen und dann jedes Element der Reihe nach geprüft haben, bis Sie den gesuchten Namen gefunden haben. Sie hätten auch zufällig Karten auswählen können (mit der Bedingung, dass Sie keine Karte zweimal wählen). Im Durchschnitt wäre das jedoch nicht besser.

In beiden Fällen liegt die maximale Anzahl an Versuchen bei 8, und der Durchschnitt liegt über viele Durchgänge hinweg bei 4,5 Versuchen. Die Strategie, jedes Element eines Feldes nacheinander zu prüfen, bis eine Übereinstimmung gefunden wird, nennt man lineare Suche. Im ungünstigsten Fall entspricht die Anzahl der Vergleiche der Größe des Datenfeldes, das durchsucht wird. Man sagt, die Komplexität des Algorithmus ist O(n) (Big-O-Notation), weil die Anzahl der nötigen Vergleiche bei einem Datenfeld mit n Elementen in der Größenordnung von n liegt.

Bei klassischen Computern gibt es keine Möglichkeit, ein unsortiertes Datenfeld schneller als mit dieser Vorgehensweise zu durchsuchen. Mit einem Quantencomputer kann man eine solche Suche in O(√n) Schritten durchführen. Diese Methode, bekannt als Grover-Algorithmus, behandeln wir in Stunde 4.

Sobald die Schüler*innen ihren Code geschrieben haben, stellt die Lehrkraft die lineare Suche vor (das heißt: Die Datenelemente werden der Reihe nach geprüft, bis das gesuchte Element gefunden ist oder alle Elemente des Datenfeldes überprüft wurden) und erläutert, dass dies das beste klassische Verfahren zur Suche in unsortierten Datenfeldern ist. Die lineare Suche hat die Komplexität O(n), während das entsprechende Quantenverfahren (der Grover-Algorithmus, der in Stunde 4 behandelt wird) die Komplexität O(√n) hat.

Beispielcode:

import random

namesArray = [
    "Adriano", "Birte", "Edouard",
    "Elena", "Florian", "Inez",
    "Niamh", "Oliver"
]

random.shuffle(namesArray)
nameToFind = "Elena"

numGuesses = 1
i = 0

while namesArray[i] != nameToFind:
    i += 1
    numGuesses += 1

print("The shuffled array was:")
print(namesArray)
print(
    nameToFind +
    " found at position " +
    str(i + 1) +
    " in " +
    str(numGuesses) +
    " guesses"
)

Die beste Strategie ist, zunächst das mittlere Element des Datenfeldes zu prüfen. Wenn Sie eine Übereinstimmung finden, sind Sie fertig. Ist der gesuchte Name im Alphabet weiter hinten als der geprüfte Name, gehen Sie zum Mittelpunkt der oberen Hälfte des Datenfeldes und prüfen erneut. Ist er im Alphabet weiter vorne, gehen Sie zum Mittelpunkt der unteren Hälfte und prüfen erneut. Wiederholen Sie dieses Vorgehen, bis Sie den Namen gefunden haben.

Je nachdem, wie Sie bei der Bestimmung der Mittelpunkte gerundet haben, sollten Sie „Inez“ nach zwei oder drei Versuchen gefunden haben. Die maximale Anzahl an Versuchen beträgt vier, und der Durchschnitt über alle Namen liegt bei Anwendung dieser Strategie bei 2,625.

Dieses Verfahren nennt man binäre Suche. Die Kenntnis der Struktur des Datenfeldes macht diese Suche deutlich schneller als eine lineare Suche. Im ungünstigsten Fall hängt die Anzahl der Vergleiche mit dem Logarithmus zur Basis 2 der Anzahl der Elemente zusammen. Im Beispiel oben gibt es 8 Elemente: log₂(8) = 3. Wenn es 1024 Elemente gäbe, wären höchstens 11 Vergleiche nötig log₂(1024) = 10. Man sagt, die Komplexität des Algorithmus ist O(log(n)) (Big-O-Notation), weil die Anzahl der nötigen Vergleiche bei einem Datenfeld mit n Elementen in der Größenordnung von log(n) liegt.

Sobald die Schüler*innen ihren Code geschrieben haben, stellt die Lehrkraft die binäre Suche vor (das heißt: Es wird stets das mittlere Element des Datenfeldes gewählt; je nach Ergebnis des Vergleichs wird die Suche anschließend in der unteren oder oberen Hälfte des Datenfeldes fortgesetzt) und erläutert, dass dies das beste klassische Verfahren zur Suche in sortierten Datenfeldern ist. Die binäre Suche hat die Komplexität O(log(n)).

Beispielcode:

namesArray = ["Adriano", "Birte", "Edouard", "Elena", "Florian", "Inez", "Niamh", "Oliver"]
nameToFind = "Inez"
 
numGuesses = 1
low = 0
high = len(namesArray) - 1
mid = int((low + high) / 2)
 
while namesArray[mid] != nameToFind:
    if nameToFind > namesArraylow = mid + 1
    else:
        high = mid - 1
    mid = int((low + high) / 2)
    numGuesses += 1
 
print(nameToFind + " found at position " + str(mid + 1) + " in " + str(numGuesses) + " guesses")

Vermutlich haben Sie erkannt, dass Sie durch das Abfragen einer von zwei Möglichkeiten pro Merkmal jedes Mal etwa die Hälfte der Kandidaten ausschließen konnten. Da es acht Figuren gab, reichten drei Fragen, um die Figur jedes Mal eindeutig zu bestimmen (die Figuren wurden so ausgewählt, dass sie alle unterschiedlichen Kombinationen der drei binären Merkmale darstellen, sodass am Ende keine Mehrdeutigkeit entstehen kann).

Das Ergebnis ist in allen Fällen: drei Versuche. Das ist eine Variante der binären Suche aus Aufgabe 2a. Entsprechend liegt die Komplexität des Algorithmus wieder bei O(log(n)) (wobei man in diesem Fall bei jeder Suche genau log₂(n) Fragen benötigt).

Im Quantencomputing hat genau diese Problemstruktur eine bemerkenswerte Lösung: Die gesuchte Antwort kann mit einem einzigen Durchlauf gefunden werden, unabhängig davon, wie groß n ist. Dieses Problem ist als Bernstein-Vazirani-Problem bekannt, und wir werden in Stunde 3 sehen, wie der zugehörige Algorithmus funktioniert.

Sobald die Schüler*innen ihren Code geschrieben haben, erläutert die Lehrkraft, dass die richtige Strategie darin besteht, jeweils genau ein Merkmal abzufragen (z. B. „Trägt die Person eine Brille?“). Dadurch wird bei jeder Abfrage etwa die Hälfte der Figuren ausgeschlossen, sodass die richtige Figur bei acht Möglichkeiten immer mit drei Abfragen bestimmt werden kann. Dies ist eine Variante der binären Suche, da sich der Suchraum bei jedem Schritt erneut halbieren lässt. Dieses Beispiel wurde gewählt, weil es äquivalent zu einem speziellen Suchproblem ist, dem Bernstein-Vazirani-Problem, bei dem der Quantenalgorithmus die Komplexität O(1) hat. Dieser Algorithmus wird in Stunde 3 behandelt.

Beispielcode:

namesArray = [
    ["Adriano", "Blond", "Blue", "No Glasses"],
    ["Birte", "Blond", "Blue", "Glasses"],
    ["Edouard", "Blond", "Brown", "No Glasses"],
    ["Elena", "Blond", "Brown", "Glasses"],
    ["Florian", "Brown", "Blue", "No Glasses"],
    ["Inez", "Brown", "Blue", "Glasses"],
    ["Niamh", "Brown", "Brown", "No Glasses"],
    ["Oliver", "Brown", "Brown", "Glasses"]
]

hairColour = "Brown"
eyeColour = "Brown"
wearsGlasses = "No Glasses"

possibleCandidates = [
    True, True, True, True,
    True, True, True, True
]

for i in range(0, len(namesArray)):
    if namesArray[i][1] != hairColour:
        possibleCandidates[i] = False
    if namesArray[i][2] != eyeColour:
        possibleCandidates[i] = False
    if namesArray[i][3] != wearsGlasses:
        possibleCandidates[i] = False

i = 0
while possibleCandidates[i] == False:
    i += 1

print(
    "The person with these characteristics is " +
    namesArray[i][0]
)

Die richtige Strategie besteht darin, jede Primzahl der Reihe nach zu testen. Wenn die Zahl nicht durch die Primzahl teilbar ist, nimmt man die nächste Primzahl in der Liste. Ist sie teilbar, berechnet man den Quotienten und prüft dann erneut, ob dieser Quotient durch die Primzahlen in der Liste teilbar ist (wieder beginnend von vorne).

Diese Strategie nennt man Probeteilung (trial division). Bei einer Zahl wie 8192, die viele kleine Primfaktoren besitzt, kann man die Primfaktorzerlegung relativ schnell durchführen (in diesem Fall mit 12 Rechenschritten). Wenn eine Zahl jedoch nur zwei Primfaktoren hat, die zudem ähnlich groß sind, ist das Verfahren deutlich langsamer. Im Fall von 6557 (=79·89) benötigt man 22 Rechenschritte, um die Faktoren zu finden.

Würde man eine Zahl konstruieren, die das Produkt aus zwei Primzahlen ist, die zum Beispiel jeweils 600 Stellen haben, könnte sie nicht einmal ein Supercomputer faktorisieren. Der RSA-Algorithmus, der weltweit zur Verschlüsselung im Bankwesen und im Internet eingesetzt wird, stützt seine Sicherheit genau auf diese Tatsache. Bei klassischen Computern gilt dieses Verschlüsselungsverfahren daher als praktisch nicht zu knacken.

Quantencomputing könnte jedoch Wege eröffnen, diese und andere Verfahren zu brechen, die bislang als unknackbar galten. In Stunde 5 und 6 lernen Sie das RSA-Verschlüsselungssystem kennen und sehen, wie der Shor-Algorithmus einen möglichen Weg bietet, wie ein Quantencomputer RSA angreifen könnte.

Sobald die Schüler*innen ihren Code geschrieben haben, bestätigt die Lehrkraft die Ergebnisse: Für 8192 werden 12 Rechenschritte benötigt, für 6557 22 Rechenschritte. Ziel dieser Aufgabe ist es zu verdeutlichen, dass die Primfaktorzerlegung großer Zahlen rechnerisch aufwendig ist, insbesondere dann, wenn eine Zahl das Produkt zweier großer Primzahlen ist. Der RSA-Algorithmus, auf dem ein großer Teil der Internetverschlüsselung basiert, stützt seine Sicherheit auf die Schwierigkeit, große Zahlen zu faktorisieren. In Stunde 5 wird der RSA-Algorithmus behandelt, und in Stunde 6 wird gezeigt, wie ein Quantenalgorithmus – der Shor-Algorithmus – dies eines Tages möglicherweise brechen könnte.

Beispielcode:

primesArray = [
    2, 3, 5, 7,
    11, 13, 17, 19,
    23, 29, 31, 37,
    41, 43, 47, 53,
    59, 61, 67, 71,
    73, 79, 83, 89,
    97
]

numberToFactorise = 8192
primeFactorArray = []

totalCalcs = 0

def inPrimesArray(x, primesArray):
    isPrime = False
    for i in
    range(0, len(primesArray)):
        if x == primesArray[i]:
            isPrime = True
    return isPrime

while inPrimesArray(numberToFactorise, primesArray) == False:
    i = 0
    totalCalcs += 1
    while numberToFactorise % primesArray[i] != 0:
        i += 1
        totalCalcs += 1
    primeFactorArray.append(primesArray[i])
    numberToFactorise = numberToFactorise / primesArray[i]

primeFactorArray.append(int(numberToFactorise))

print("The prime factors array is ")
print(primeFactorArray)
print(
    "The number of calculations required was " +
    str(totalCalcs)
)