AlgorithmenProzedur-Konzept und Reihung
23.04.2009Helmut Paulus Max-Planck-Gymnasium
Trier
Quelle: FDK Informatik - Unterrichtsgang durch die Themen des neuen Lehrplans
Links: http://www.informatik-lehren.de/umsetzung/ oder Download
Algorithmus
Eine Verarbeitungsvorschrift muss Anforderungen genügen, um als Algorithmus bezeichnet werden zu können:
• definierte Eingaben und Ausgaben ,es muss genau festgelegt werden, mit welchen "Eingabedaten“ der Algorithmus arbeitet und welche Daten er liefert.
• eindeutig,die einzelnen Schritte und ihre Abfolge sind unmissverständlich beschrieben, keine Mehrdeutigkeiten
• allgemein,es wird nicht nur ein Problem, sondern eine ganze Klasse von Problemen gelöst
• ausführbar,der "Prozessor" muss die Einzelschritte abarbeiten können
• endlich,endlicher Länge des Textes; der Algorithmus muss irgendwann zu einem Ende kommen; es muss eine vorhersagbare Obergrenze für die Anzahl der Schritte existieren.
2
DefinitionEin Algorithmus ist eine Verarbeitungsvorschrift, die so präzise formuliert ist, dass
sie auch von einer Maschine abgearbeitet werden kann.
Diese Eigenschaften lassen sich meist nicht (formal) nachweisen, sie sollten aber als Leitlinien für den Entwurf eines Algorithmus betrachtet werden.
Algorithmus
• Schachspiel sicher gewinnen
1. Stelle die Figuren auf
2. Wiederhole bis du gewonnen hast
a) Wähle den besten Zug aus
b) Führe diesen Zug aus
c) Warte bis der Gegner seinen Zug ausgeführt hat
3
Gegenbeispiele:
Hinweis auf math. Algorithmen der Antike (Heron, Euklid)
...
3
1
2
1
1
1:
222s (Nicht endlich)• Berechne die Summe
Ein erster Schritt zur Verbesserung:
2a) Untersuche alle möglichen Fortsetzungen, wähle einen Zug aus, der sicher zum Sieg führt.
Nicht effektiv: es gibt nur endlich viele Fortsetzungen, ihre Anzahl ist aber zu groß!
(nicht ausführbar)
Entwicklung einfacher Standardalgorithmen
4
Beispiel: ggT(a,b)
Darstellung als StruktogrammStruktur
Korrektheitstest (PAP)Ablauf/Datenfluss
Umgangssprachlich
Bestimme die kleinere der beiden Zahlen und speichere den Wert als Hilfszahl ab
Solange die Division beider Zahlen durch die Hilfszahl einen Rest ungleich Null ergibt, vermindere die Hilfszahl um Eins
Die Hilfszahl ist der ggT der vorgegebenen Zahlen
1. Setze die Hilfszahl h auf die kleinere der a und b
2. Solange h kein Teiler von a und b vermindere h um 1
3. Gib aus h
Formale Formulierung
Diskussion: Vorteile / Nachteile der unterschiedlichen Beschreibungen
Analyse einfacher Standardalgorithmen
5
Gütekriterien:
• KorrektheitEin Algorithmus sollte das vorgegebene Problem (gemäß Problemspezifikation!) lösen.
• Effektivität(Laufzeitverhalten, Resourcen)
Überprüfung der Korrektheit
1. Formal (Verifikation):Mittels logischer Herleitungen wird die Einhaltung der Bedingungen an die Zwischen- und Endergebnisse des Algorithmus bzw. Programms nachgewiesen.
2. Empirisch (Testen):Mit bestimmten ausgesuchten Daten, für die das Ergebnis bekannt ist, wird der Algorithmus bzw. das Programm erprobt. Dabei kann lediglich das Vorhandensein von Fehlern entdeckt, nicht jedoch die Fehlerfreiheit nachgewiesen werden.
Untersuchung des Laufzeitverhaltens
1. Grobe Abschätzung der VerarbeitungsschritteAbhängigkeit Laufzeit vom Datenumfang (z. B. Sortieralgorithmen)
2. Laufzeitmessungen
Vertiefung
6
Untersuchung der Effizienz verschiedener Standardalgorithmen:
Z. B.: Verschiedene ggT-Algorithmen:
Wikipedia: http://de.wikipedia.org/wiki/Euklidischer_Algorithmus
Algorithmus der Woche: http://www-i1.informatik.rwth-aachen.de/~algorithmus/index.php
Aufgaben:
• Algorithmus verstehen, Darstellung und Begründung des unterschiedlichen Aufwands
• Implementierung mit Laufzeitmessung
Weitere Beispiele:
• Multiplikation langer Zahlen (Algorithmus der Woche)
• Schnelles Potenzieren (Wikipedia)
• Russische Bauernmultiplikation (Wikipedia, K. Merkert: HSG-Kaiserslautern)
Laufzeitmessung mit Delphi: http://www.delphi-treff.de/tipps/applikation/
Laufzeitmessung mit Delphi
7
procedure TForm1.Button1Click(Sender: TObject);
var
Zeit: Cardinal;
begin
Zeit := GetTickCount;
//Befehlesfolge deren Zeitdauer bestimmt werden soll
Caption := IntToStr(GetTickCount - Zeit);
end;
procedure TForm1.Button2Click(Sender: TObject);
var
a, b, c: Int64;
begin
QueryPerformanceFrequency(a);
QueryPerformanceCounter(b);
//Befehlesfolge deren Zeitdauer bestimmt werden soll
QueryPerformanceCounter(c);
//Ausgabe in ms (Multiplikation mit 1000)
Caption := IntToStr((c - b) * 1000 div a);
end;
GetTickCount
QueryPerformanceCounter
Liefert die Zeit in ms , die seit dem letzten Windowsstart vergangen ist.
Rückgabewert vom Typ Cardinal(Vorzeichenloser 32Bit-Datentyp).
Auflösung: ms - Bereich
Timerfrequenzabfragen
Anzahl der Takte seit Start
Zeitspanne berechnen
Auflösung: > 1 ms
Prozedur-Konzept und Reihung
23.04.2009Helmut Paulus Max-Planck-Gymnasium
Trier
Nach: Fertige Programme in den Materialien zum WBK 10.2
Prinzip der Cäsarverschlüsselung
Einführung:
• Warum möchte man Texte verschlüsseln?
• Wie kann man Texte verschlüsseln?
• Als Beispiel soll ein altes Verschlüsselungsverfahren (Caesar) untersucht werden.Demonstration der Caesar Verschlüsselung mit Hilfe von Cryptool - das Prinzip des Verschlüsselungsverfahrens erkennen.
9
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
D E F G H I J K L M N O P Q R S T U V W X Y Z A B C
Chiffrierung nach Caesar
QuelltextHALLO
GeheimtextIBKKR
Schlüssel = 1
Entwickle ein System, mit dem man Texte nach der Caesar-Methode verschlüsseln und wieder entschlüsseln kann!
Algorithmen entwickeln und darstellen
Algorithmus in Wortform (Eigene Sprache)
10
Algorithmus verschlüsseln
Gib ein Quelltext, SchlüsselSetze Geheimtext auf ‘‘ Für jedes Zeichen von Quelltext
bestimme die Ordnungszahl nerhöhe n um Schlüsselwenn n > 90 dann
vermindere n um 26hänge an Geheimtext das zu n gehörende Zeichen
Gib aus Geheimtext
Vereinfachung: Der Quelltext besteht nur aus Großbuchstaben .
Grafische Form
Verarbeitung von Zeichen und Zeichenketten
11
Einführung des Datentyps „char“ für einzelne Zeichen
• Die zulässigen Zeichen und ihre Nummerierung werden durch den ASCII-Code festgelegt. (ASCII- Tabellen siehe z. B. Wikipedia, SELFHTML )
• Umwandlungsfunktionen „ord“ und „chr“ zum Kodieren bzw. Dekodieren
Kodierung: Ord(‘A‘) 65
Dekodierung : chr(65) ‘A‘
Evtl. auf Unicode eingehen
Vertiefung
Datentyp „string“ für Zeichenketten
• Der Zugriff auf die einzelnen Zeichen einer Zeichenkette erfolgt über einen Index. • Die Länge einer Zeichenkette bestimmt man mit der vordefinierten Operation „length“.• Zeichenketten kann man mit dem „+“ aneinander hängen.
Implementierung des Algorithmus
• Evtl. Wiederholung von programmiersprachlicher Details
• Implementierung des Verschlüsselungs- und des Entschlüsselungs-Algorithmus vorerst in den Ereignisverarbeitungsmethoden
• Lokale Variablen (EVA)
12
Einführung des Prozedurkonzepts (4)
• Entwicklung eines eigenen Datenmodells für die Ver- und Entschlüsselung:– Schlüssel, Klartext und Geheimtext als globale Variablen (Attribute im private-Abschnitt des
Formulars)
• Auslagerung der Algorithmen in eigene Prozeduren (Unterprogramme)– Programmeinheiten, die Anweisungen zur Lösung eines Teilproblems zu einer neuen Einheit
zusammenfassen
– Deklaration der Prozeduren (Methoden) im private-Abschnitt des Formulars
– Zur Vorbereitung auf das Objektkonzept wird hier statt mit Parameterübergabe mit globalen Variablen gearbeitet.
13
TGUI = class(TForm)procedure BVerschluesselnClick();procedure BEntschluesselnClick();
private{ Private-Deklarationen }schluessel : integer;quelltext: string;geheimtext: string;procedure Verschluessen;procedure Entschluesseln;
public{ Public-Deklarationen }
end;
procedure TGUI.verschluesseln;vari, n: integer;
begingeheimtext := '';for i := 1 to length(quelltext) dobegin
n := ord(quelltext[i]);n := n + Schluessel;if n > 90 then n := n - 26;geheimtext := geheimtext + chr(n);
endend;
procedure TGUI.BVerschluesselnClick();begin// Daten aktualisierenschluessel := StrToInt(ESchluessel.Text);quelltext := EQuelltext.Text;// Daten verarbeitenverschluesseln;// Benutzungsoberfläche aktualisierenEGeheimtext.Text := geheimtext;
end;
Deklaration und Implementierung als Bestandteil des Formulars Aufruf in der Ereignisbearbeitung
Vertiefung
14
Übungen: Erstelle weitere Prozeduren, die abgewandelte Caesar-Algorithmen enthalten (z.B. Umkehrung der Reihenfolge der Zeichen).
Link: Fertige Programme in den Materialien zum WBK 10.2
Weiterführung des Prozedurkonzepts (6)• Prozeduren mit Parametern
– Aktuelle und formale Parameter
– Verzicht auf Variablenparameter (call-by-reference)
• Funktionen
15
Ergänzungen des Verschlüsselungsalgorithmus durch Varianten, z.B.
• Löschen von Leerzeichen im Klartext
• Umwandlung in nur Großbuchstaben
• Einbeziehung von Sonderzeichen in der verwendeten Sprache.
Der Quelltext kann mit Hilfe vordefinierter String-Operationen (Length, Pos, Delete, Insert) implementiert werden. Hierzu muss man genau wissen, wie diese String-Operationen benutzt werden können.
• Alle Informationen, die man zur Benutzung einer Operation benötigt, werden in einer sog. Schnittstellenbeschreibung festgelegt.
• Ziel ist also zunächst, den Umgang mit Schnittstellenbeschreibungen kennen zu lernen.
Schnittstellenbeschreibungen
16
procedure Delete(var S: string; Index, Count: integer);
Beschreibung:Delete entfernt, beginnend mit S[Index], Count Zeichen aus dem String S. Ist der Wert von Index größer als die Länge von S, werden keine Zeichen gelöscht. Werden mit Count mehr Zeichen angegeben, als beginnend bei S[Index] im String vorhanden sind, wird der Rest des Strings gelöscht.
Beispiel: Wort := ‘Autobahn‘ Delete(Wort, 5, 4); Wort > ‘Auto'}
Delphi-Hilfe
procedure Insert(Source: string; var S: string; i: integer);
Beschreibung:Insert fügt Source in S an der Position S[i] ein.
Beispiel: Wort:= ‘Haus‘;
Insert(‘bar', Wort, 4);
Wort = ‘Hausbar‘
Funktion / Prozedur
17
Eine Funktion liefert einen Wert zurück, ist also ein Unterprogramm mit Rückgabewert.Eine Prozedur ist ein Unterprogramm ohne Rückgabewert.
function Length(S: string): integer;
Beschreibung:Length gibt die Anzahl der im angegebenen String vorhandenen Zeichen zurück.
Beispiel:Anzahl := Length(‘Autobahn');
Anzahl = 8
Typ des Rückgabewertes
Der Rückgabewert wird weitergegeben
Aufruf einer Prozedur dagegen nur als eigenständige Anweisung:Insert(‘bar', Wort, 4);
Parameter
18
Mit Hilfe von Parametern werden Daten zur Laufzeit an das betreffende Unterprogramm übergeben. Bei der Deklaration werden für die zu übergebenden Daten Platzhalter (formale Parameter) eingeführt, denen zur Laufzeit dann bestimmte Werte (aktuelle Parameter)
übergeben werden.
procedure Delete(var S: string; Index, Count: integer);
Beispiel:
Wort := ‘Autobahn‘;
Delete(Wort, 1, 4);
Wort = ‘bahn‘;
Formale Parameter
Aktuelle Parameter
Übergabemechanismen:call-by-value: Der Wert des aktuellen Parameters wird an den Werteparameter übergeben.
call-by-reference: Es wird eine Referenz zwischen dem aktuellen Parameter und dem Referenzparameter erzeugt. (Kann verzichtet werden)
Aufgabe
Es ist eine Prozedur zu entwickeln, die in einer Zeichenkette eine Zeichenkette durch eine neue ersetzt.
Beispiel: Ersetze `Hans` durch `Peter` innerhalb von `Hans im Glück‘
19
procedure TGUI.ersetze(alt: string; neu: string);
var
stelle: integer;
hilfstext: string;
begin
hilfstext := '';
stelle := pos(alt, Quelltext);
while stelle > 0 do
begin
hilfstext := hilfstext + Copy(Quelltext, 1, stelle-1) + neu;
Delete(Quelltext, 1, stelle + length(alt)-1);
stelle := pos(alt, Quelltext);
end;
hilfstext := hilfstext + Quelltext;
Quelltext := hilfstext;
end;
Lösung mit globaler Variable Quelltext (aus WBK10.2)
Lösung Quelltext vorbereiten
20
procedure TGUI.vorbereiten;
Var
c: char;
begin
for c := 'a' to 'z' do
ersetze(c, chr(ord(c)-32));
ersetze('Ä', 'AE‘);
ersetze('Ö', 'OE‘);
ersetze('Ü', 'UE‘);
ersetze('ä', 'AE‘);
ersetze('ö', 'OE‘);
ersetze('ü', 'UE‘);
ersetze('ß', 'SS‘);
ersetze(' ', ‘');
ersetze('.', ‘‘);
ersetze('!', ‘‘);
ersetze(',', ‘‘);
for c := '0' to '9' do
ersetze(c, ‘‘);
// u.s.w.
end;
• Löschen von Leerzeichen
• Umwandlung in nur Großbuchstaben
• Sonderzeichen in der verwendeten Sprache.
• Entfernen von Steuerzeichen
procedure TGUI.vorbereiten;
var
c: char;
i: integer;
hilfstext: string;
begin
hilfstext := '';
for i := 1 to length(Quelltext) do
begin
c := text[i];
case c of
'A'..'Z': hilfstext := hilfstext + c;
'a'..'z': hilfstext := hilfstext +
chr(ord(c)-32);
'ß': hilfstext := hilfstext + 'SS';
'ä': hilfstext := hilfstext + 'AE';
'ö': hilfstext := hilfstext + 'OE';
'ü': hilfstext := hilfstext + 'UE';
'Ä': hilfstext := hilfstext + 'AE';
'Ö': hilfstext := hilfstext + 'OE';
'Ü': hilfstext := hilfstext + 'UE';
end;
end;
Quelltext := hilfstext;
end;
Alternative
Datenstruktur Reihung (7)
• Entschlüsselung ohne bekannten Schlüssel.– Erarbeitung einfacher Verfahren der Kryptoanalyse, z.B. mit Hilfe einer
Häufigkeitsverteilung von Buchstaben in den Schriftstücken.
• Problem: Zeichenketten müssen geeignet abgelegt sein.– Einführung und Erläuterung des Begriffs "Reihung",
– Erarbeitung und Erläuterung des Zugriffs auf abgelegte Zeichenketten (Indizierung), Operationen mit Zeichenketten
– Einarbeitung in die schon erarbeiteten Algorithmen
• Implementierung und Übung
• Vertiefende Übungen zu Algorithmen auf Reihungen– Lösung per Standardalgorithmus: Finde das Maximum in der Reihung.
– Zufällige Würfelserien simulieren und auswerten
– Lottoziehung
– Primzahlensieb
– …
21
Häufigkeitsanalyse
22
type
THaeufigkeit = array ['A'..'Z'] of integer;
TGUI = class(Tform)
…
private
{ Private-Deklarationen }
schluessel : integer,
quelltext: string;
geheimtext : string;
haeufigkeit: THaeufigkeit;
procedure verschluesseln;
procedure entschluesseln;
procedure vorbereiten;
procedure analysieren;
public
{ Public-Deklarationen }
end;
Erweiterung des Datenmodells
Datentyp für dieHäufigkeitstabelle
Häufigkeitstabelle
Häufigkeitsanalyse
23
procedure TGUI.analysieren;
var
c: char;
i: integer;
begin
for i := 1 to length(quelltext) do
begin
c := quelltext[i];
haeufigkeit[c] := haeufigkeit[c] + 1;
end;
end;
Procedure TGUI.BTextAnalysierenClick();
Var
c: char;
begin
// Datenmodell aktualisieren
for c := 'A' to 'Z' do
haeufigkeit[c] := 0;
analysieren;
// Anzeige aktualisieren
MHaeufigkeitText.Clear;
for c := 'A' to 'Z' do
MHaeufigkeitText.Lines.Add(c + ' -> ' +
IntToStr(haeufigkeit[c]);
end;
ProzedurText analysieren
Aufruf in der Ereignisbearbeitung
Memo-Komponente als mehrzeiliges Ausgabefeld
Literaturhinweise und Links
24
E. Modrow: Informatik mit Delphi, Band 1/2, Dümmler-Stam 1998-2000.
P. Damann, J. Wemßen: Objektorientierte Programmierung mit Delphi, Band 1. Klett-Verlag 2001.
U. Bänisch: Praktische Informatik mit Delphi, Band 1/2. Cornelsen 2001.
Frischalowski: Delphi 5.0, Band 1/2, Herdt-Verlag 1999.
Pohl: Schülerübungen / Klausuren in Delphi, Heft 1/2, Verlag J. Pohl 1997-2001.
K. Merkert:http://hsg.region-kaiserslautern.de/faecher/inf/material/delphi/index.php
R. Mechling:http://www.gk-informatik.de/
K. Heidler:http://www.friedrich.fr.schule-bw.de/delphi/delphi.htm
Hessischer Bildungsserver:http://lernen.bildung.hessen.de/informatik/
S. Spolwig: http://oszhdl.be.schule.de/gymnasium/faecher/informatik/delphi/index.htm
Weitere Hinweise unter:
http://www.delphi-source.de
Einsteiger-Tutorial
http://www.delphi-treff.de/content/tutorials/einsteigerkurs/
…
