Aufgaben: Die Strukturen eines Programms

Erkläre, was eine Variable in einem Programm ist, und gib ein Beispiel: Welchen Namen und welchen Inhalt hätte eine Variable in einem Videospiel, die die Punkte des Spielers speichert? Welche Operation würde ihren Wert beim Abschluss eines Levels ändern?

Erkläre, was eine bedingte Anweisung (wenn ... dann ... sonst ...) ist, und schreibe zwei Beispiele für Entscheidungen aus dem Alltag, die mit dieser Struktur ausgedrückt werden. Gib jeweils die Bedingung und die beiden möglichen Aktionen an.

Erkläre, was eine Schleife ist und welches Problem sie gegenüber dem vielfachen Wiederholen derselben Anweisungen löst. Schreibe in Pseudocode eine Schleife, die die Zahlen von 1 bis 5 ausgibt.

Erkläre den Unterschied zwischen einer Variablen und einer Konstanten in einem Programm, mit je einem Beispiel aus einem Abrechnungsprogramm (der Preis des Produkts im Gegensatz zum Mehrwertsteuersatz).

Die Daten eines Programms haben einen Typ: Ganzzahl, Dezimalzahl, Text oder Boolean. Gib für jedes Datum den am besten geeigneten Typ an und begründe ihn: das Alter einer Person, ihre Körpergröße in Metern, ihr Name und ob sie bestanden hat oder nicht.

Erkläre, was eine Funktion in einem Programm ist, und nenne zwei Vorteile davon, den Code in benannte Funktionen aufzuteilen (Wiederverwenden ohne Kopieren, jeden Teil getrennt verstehen und testen).

Was ist ein Kommentar im Quelltext? Erkläre, an wen sich Kommentare richten (nicht an den Computer, sondern an diejenigen, die den Code später lesen), und was ein guter Kommentar erklären sollte (das Warum von Entscheidungen, nicht das, was man ohnehin sieht).

Lies dieses Fragment und erstelle die Ablaufverfolgung (Trace):

Start

    x ← 4

    x ← x + 2

    ausgeben x

Ende

Gib an, welcher Wert auf dem Bildschirm angezeigt wird, und erkläre, warum die zweite Anweisung keine mathematische Gleichung, sondern eine Zuweisung ist.

Lies dieses Programm in Pseudocode:

Start

    summe ← 0

    n ← 1

    solange n ≤ 5 tue

        summe ← summe + n

        n ← n + 1

    Ende solange

    ausgeben summe

Ende

Erstelle die Ablaufverfolgung Schritt für Schritt (Wert von summe und n am Ende jedes Durchlaufs) und gib an, wie oft die Schleife wiederholt wird und welcher Wert am Ende ausgegeben wird.

Schreibe in Pseudocode ein Programm, das die Punktzahl einer Klausur (eine Zahl von 0 bis 10) einliest und „bestanden“ ausgibt, wenn die Punktzahl 5 oder größer ist, und andernfalls „nicht bestanden“. Verwende eine Variable, eine Dateneingabe und eine Verzweigung.

Das Flussdiagramm in der Abbildung stellt ein Programm mit einer Schleife dar: Es liest eine Zahl n ein und gibt, solange n größer als 0 ist, ihren Wert aus und zieht 1 ab, wie in der Abbildung gezeigt.

Wenn der Benutzer n = 3 eingibt: (a) Erstelle die Ablaufverfolgung und gib an, welche Werte n annimmt und was in jedem Durchlauf ausgegeben wird; (b) gib an, wie oft der Schleifenrumpf ausgeführt wird; (c) erkläre, was passieren würde, wenn der Benutzer n = 0 eingäbe.

Dieses Programm klassifiziert eine Person nach ihrem Alter:

Start

    einlesen alter

    wenn alter ≥ 18 dann

        ausgeben "volljährig"

    sonst

        ausgeben "minderjährig"

    Ende wenn

Ende

Erstelle die Ablaufverfolgung für die Eingabe 17 und für die Eingabe 21 und gib jeweils an, welche Bedingung ausgewertet wird und was auf dem Bildschirm ausgegeben wird.

Schreibe in Pseudocode ein Programm, das den Countdown von 10 bis 1 ausgibt und nach dem Ende der Schleife „Abheben!“ ausgibt. Verwende eine Variable und eine solange-Schleife.

Dieses Programm addiert die Zahlen, die der Benutzer eingibt, bis er eine Null eingibt:

Start

    summe ← 0

    einlesen n

    solange n ≠ 0 tue

        summe ← summe + n

        einlesen n

    Ende solange

    ausgeben summe

Ende

