GSG-Lebach Informatik
Serviceseite für Schüler des Informatikkurses 2002 - 2004 (Steffen)
Diese Seite verschiedene Materialien und Beispielprogramme zu den Themen des
Grundkurses Informatik am Geschwister-Scholl-Gymnasium Lebach 2002 - 2004. Als
Programmiersprache wurde damals Standard-Pascal bzw. Turbo-Pascal verwendet.
1. Datentyp ARRAY (Feld)
Ein Feld kann mehrere Werte des gleichen Typs aufnehmen. Die Werte
sind angeordnet und nummeriert. Dadurch sind die Werte über diese Nummer, den Index,
ansprechbar.
Wichtige Algorithmen sind das Sortieren der Elemente eines Feldes. Im Programm SORT.PAS
werden zwei einfache Sortierverfahren dargestellt, einmal das sog. Bubble-Sort-Verfahren
und das Sortieren durch Auswahl, jeweils als Prozedur formuliert.
2. Datentyp SET (Menge)
Eine Menge kann bis zu 256 Elemente des gleichen Typs enthalten. Im Gegensatz zu einem Feld (array) sind die Elemente nicht angeordnet. Häufig wird der IN-Operator verwendet, der überprüft, ob ein Element IN der Menge ist.
a) Programm MENGE1.PAS : Ein Text wird zeichenweise
über die Tastatur eingegeben. Ist der Buchstabe ein Vokal, d.h. liegt er
in der Menge der Vokale, so wird statt dessen ein * ausgegeben.
b) Programm MENGE2.PAS : In diesem Beispiel soll die
Menge 6 verschiedene zufällige Lottozahlen aufnehmen. Das Problem, dass keine
Zahl doppelt vorkommen darf, wird durch Verwendung der Menge elegant und einfach
gelöst. Zur _bung werden die erzeugten Lottozahlen in einer Datei
abgespeichert.
3. Datentyp FILE
Der Datentyp FILE dient dazu, viele Variable des gleichen Typs in einer Datei auf der Festplatte abzuspeichern. Die Werte sind dort sequentiell (hintereinander) angeordnet.
Programm PRIMFILE.PAS : In diesem Beispiel werden Primzahlen erzeugt und in eine Datei gespeichert. Zusätzlich werden beim Lesen aus der Datei auch die sog. Primzahlzwillinge erkannt.
4. Datentyp RECORD
Eine Variable vom Typ RECORD (Verbund) kann Komponenten verschiedener Typen aufnehmen. Die einzelnen Komponenten sind nicht angeordnet; sie müssen bei der Ein- und Ausgabe direkt angesprochen werden.
a) Programm BRUCH.PAS : In diesem Programm wird gezeigt, wie mit Hilfe des Typs RECORD ein eigener Datentyp erzeugt wird, der eine Bruchzahl repräsentiert. Exemplarisch werden zwei Brüche in kleinen Prozeduren addiert und multipliziert.
b) Programm RECORD1.PAS : Hier wird ein relativ umfangreicher Datentyp erstellt, der in etwa den Eintragungen in einer Kundenkartei entspricht. Die Ein- und Ausgabe erfolgt jeweils in eigenen Prozeduren.
c) Programm MP3DAT.PAS : Dieses kleine Dateiprogramm zur Verwaltung von mp3-Dateien verbindet den Datentyp record (für die Daten eines mp3-Titels) mit dem Datentyp array (zur Aufnahme vieler Titel). Das Programm enthält Prozeduren für die wichtigsten Arbeiten mit einer Datei: Eingabe und Löschen einzelner Titel, Laden und Speichern, Sortieren und Suchen.
5. Programmieren mit Modulen
Ein Modul ist die Zusammenfassung von Objekten und Operationen mit folgenden Eigenschaften:a) Eine Kommunikation mit der Umgebung ist nur über definierte Schnittstellen möglich.
b) Die Zusammenfassung von Moduln zu einem Programm ist ohne Kenntnis des Modulinnern möglich.
5.1 einfache Module
Ein einfacher Modul definiert seine Leistung
als eine Operation
Op : D ---> V; Jedem Wert aus einer Definitionsmenge wird ein anderer Wert aus einer Menge V
zugeordnet.
Die klassischen Programmiersprachen unterstützen diese Modultechnik durch Funktionen
und Prozeduren.
Beispiel: Ein Rechteck ist charakterisiert durch Werte für Länge,
Breite, Umfang und Flächeninhalt. Das kleine Programm Modul
1 demonstriert, wie mit Hilfe einer Prozedur und einer Funktion aus den
Seitenlängen die beiden anderen Größen ermittelt werden.
5.2 Units
Eine Unit stellt eine Sammlung von Typendeklarationen, Konstanten, Variablen, Prozeduren und Funktionen dar. Die Unit ist separat übersetzbar und kann von anderen Programmen (ohne erneute Übersetzung) verwendet werden kann. Einige dieser Prozeduren sind von außen zugänglich, die Zugangsprozeduren. Die Daten selbst und die übrigen Prozeduren sind von außen nicht zugänglich.Beispiel: Die Prozedur bzw. Funktion zur Berechnung von Umfang und Flächeninhalt eines Rechtecks können auch in eine Unit ausgelagert werden. Der zugehörige Quelltext rechteck.pas zeigt, wie's gemacht wird.
Im Hauptprogramm stehen die in der Unit vereinbarten Methoden durch die Anweisung USES rechteck; zur Verfügung.
5.3 Objekte
Unter einem Objekt versteht man in der Informatik zweierlei:
- ein Ding in der realen Welt
- ein programmiertes Modell davon
Ein Objekt hat einen Zustand, der durch Attribute (Eigenschaften) beschrieben wird, und
Methoden, die angeben, was man mit dem Objekt tun kann bzw. was das Objekt kann. Die Methoden erlauben den Zugriff auf die Attributwerte.
Beispiel: Das oben dargestellte Modul Rechteck mit vier Eigenschaften und
zwei Methoden soll nun auch als Objekt in Pascal vereinbart werden.
Der Einfachheit halber werden die beiden Prozeduren ohne Parameter formuliert,
da die zugehörigen Eigenschaften im Objekt bereits definiert sind. Die
einzige im Programm vereinbarte Variable r enthält Informationen zu Länge, Breite,
Umfang, Fläche
und die beiden Methoden zur Berechnung von Umfang
und Flächeninhalt!
5.4 Eigene Unit für Turtle-Grafik
Als Anwendung des modularen Programmierens wird eine sog. Turtle-Grafik
definiert. Eine "Schildkröte" hat die Eigenschaften Ort (x- und
y-Koordinate), Richtung (Winkel) und Farbe. Diese Schildkröte kann sich nach
links und rechts drehen, sich vorwärts bewegen und ihre Farbe ändern. Dabei
zeichnet sie eine Linie in der aktuellen Farbe.
Die Schildkröte soll in einer eigenen Unit zum Leben erweckt werden.
Der öffentliche Interface-Teil sieht folgendermaßen aus:
UNIT gsgturt;
{einfache Turtle-Befehle, Lebach 2002}
INTERFACE {oeffentlicher Teil}
USES crt,graph;
{oeffentliche Vereinbarung des Objektes, hier der Methoden}
PROCEDURE grafikein; {schaltet Grafikmodus ein}
PROCEDURE grafikaus; {schaltet Grafikmodus aus}
PROCEDURE home(x,y : REAL); {stellt turtle in Startposition (x/y)}
PROCEDURE vor(s : REAL); {turtle geht vorwaerts}
PROCEDURE drehelinks(w : REAL); {turtle wird gedreht}
PROCEDURE dreherechts(w : REAL); {
"
}
PROCEDURE schreibe(x,y : INTEGER; notiz: STRING); {Textausgabe}
{schreibt an die Grafikposition (x,y) einen Text
PROCEDURE zeichenfarbe(f : word); {legt die Zeichenfarbe fest}
PROCEDURE loeschebild; {löscht aktuelles Bild}
Eine schöne Anwendung sind rekursiv definierte Kurven, wie die
berühmte Koch-Kurve. Der Quelltext kann hier
geladen werden.
6. Rekursive Algorithmen
Rekursive Algorithmen verwenden sich selbst bei ihrer eigenen Beschreibung. Ein bekanntes einfaches Beispiel ist die Fakultät einer natürlichen Zahl n. Es gilt:
0! = 1 und n! = n * (n-1)!
Schon ein wenig raffinierter ist die rekursive
Bestimmung der Nullstelle einer Funktion durch das sog.
Intervall-Halbierungs-Verfahren. Die zugehörige Prozedur "nullstelle"
kann Bestandteil eines größeren Programms zur Untersuchung reeller Funktionen
sein. Ein solches Programm "plot.pas"
kann hier geladen werden.
7. Dynamische Datenstrukturen
Die Datentypen Menge, Verbund, Feld werden als statische Datentypen
bezeichnet, ihre Größe ist beim Aufruf des Programms bereits festgelegt.
Dynamische Datenstrukturen dagegen ändern ihre Struktur und Größe während
der Programmausführung. Die wichtigsten dynamischen Datenstrukturen sind lineare
Listen (einfach oder ringförmig verkettet, Stapel, Schlange) und Bäume
(insbesondere binäre Bäume). Die Beziehung zwischen einzelnen Datenelementen
wird über Zeiger hergestellt.
Weitere Informationen enthält ein Manuskript, das im Schuljahr 2002/2003 für
den Grundkurs Informatik am GSG Lebach entstand. --->
download Manuskript - hoffentlich ohne Tippfehler :-)
8. Formale Sprachen
8.1 Endliche Automaten
Endliche Automaten besitzen innere Zustände. Die Übergänge zwischen den
Zuständen hängt von den Eingabezeichen ab. Solche Automaten können verwendet
werden, um bestimmte Zeichenfolgen zu erkennen.
Beispiel: Ein Automat soll "Programme" der Form y = x + x + x
. erkennen; Die Anzahl der Folge "+ x" sei unbegrenzt. Durch ein
kleines Pascal-Programm kann ein solcher erkennender Automat realisiert
werden. ---> automat.pas
8.2 Syntaxüberprüfung durch rekursiven Abstieg
Die Syntax einer Sprache kann durch Syntaxdiagramme beschrieben werden.
Terminalsysmbole, die in der Sprache selbst vorkommen, werden dabei in runde
Kästchen geschrieben; Nichtterminalsymbole, die zur Beschreibung der Sprache
dienen, werden in Rechtecken dargestellt. Die Syntaxüberprüfung erfolgt so,
dass jedem Nichtterminalsysmbol eine (eventuell rekursive) Prozedur zugeordnet
wird.
Beispiel: Syntaxdiagramm für obige Sprache
S ---> ( y ) ---> ( = ) ---> [ term ] ---> ( . )
term ----> ( x ) ------->
I I
I<-- ( + )
---
Entsprechendes Pascalprogramm zur Syntaxüberprüfung: ---> parser.pas
8.3 Syntaxdiagramm der Programmiersprache PASCAL (nach Dr. Gerd Wegener, Hannover)
8.4 Parser und Compiler der einfachen Sprache PAS03
Im Grundkurs Informatik 13/1 wurde im Herbst 2003 ein Parser und ein Compiler
für eine einfache Sprache PAS03 entwickelt. Die Zielsprache ist für eine
sogenannte Kellermaschine konzipiert, bei der z.B. der Befehl ADD die beiden
obersten Elemente des Kellers bzw. des Stapels addiert werden und das Ergebnis
wieder oben aufgelegt wird.
Ein mögliches Quellprogramm ist:
BEGIN READ X
Y = 3 * ( 1 + 2 * X )
WRITE Y
END
Der Compiler erzeugt daraus das maschinennahe Programm:
READ X
LOAD 3
LOAD 1
LOAD 2
LOAD X
MUL
ADD
MUL
STOR Y
WRIT Y
STOP
Zum Experimentieren kann der Quelltext dieses einfachen Compilers hier geladen werden ---> PASCOM03.PAS.
Um zu sehen, wie das maschinennahe Programm mit Hilfe eines Stapels abgearbeitet wird, werden die Maschinenbefehle an einen Interpreter übergeben. Dieser arbeitet die Befehle ab und zeigt den Ablauf auch am Bildschirm an. So bekommt die theoretische Kellermaschine zumindest eine quasireale Existenz. ---> COMP.EXE
9. Kryptologie
Im Grundkurs Informatik wird am Ende der Klassenstufe 13 auch das Thema Verschlüsselung behandelt. Die wichtigsten Verfahren werden in einem kleinen Manuskript vorgestellt.
- Compiler Turbo-Pascal 5.5 (ca. 300 kByte)
Die Firma Borland bietet ihren
Compiler für Turbo-Pascal in der Version 5.5 mit einem integrierten Editor
inzwischen als sog. "freeware" allen interessierten Programmierern -
also auch Schülern - zur
kostenlosen Benutzung an. Die wichtigsten Dateien sowie zwei kleine Beispiele
zur Grafikprogrammierung können auch hier geladen werden.
siehe auch:
http://www.steffen-lebach.de/downinf.htm
http://mitglied.lycos.de/gsginf11/
Besucherzähler:
Impressum: W. Steffen, GSG Lebach, Straße der Weißen Rose, 66822 Lebach