Informatik: Übungs-Testlets für den TestAS

Ein Algorithmus ist eine endliche Folge genau festgelegter Schritte, die ein Problem löst. Das Sortieren ist eines der am meisten untersuchten Probleme der Informatik, weil sortierte Daten viel effizienter durchsucht und verarbeitet werden können.

Bubblesort ist einer der einfachsten Sortieralgorithmen. Er durchläuft die Liste wiederholt, vergleicht benachbarte Elemente und vertauscht sie, wenn sie in falscher Reihenfolge stehen. Nach dem ersten Durchlauf ist das größte Element ans Ende der Liste „aufgestiegen“; nach dem zweiten Durchlauf steht das zweitgrößte an seinem Platz und so weiter. Der Algorithmus kann früher aufhören, wenn ein Durchlauf keine Vertauschung macht, da die Liste dann sortiert ist. Selectionsort arbeitet anders: Er sucht im unsortierten Teil das kleinste Element und tauscht es nach vorn, und das für jede Position. Beide Algorithmen brauchen eine Zahl von Vergleichen, die mit dem Quadrat der Listenlänge wächst, was sie für große Listen langsam macht; Algorithmen wie Mergesort und Quicksort sind in der Praxis viel schneller.

Ein weiterer klassischer Algorithmus, den Euklid vor mehr als 2000 Jahren beschrieb, findet den größten gemeinsamen Teiler (ggT) zweier positiver ganzer Zahlen. Er beruht darauf, dass der ggT von a und b gleich dem ggT von b und dem Rest von a geteilt durch b ist. Der Algorithmus ersetzt das Paar (a, b) wiederholt durch (b, a mod b), bis die zweite Zahl null ist; die erste Zahl ist dann der ggT. Für 48 und 18: 48 mod 18 = 12, ergibt (18 | 12); 18 mod 12 = 6, ergibt (12 | 6); 12 mod 6 = 0, ergibt (6 | 0). Der ggT ist 6. Der Algorithmus ist sehr effizient, weil die Zahlen schnell kleiner werden.

ggT(a, b) = ggT(b, a mod b) ggT(a, 0) = a

Um einen Algorithmus zu verstehen oder zu prüfen, verfolgen Informatiker ihn von Hand an kleinen Beispielen, notieren den Zustand nach jedem Schritt und testen Sonderfälle wie eine leere Liste, eine Liste mit einem Element oder eine bereits sortierte Liste. Zu beweisen, dass ein Algorithmus für alle Eingaben korrekt ist, verlangt mehr: eine Begründung, oft mit Schleifeninvarianten, dass er immer terminiert und immer das richtige Ergebnis liefert.

Ein Student verfolgt Bubblesort an der Liste unten und geht in jedem Durchlauf von links nach rechts.

Programme treffen Entscheidungen mit Bedingungen, die entweder wahr oder falsch sind. Solche Bedingungen sind boolesche Ausdrücke, benannt nach dem Mathematiker George Boole, und sie werden aus Vergleichen gebildet, die mit den Operatoren AND, OR und NOT verknüpft sind. Der Ausdruck (alter ≥ 18) AND (hatTicket) ist nur wahr, wenn beide Teile wahr sind; (istMitglied) OR (bezahlt) ist wahr, wenn mindestens ein Teil wahr ist; NOT(istGesperrt) ist genau dann wahr, wenn istGesperrt falsch ist.

Das Verhalten jedes booleschen Ausdrucks lässt sich mit einer Wahrheitstabelle prüfen, die das Ergebnis für jede Kombination der Eingaben auflistet. Bei n Eingangsvariablen gibt es 2ⁿ Zeilen. Zwei Ausdrücke sind gleichwertig, wenn ihre Wahrheitstabellen übereinstimmen. Wichtige Äquivalenzen sind die Gesetze von De Morgan: NOT(A AND B) ist gleichwertig zu (NOT A) OR (NOT B), und NOT(A OR B) ist gleichwertig zu (NOT A) AND (NOT B). Sie werden oft genutzt, um Bedingungen zu vereinfachen oder das Gegenteil einer Bedingung richtig auszudrücken: Das Gegenteil von „der Nutzer ist angemeldet und ist Administrator“ ist „der Nutzer ist nicht angemeldet oder ist kein Administrator“, nicht „der Nutzer ist nicht angemeldet und kein Administrator“.

NOT(A AND B) ≡ (NOT A) OR (NOT B) NOT(A OR B) ≡ (NOT A) AND (NOT B) A OR (A AND B) ≡ A

Viele Programmiersprachen werten boolesche Ausdrücke mit Kurzschlussauswertung aus: Ist in A AND B A falsch, wird B gar nicht ausgewertet, da das Ergebnis falsch sein muss; ist in A OR B A wahr, wird B übersprungen. Programmierer nutzen das, um Fehler zu vermeiden, und schreiben zum Beispiel (x ≠ 0) AND (10 / x > 2), damit die Division nie ausgeführt wird, wenn x null ist.

Boolesche Logik ist auch die Grundlage digitaler Hardware: Dieselben Operatoren werden als Logikgatter umgesetzt, und jede Rechnung in einem Prozessor ist letztlich eine Kombination von ihnen.

Die Software einer Bibliothek entscheidet, ob ein Nutzer ein Buch ausleihen darf. Die Variablen sind M (der Nutzer ist Mitglied), F (der Nutzer hat unbezahlte Gebühren) und S (das Buch ist ein besonderes Präsenzexemplar). Die Ausleihe ist erlaubt, wenn die Bedingung M AND (NOT F) AND (NOT S) wahr ist.