Erstelle die Ablaufverfolgung für die Eingabefolge 4, 3, 0: Gib den Wert von n und summe nach jedem Einlesen an und was am Ende ausgegeben wird. Erkläre außerdem, warum das erste einlesen n außerhalb der Schleife steht.

Das Flussdiagramm in der Abbildung stellt die Zugangskontrolle eines Geräts dar: Es gibt höchstens drei Versuche, das richtige Passwort einzugeben, wie in der Abbildung gezeigt.

(a) Erkläre den vollständigen Ablauf des Programms, wenn der Benutzer das Passwort zweimal falsch und beim dritten Mal richtig eingibt. (b) Gib an, wie oft das Programm höchstens nach dem Passwort fragt. (c) Begründe, warum die Variable versuche nur in einem der Zweige der zweiten Raute erhöht wird.

Dieses Programm sollte die Zahlen von 1 bis 5 ausgeben, hat aber einen Fehler:

Start

    n ← 1

    solange n ≤ 5 tue

        ausgeben n

    Ende solange

Ende

1. a) Finde den Fehler: Was fehlt im Schleifenrumpf?

1. b) Erkläre, was passiert, wenn das Programm so ausgeführt wird, wie es geschrieben ist.

1. c) Schreibe den korrigierten Pseudocode.

Ein Mitschüler behauptet, dass der folgende Pseudocode immer funktioniert und der effizienteste ist, um zu zählen, wie viele Zahlen zwischen zwei beliebigen positiven ganzen Zahlen $A$ und $B$ ($A \le B$) gleichzeitig durch $3$ und durch $5$ teilbar sind:

Start

    einlesen A, B

    gesamt ← 0

    solange A ≤ B tue

        wenn (A mod 3 = 0) oder (A mod 5 = 0) dann

            gesamt ← gesamt + 1

        Ende wenn

        A ← A + 1

    Ende solange

    ausgeben gesamt

Ende

(a) Widerlegen Sie zwei Schwächen seines Vorschlags: einen Fehler in der bedingten Logik gemessen an der geforderten Spezifikation und eine algorithmische Ineffizienz (analysieren Sie, wie viele Durchläufe und Bedingungsauswertungen durchgeführt werden, wenn $B - A = 1\,000\,000$).

(b) Wenn zwingend eine solange-Schleife verwendet werden muss, schreiben Sie den Algorithmus neu und optimieren Sie Startwert und Schrittweite so, dass möglichst wenige Durchläufe nötig sind und innerhalb der Schleife keine Verzweigung ausgewertet wird.

(c) Entwerfen Sie eine mathematische Lösung in konstanter Zeit $O(1)$ ohne Schleifen in Pseudocode und begründen Sie die verwendete Formel formal.

Entwerfen Sie in Pseudocode einen Algorithmus für das Spiel „Zahlenraten“, bei dem die Rollen vertauscht sind: Der Benutzer denkt sich eine geheime ganze Zahl zwischen $1$ und $100$ aus und der Computer muss sie mit der optimalen Strategie der binären Suche erraten.

(a) Schreiben Sie den Pseudocode des Algorithmus. In jedem Durchlauf schlägt der Computer die Mitte des aktuellen Intervalls vor und der Benutzer antwortet, ob die geheime Zahl „größer“ oder „kleiner“ ist oder ob die Maschine „richtig geraten“ hat.

(b) Bauen Sie einen Validierungsmechanismus ein, der erkennt, ob der Benutzer einen Widerspruch begeht oder schummelt (zum Beispiel, wenn sich die Grenzen des Suchintervalls überkreuzen, weil die untere Grenze die obere übersteigt), und das Programm mit einer begründenden Warnmeldung beendet.

(c) Begründen Sie formal, wie viele Versuche der Computer höchstens benötigt, um jede Zahl im Bereich $[1; 100]$ zu erraten, und sagen Sie vorher, wie viele Versuche höchstens erforderlich wären, wenn der Bereich auf $[1; 1\,000]$ erweitert würde.

Entwerfen Sie in Pseudocode den Steuerungsalgorithmus für eine per Taster geregelte Fußgängerampel, der den Verkehr einer Hauptstraße sicher steuert und die folgenden Anforderungen erfüllt:

1. Im Ruhezustand zeigt die Fahrzeugampel Grün.

2. Um Staus durch ständige Anforderungen zu vermeiden, muss zwischen zwei aufeinanderfolgenden Fußgängerphasen eine Mindestgrünzeit für Fahrzeuge von $30$ Sekunden gewährleistet sein.

3. Sobald diese Mindestzeit verstrichen ist und ein Tastendruck eines Fußgängers erkannt wurde, lautet die zwingende Abfolge: Gelb für Fahrzeuge für $3$ Sekunden, Rot für Fahrzeuge und Grün für Fußgänger für $15$ Sekunden und schließlich blinkendes Grün für Fußgänger für $4$ Sekunden, bevor das Grün für Fahrzeuge wiederhergestellt wird.

