Algorithmen Prozedur-Konzept und Reihung · Algorithmen Prozedur-Konzept und Reihung 23.04.2009...

Post on 06-Aug-2019

215 views 0 download

transcript

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/