GK Informatik
LPE1
Algorithmen / Aufgaben
Daten, Formate, Dokumente
Für den Computer ist jede Datei nur eine Bytefolge.
Es gibt 2 verschiedene Grundtypen von Dateien:
Programm-Dateien (.exe, .com, .dll) enthalten
Daten-Dateien (.txt, .doc, .bmp, .jpg) enthalten
Prozessor-Befehle;
Benutzer-Informationen.
Die Zuordnung zwischen Daten und Kodierungs-Information nennt man ein Datenformat.
Algorithmen
z.B. Kodierungsvorschrift für RLE-Komprimierung
Wir denken uns alle Pixel des Bildes in der unter 2a) und 2b)
beschriebenen Reihenfolge in einer "Pixelschlange" aufgereiht.
Setze die "aktive Farbe" auf "schwarz".
Wiederhole nun die folgenden Schritte
{
i.
Bestimme die Anzahl n der am Anfang der Schlange aufeinander folgenden Pixel,
die die aktive Farbe haben. Dabei darf n höchstens 255 werden.
Gibt es mehr als 255 "aktiv"-farbige Pixel hintereinander, dann halte beim 255. Pixel an.
ii.
Schreibe das Byte n in die Daten.
iii.
Streiche die schon gezählten Pixel ab,
d.h.: die Schlange beginnt nun mit dem ersten noch nicht gezählten Pixel.
iv.
Wenn die aktive Farbe "schwarz" ist,
dann:
schalte sie auf "weiß" um,
andernfalls:
schalte sie auf "schwarz" um.
}
solange, bis keine Pixel mehr in der "Schlange" sind.
Eingabe (Pixelbild)
⇒
⇒
Algorithmus (Arbeitsanweisungen)
Ausgabe (Bilddatei)
Drei Grundstrukturen von Arbeitsanweisungen und deren Darstellung (Struktogramm)
1. Sequenz, d.h. Anweisungsfolge:
Sequenz
Anweisung 1
Setze die "aktive Farbe" auf "schwarz".
Wiederhole nun die folgenden Schritte
2. Schleife, d.h. Wiederholte Ausführung
Wiederhole nun die folgenden Schritte
{
Arbeitsanweisung
}
solange, bis
3. Entscheidung bzw. logische Alternative
Wenn die aktive Farbe "schwarz" ist,
dann:
andernfalls:
Anweisung 2
Schleife
Wiederhole solange bis
Anweisung 1
Anweisung 2
Entscheidung
Weiß?
ja
Schwarz
nein
Weiß
GK Informatik
LPE1
Algorithmen / Aufgaben
Sequenz, Entscheidung und Schleife
sind die universellen Bausteine, aus denen sich jeder noch so komplizierte Algorithmus aufbauen läßt.
1. Der RLE-Algorithmus enthält an einer Stelle eine reichlich komplexe Anweisung, die eigentlich
nur für Menschen verständlich ist, sicher aber nicht für einen Computer, nämlich die Anweisung:
v.
Bestimme die Anzahl n der am Anfang der Schlange aufeinander folgenden Pixel,
die die aktive Farbe haben. Dabei darf n höchstens 255 werden.
Gibt es mehr als 255 "aktiv"-farbige Pixel hintereinander, dann halte beim 255. Pixel an.
Schreibe das Byte n in die Daten.
Zerlegen Sie diese Anweisung in "kleinere Häppchen"
und stellen Sie den Teil-Algorithmus in einem eigenen Struktogramm dar.
2. Erstellen Sie ein Struktogramm für einen Algorithmus,
der aus einer Menge von drei Zahlen {a, b, c} den größten Wert g heraussucht.
3. Erstellen Sie ein Struktogramm für einen Algorithmus,
der aus einer Menge von k Zahlen den größten Wert heraussucht. Obwohl sich diese Aufgabe recht
ähnlich anhört wie die vorige, erfordert sie wahrscheinlich doch einen ganz anderen Lösungsansatz!
4. Stellen Sie den Algorithmus zum
Bestimmen der Lösungsmenge einer linearen Gleichung der Form "a ∗ x + b = 0"
mit einem Struktogramm dar! Beachten Sie dabei, daß hier verschiedene Fälle zu unterscheiden sind, je
nachdem, ob a oder b von Null verschieden sind oder nicht. Daher greift die Idee "x = –b/a" zu kurz.
Selbst für den Fall "a=b=0" sollte Ihr Algorithmus die korrekte Lösungsmenge liefern!
5. Lösen Sie die entsprechende Aufgabe für quadratische Gleichungen der Form "a*x² + b*x + c = 0"!
Sie können dabei voraussetzen, daß es sich bei der gegebenen Gleichung wirklich um eine echte quadratische Gleichung handelt, mit anderen Worten: a darf als verschieden von Null vorausgesetzt werden.
Bemühen Sie aber auch bei dieser Aufgabe darum, daß Ihr Algorithmus für alle dann noch möglichen
Varianten des Problems stets die korrekte Lösungsmenge liefert!
6. Wer eine richtig leistungsfähige Algorithmensammlung aufbauen will, wird die quadratische Gleichung
aus der vorigen Aufgabe etwas allgemeiner sehen: in "a*x² + b*x + c = 0" sollen nun beliebige Werte für
a, b und c zugelassen werden! Damit muss Ihr Algorithmus nun auch den Fall "a = 0" behandeln.
RLE-Komprimierung
Algorithmus zur Run Length Encoding Komprimierung von Monochrom Bildern
Wir denken uns alle Pixel des Bildes in der unter 2a) und 2b)
beschriebenen Reihenfolge in einer "Pixelschlange" aufgereiht.
Setze die "aktive Farbe" auf "schwarz"
Wiederhole, bis keine Pixel in der Schlange
Bestimme die Anzahl n der am Anfang der Schlange
aufeinander folgenden Pixel, die die aktive Farbe haben.
Schreibe das Byte n in die Daten
Streiche die schon gezählten Pixel ab,
die Schlange beginnt nun mit dem ersten noch nicht gezählten Pixel.
Ist die aktive Farbe schwarz
ja
nein
Setze WEISS
Setze SCHWARZ
© Copyright 2024 ExpyDoc