(a) Schreiben Sie den Pseudocode des Systems, strukturiert innerhalb einer Endlosschleife zur Überwachung.

(b) Analysieren Sie, welchen Blockadefehler die Kreuzung erleiden würde, wenn der Sensor im dauerhaft aktiven Zustand ausfiele (Taster klemmt), und begründen Sie, wie Ihr Entwurf verhindert, dass die Hauptstraße dauerhaft zusammenbricht.

(c) Begründen Sie technisch, warum es in nebenläufigen Echtzeit-Steuerungssystemen vorzuziehen ist, einen Zeitstempel der Uhr (aktuelle_zeit()) abzufragen, statt die CPU durch passives blockierendes Warten (warten()) anzuhalten.

Analysieren Sie den folgenden Algorithmus, der Indexpaare $(i, j)$ verarbeitet:

Start

    einlesen N

    zaehler ← 0

    für i von 1 bis N tue

        für j von i bis N tue

            wenn (i + j) mod 2 = 0 dann

                zaehler ← zaehler + 1

            Ende wenn

        Ende für

    Ende für

    ausgeben zaehler

Ende

(a) Leiten Sie eine Formel her und begründen Sie sie algebraisch, die angibt, wie oft insgesamt die Bedingung wenn in Abhängigkeit von $N$ ausgewertet wird (berechnen Sie die Summe der Durchläufe der inneren Schleife bezogen auf die äußere).

(b) Sagen Sie den exakten Endwert von zaehler voraus, wenn die Eingabe $N = 5$ ist, und erstellen Sie dazu eine Trace-Tabelle, die die Werte von $i$, $j$, das Ergebnis der Bedingung und die Aktualisierungen von zaehler zeigt.

(c) Ein Schüler behauptet: „Da die verschachtelte Schleife Zahlenpaare durchläuft, würde das Ersetzen von für j von i bis N durch für j von 1 bis N und das Teilen des Endergebnisses durch $2$ für jedes $N$ genau dasselbe Ergebnis liefern.“ Zeigen Sie durch eine formale Argumentation oder ein Gegenbeispiel, ob diese Behauptung wahr oder falsch ist.

Ein IT-Sicherheitsanalyst überprüft den folgenden Pseudocode, der die Zugangskontrolle mit Karte und PIN an einem Bankterminal steuern soll:

Start

    geheime_pin ← 3852

    versuche ← 0

    gesperrt ← falsch

    solange versuche < 3 und nicht gesperrt tue

        einlesen eingegebene_pin

        wenn eingegebene_pin = geheime_pin dann

            ausgeben "Willkommen im System"

        sonst

            versuche ← versuche + 1

            ausgeben "PIN falsch"

        Ende wenn

    Ende solange

    wenn versuche = 3 dann

        gesperrt ← wahr

        ausgeben "Karte aus Sicherheitsgründen gesperrt"

    Ende wenn

Ende

(a) Identifizieren Sie einen schwerwiegenden Fehler im Kontrollfluss, der auftritt, wenn der Benutzer beim ersten Versuch die richtige PIN eingibt, und begründen Sie ihn.

(b) Sagen Sie das Verhalten des Programms und den Endwert der Variablen versuche und gesperrt voraus, wenn der Benutzer die Eingabefolge 1111, 3852, 9999 eingibt.

(c) Schreiben Sie den Algorithmus in Pseudocode neu und korrigieren Sie den Ablauf so, dass ein sauberer sofortiger Ausstieg nach einem Treffer und eine strikte Sperrung nach drei aufeinanderfolgenden Fehlversuchen gewährleistet sind, wobei unter keinen Umständen die Willkommensmeldung erscheinen darf, wenn die Karte gesperrt wird.

Beim Entwurf einer hydraulischen Anlage werden zylindrische Buchsen aus Sphäroguss mit ringförmigem Querschnitt (Kreisring) und einer Dichte $\rho = 7{,}2\text{ g/cm}^3$ verwendet.

(a) Entwerfen Sie in Pseudocode eine Funktion area_anillo(radio_int, radio_ext), die die Fläche des Kreisrings ($\pi \cdot (r_{ext}^2 - r_{int}^2)$) berechnet und zurückgibt. Die Funktion muss prüfen, dass $radio\_ext > radio\_int > 0$ gilt; verletzen die Parameter diese physikalische Bedingung, muss sie $-1{,}0$ als Fehlercode zurückgeben. Verwenden Sie $\pi \approx 3{,}1416$.

(b) Entwerfen Sie eine zweite Funktion masa_tubo(radio_int, radio_ext, longitud, densidad), die area_anillo aufruft, um das Volumen und die Gesamtmasse des Abschnitts in Kilogramm zu berechnen (die Abmessungen werden in Zentimetern und die Dichte in $\text{g/cm}^3$ eingegeben). Gibt area_anillo einen Fehler zurück oder ist die Länge kleiner oder gleich null, muss die Funktion den Wert $-1{,}0$ weitergeben.

(c) Führen Sie die vollständige Ablaufverfolgung der Ausführung von masa_tubo(4{,}0, 5{,}0, 100{,}0, 7{,}2) durch, geben Sie die in jede Funktion eingehenden und aus ihr ausgehenden Werte an und begründen Sie das erhaltene numerische Ergebnis.

Der Qualitätssicherungsausschuss einer Schule bewertet den folgenden Algorithmus, der die Endnote eines technischen Moduls aus drei Teilnoten ($N_1, N_2, N_3 \in [0{,}0; 10{,}0]$) bestimmen soll. Die offizielle Vorschrift lautet: „Der Schüler gilt als ‚bestanden‘, wenn der gewichtete Mittelwert ($30\,\%$ für $N_1$, $30\,\%$ für $N_2$ und $40\,\%$ für $N_3$) gleich oder größer als $5{,}0$ ist, sofern keine der Einzelnoten kleiner als $4{,}0$ ist; andernfalls gilt er als ‚nicht bestanden‘.“

Start

    einlesen N1, N2, N3

    mittel ← N1 · 0,3 + N2 · 0,3 + N3 · 0,4

    wenn mittel ≥ 5,0 oder (N1 ≥ 4,0 und N2 ≥ 4,0 und N3 ≥ 4,0) dann

        ausgeben "bestanden"

    sonst

        ausgeben "nicht bestanden"

    Ende wenn

Ende

(a) Erklären Sie ausführlich, warum das Programm keinen Syntaxfehler erzeugt und normal ausgeführt wird, obwohl es einen kritischen Logikfehler in der Verzweigung enthält.

(b) Entwerfen Sie zwei Testtripel von Noten $(N_1, N_2, N_3)$, die den Fehler des Algorithmus offenlegen: eines, das ein falsch positives Ergebnis verursacht (das Programm erklärt „bestanden“, obwohl es „nicht bestanden“ sein müsste), und eines, das ein falsch negatives Ergebnis verursacht (oder begründen Sie, ob Letzteres mit dem aktuellen Ausdruck möglich ist).

(c) Schreiben Sie den Algorithmus in Pseudocode neu, indem Sie die logische Bedingung korrigieren und eine vorherige Prüfung ergänzen, die verifiziert, dass die drei eingegebenen Noten im gültigen Bereich $[0{,}0; 10{,}0]$ liegen.

Ein unerfahrener Programmierer hat das Spiel „Zahlenraten“ mit einer einzigen Funktion umgesetzt, die direkt auf globale Variablen zugreift:

globale Variablen: geheimzahl, versuche

funktion runde_spielen()

    ausgeben "Gib eine Zahl ein (1-100): "

    einlesen tipp

    versuche ← versuche + 1

    wenn tipp = geheimzahl dann

        ausgeben "Richtig geraten in ", versuche, " Versuchen!"

    sonst

        wenn tipp < geheimzahl dann

            ausgeben "Die Geheimzahl ist größer"

        sonst

            ausgeben "Die Geheimzahl ist kleiner"

        Ende wenn

    Ende wenn

Ende funktion

(a) Begründen Sie drei Nachteile dieses Entwurfs anhand der Konzepte Kopplung, Seiteneffekte und mangelnde Kohäsion. Warum verhindert das Vermischen der Konsolen-Ein-/Ausgabe mit der Vergleichslogik, dass diese Funktion in einer grafischen Oberfläche oder einer Webanwendung wiederverwendet werden kann?

(b) Definieren Sie die modulare Architektur neu, indem Sie drei Funktionen mit geringer Kopplung erstellen: eine reine Vergleichsfunktion (die den Tipp und die Geheimzahl erhält und eine Ergebniskennung zurückgibt), eine Eingabevalidierungsfunktion (die den Bereich $[1; 100]$ prüft) und eine Funktion zur Zustandsaktualisierung. Geben Sie für jede die genaue Signatur (Name, Parameter mit Typ und Rückgabetyp) und ihre Zuständigkeiten an.

(c) Schreiben Sie in Pseudocode das Hauptprogramm, das diese Funktionen durch Parameterübergabe und Rückgabewerte koordiniert, ohne eine einzige globale Variable zu verwenden.