1. Übung zum Kurs Algorithmische Mathematik II fileZudem soll das Programm diese eingelesene...

1. Ubung zum KursAlgorithmische Mathematik II

Averkov, Zeile, PetersEmail: clemens.zeile@ovgu.de, benjamin.peters@ovgu.de

Fakultat fur MathematikOtto-von-Guericke-Universitat Magdeburg

Sommersemester 201613. April 2016

1 / 51

Inhalt I

OrganisatorischesScheinkriterienSonstiges und Fragen

Unterschiede zwischen C und C++

Prasenzaufgaben

Programmiergrundlagen (Backup)Variablen, Datentypen, OperationenProzedurenKontrollstrukturenRekursion

2 / 51

Scheinkriterien

Teil 1:

I voraussichtlich 10 Ubungsblatter,

I in denen insgesamt 50 % der Punkte zu erreichen sind.

I Die Ubungsblatter sollen in 2er Gruppen abgegeben werden.

I Ublicherweise gibt es 4 Aufgaben: eine Programmieraufgabe, dreiBeweisaufgaben.

I Alle Aufgaben sind abzugeben. Von den Beweisaufgaben sind bestimmteAufgaben als Votieraufgabe gekennzeichnet. Um fur Votieraufgaben Punkte zuerhalten, muss jeder in der Lage sein diese auch vorzurechnen.

I Fur die Programmieraufgabe(n) gelten die Hinweise aus dem ersten Semester,Abgaben an clemens.zeile@ovgu.de

Teil 2:

I Ende Mai wird eine Aufgabe fur ein Programmierprojekt bekanntgegeben.

I Dieses soll in 3er Gruppen bearbeitet werden und

I Anfang Juli abgegeben werden.

I Um den Schein zu erhalten (fur die Prufung zugelassen zu werden) muss dasProgrammierprojekt erfolgreich prasentiert werden.

3 / 51

Sonstiges und Fragen

I Ubungsaufgaben werden immer 1 Woche nach Abgabe besprochen

I Donnerstag-Ubung am 5. Mai 2016 fallt aus (Christi Himmelfahrt) und wirdnachgeholt

I Wann wollt ihr mit der Ubung beginnen?

I Andere Fragen?

4 / 51

C und C++

I C++ (erstmals 1983) ist Nachfolger bzw. eine Erweiterung von C, daher haufig

”C/C++“

I C++ ist zu C abwartskompatibel, womit sich (fast alle) C-Programme auch miteinem C++-Compiler ubersetzen lassen.

I Wichtigste Erweiterung Objektorientierte Programmierung (OOP) - auch mit Cmoglich, doch C++ hilft dem Entwickler dabei.

I Die Erweiterungen, die in C++ existieren, werden mit den gleichen Konstruktengesteuert (Entscheidungen treffen, Programmteile in Funktionen zusammenfassenund Wiederholungen durch Schleifen), die bereits C eingefuhrt hat.

I Mit Standardbibliothek deutlich komfortabler: Strings anstatt Char, bool alsDatentyp (0 oder 1) und viele weitere Optionen

I Dateiendungen: .h und .c fur C-Programme, .h/.hpp und .cpp fur C++

I Referenzen und Zeiger in C++, nur Zeiger in C

5 / 51

Ausgabe

Dieses C-Programm schreibt”Hallo Welt“ auf den Bildschirm und lasst sich also auf C

und C++ gleichermaßen ubersetzen, es ist also ein C/C++-Programm.

Folgendes Programm ist ein reines C++-Programm, das ebenfalls”Hallo Welt“ auf

den Bildschirm schreibt:

Ein C-Compiler wurde dieses Programm nicht ubersetzen konnen.

6 / 51

OOP: Klassen und Objekte

C++ kennt Klassen und Strukturen, Hauptmerkmale

I Objekte werden durch Klassen beschrieben, sind vom gleichen Typ (z.B. Klasse

”Auto”, Objekte: verschiedene Modelle)

I Schlusselwort class

I Attribute (auch Eigenschaften, Variablen) und Methoden (Funktionen)bestimmen Objekt einer Klasse.

I public: Zugriff auch außerhalb der Klasse, private: nur innerhalb Klasse

7 / 51

OOP: Klassen und Objekte, Beispiel

8 / 51

OOP: Klassen und Objekte, Beispiel

9 / 51

StrukturenEine Struktur ist nun ein benutzerdefinierter Datentyp - ein Datentyp, den Sie selbsterstellen

10 / 51

Aufgabe 1

Schreiben Sie ein Programm, das Vorname, Nachname und Alter in eine Struktur(person) einliest. Hinweis: Nutzen Sie zum Einlesen folgende Funktion aus derStandardbibliothek:

std :: cin >> variablenname;

Zudem soll das Programm diese eingelesene Informationen der person-Struktur ineinem Satz ausgeben.

1. Schreiben Sie zunachst alles in eine Datei (.cpp)

2. Splitten Sie dann Struktur, Funktionen (.hpp) und main (.cpp in einzelne Dateienauf

11 / 51

Exkurs: HeapsI Heap (englisch wortlich: Haufen oder Halde) auf Baumen basierende abstrakte

DatenstrukturI Objekte oder Elemente konnen abgelegt und aus diesem wieder entnommen

werdenI Elementen ist Schlussel zugeordnet, der die Prioritat der Elemente festlegtI Verwendung finden Heaps vor allem dort, wo es darauf ankommt, schnell ein

Element mit hochster Prioritat aus dem Heap zu entnehmen (HIFO-Prinzip),beispielsweise bei Vorrangwarteschlangen.

12 / 51

Aufgabe 2

Erstellen Sie eine Struktur myHeap mit den Attributen data (ganzzahliges Array),maxSize und size. Diese soll durch eine Funktion createHeap(int maxSize) initialisiertwerden. Erstellen Sie eine Funktion insertHeap (myHeap (*)heap, int value), die heapmit value befullt. Lassen Sie sich heap durch eine Funktion printHeap ausgeben.Hinweis: Das Attribut data soll als Zeiger initialisiert werden.

13 / 51

Programmiergrundlagen

I Variablen

I Prozeduren

I Parameterubergabe

I Kontrollstrukturen

I Rekursion

14 / 51

Imperative Programmierung

Definition 4.1Imperative Programmierung ist ein Programmierparadigma, in welchem ein Programmals Folge von Anweisungen (Befehlen) dargestellt wird, die im Speicher aufbewahrteRechengroßen verandern.

BemerkungAssemblersprachen und viele moderne hohere Programmiersprachen sind imperativ.

15 / 51

Variable

Definition 4.2Variable ist ein Behalter fur Rechnungsgroßen (Werte) die im Verlauf desRechenprozesses auftreten. Variable hat einen Namen und eine bestimmte Adresse imSpeicher. Der Wert der Variable kann sich im Verlauf der Berechnung andern. Der Typ(Datentyp) einer Variable bestimmt die Menge der moglichen Werte, welche dieVariable annehmen kann.

16 / 51

Variable (Fortsetzung)

Variable:

I Variablenname ist Bezeichner fur ein Objekt.

I Objekt kann durch die Verwendung des Variablennamens verandert undausgegeben werden.

I Objekt belegt einen bestimmten Bereich im Speicher (vgl. [?, § 4.9.6])

I Jede gegebene Variable darf nur innerhalb eines bestimmten Gultigkeitsbereiches(engl. scope of the variable) benutzt werden.

17 / 51

Deklaration von Variablen

Definition 4.3Deklaration einer Variable ist eine Anweisung, die einen Variablennamen in dasProgramm einfuhrt.

Definition 4.4Definition einer Variable ist eine Anweisung, die eine Variable in das Programmeinfuhrt.

18 / 51

Einfache Datentypen

Definition 4.5Ein Datentyp ist einfach, falls er nicht in andere Datentypen zerlegbar ist.

z.B.:

I Numerische Datentypen (ganze Zahlen, Gleitkommazahlen)

I Zeichen (engl. character) ist druckbares Symbol oder ein Kontrollzeichen(Tabulation, Neue Zeile usw.)

I Boolescher Typ ist der Typ, dessen Variablen zwei mogliche Werte annehmenkonnen (die Werte Wahr oder Falsch).

I Zeiger

19 / 51

Zeiger

I Ein Zeiger ist eine Variable, deren Wert Adresse eines Objektes ist.

I Zeiger ermoglichen Vernetzung von Objekten.

I Zeiger ermoglichen dynamische Speicherbelegung.

I Zeiger sind nicht in allen hoheren Programmiersprachen verfugbar.

I Zeiger ist ein low-level-Konzept (sie existieren in Assemblersprachen)

20 / 51

Zuweisung

Definition 4.6Zuweisung (Bezeichung :=) ist Operation der Form

BEZEICHNER := AUSDRUCK,

wobei BEZEICHNER der Name einer Variable ist und AUSDRUCK ein Ausdruck,der einen Wert zuruckgibt. Nach der Ausfuhrung der Zuweisung enthalt die Variableden Ruckgabewert des Ausdruckes.

Definition 4.7Ein Ausdruck ist ein Konstrukt (in einer gegeben Sprache), welches ausgewertetwerden kann.

Definition 4.8In allgemeiner Situation steht der BEZEICHNER fur einen sogenannten lvalue (einenAusdruck, der zu einem Objekt im Speicher ausgewertet wird).

21 / 51

Zuweisung: Beispiel

Listing 1: zuweisungen beispiel.py

1 x=122 y=23 temp=x4 x=y5 y=temp6 x=x+17 y=2∗y+x

Zeile x y temp1 12 ? ?2 12 2 ?3 12 2 124 2 2 125 2 12 126 3 12 127 3 27 12

22 / 51

Bemerkungen zu Zuweisungen

I Andere Bezeichnungen fur Zuweisung: = (C++ und viele weitere Sprachen;inkompatibel mit mathematischen Texten, wo = als Gleichheitzeichen benutztwird), ← (theoretische Bucher)

23 / 51

Zusammengesetzte Datentypen: Strukturen

Definition 4.9Eine Variable V heißt Struktur (Record) mit Attributen ATTR1, . . . ,ATTRn (n ∈ N)falls V als Ansammlung von Variablen mit den Namen ATTR1[V ], . . . ,ATTRn[V ]aufgefasst werden kann. Die vorigen Variablen heißen Attribute von V .

BemerkungIn modernen Programmiersprachen sind die BezeichnungenV .ATTR1, . . . ,V .ATTRn typisch.

24 / 51

Strukturen: Beispiel

Wir fuhren eine Variable p ein, die einen Punkt auf der Ebene darstellt, der durch diex- und y -Koordinaten sowie durch seine Farbe gegeben wird.

Pseudocode 4.1 Beispiel zu Strukturen

require: p - Variable mit numerischen Attributen x[p], y [p] und Farbe[p] ∈{Weiss, Schwarz}.

1: x[p] := 202: y [p] := 73: Farbe[p] := Weiss4: temp := x[p]5: x[p] := −y [p]6: y [p] := temp

25 / 51

Zusammengesetzte Datentypen: Array (= Feld ≈ Liste)

Definition 4.10Ein Array (Feld, Liste) A ist ein nummerierte Ansammlung von n Variablen, die mandurch A[1],. . . ,A[n] bezeichnet. Dabei heißt n die Lange von A und A[1], . . . ,A[n] dieKomponenten von A. Wir werden die Lange durch das Attribut Lange[A] fuhren.

Beispiel 4.11

1: A := [1, 3, 5, 7, 6]2: A[4] := A[1] + A[2] + A[4]3: A[A[2]] := A[5]− A[1]

BemerkungLeere Arrays (Bezeichnung: []) sind moglich.

BemerkungA[i . . j] bezeichnet Teilarray von A mit Komponenenten A[i ], . . . ,A[j]. Fur i > j giltA[i . . j] = [].

26 / 51

Benutzung von zusammengesetzten Datentypen: Beispiel

I Liste der Hochschulen – ist Array mit Komponenten vom Typ HochschuleI Hochschule – Struktur mit Attributen:

I Name – ZeichenketteI Standort – ZeichenketteI Art der Hochschule – (Fachhochschule/Universitat)I Wann gegrundet – DatumI Die Mitarbeiter – Array mit Komponenten vom Typ MitarbeiterI Die Studierenden – Array mit Komponenten vom Typ Studierender

I Studierender – Struktur mit Attributen:I Name – ZeichenketteI Geburtsdatum – DatumI Matrikelnummer – ???I Aktuelles Semester – ganze ZahlI usw.

I Mitarbeiter – Struktur mit Attributen:I NameI GeburtsdatumI Art des VertragesI usw.

27 / 51

Prozedurale Programmierung

Definition 4.12Prozedurale Programmierung ist ein Programmierparadigma, in welchem einProgramm als Ansamlung von Prozeduren dargestellt wird (jede Prozedur ist furLosung eines Teilproblems zustandig).

28 / 51

Prozedur (≈ Unterprogramm ≈ Routine ≈ Funktion)

Pseudocode 4.2 m = holderMittel(a, b, p)

require: a, b, p sind reelle Variablen mit a, b, p > 0ensure m ist das Holdermittel von a, b bzgl. p

1: m := 12

(ap + bp)

2: m := m1/p

I holderMittel - Name der Funktion/Prozedur

I a, b, p sind formale Eingabeparameter der Funktion holderMittel

I m ist der Ausgabeparameter der Funktion holderMittel

I Die Zeile m = holderMittel(a, b, p) heißt das Interface der FunktionholderMittel

I Hilfsvariablen, die innerhalb einer Funktion eingefuhrt und benutzt werden, heißenlokale Variablen dieser Funktion.

29 / 51

Formale und tatsachliche Parameter

Pseudocode 4.3 q = quadratischesMittel(x , y)

require: x , y > 0ensure q ist das quadratische Mittel von x und y

1: q := holderMittel(x , y , 2)

I Die Funktion holderMittel wird wahrend der Ausfuhrung der FunktionquadratischesMittel aufgerufen. Die Parameter x , y , 2, fur welche dieFunktion holderMittel benutzt wird, heißen tatsachliche Parameter beimAufruf von holderMittel

30 / 51

Parameterubergabe

Pseudocode 4.4 vertauschen(a, b)

require: a, b – Referenzen auf reelle Variablen, temp ist eine reelle Variable innerhalbder Prozedur umtausch

ensure Die Werte von a und b werden vertauscht.1: temp := a2: a := b3: b := temp

Pseudocode 4.5

1: x := 3, y := 5, z := 72: vertauschen(x , y)3: vertauschen(y , z)

I In diesem Beisipel mochten wir, dass sich die Werte von x und y nach derAusfuhrung der Prozedur vertauschen verandern. Deswegen definieren wirParameter a und b von vertauschen als Referenzen. Wahrend der Ausfurhungvon vertauschen sind die Parameter a bzw. b “Zweitnamen” fur x bzw. y .Solche Parameterubergabe heißt call by reference (Ubergabe durch die Referenz).Die Parameterubergabe in holderMittel ist call by value (Uberegabe durchden Wert).

I temp ist lokaler Parameter der Funktion vertauschen

31 / 51

Vereinbarung zur Parameterubergabe

I Vereinbarung: im Folgenden werden nicht zusammengesetzte Variablen durch denWert ubergeben und zusammengesetzte (Arrays oder Variablen, die Attributenbesitzten) durch die Referenz.

32 / 51

Beispiel zu geschachtelten Aufrufen

Funktion A wird aufgerufen (Parameter der Funktion werden generiert)In der Zeile X der Funktion A wird die Funktion C aufgerufen

Die Funktion C startet; ihre Parameter werden generiertIn der Zeile Y der Funktion C wird die Funktion D aufgerufen

Die Funktion D startet; ihre Parameter werden generiertDie Funktion D terminiert; ihre Parameter werden geloscht

Die Funktion C setzt von der Zeile Y fortDie Funktion C terminiert; ihre Parameter werden geloscht

Die Funktion A wird von der Zeile X fortgesetztFunktion A terminiert; ihre Parameter werden geloscht

33 / 51

Strukturierte Programmierung

Definition 4.13Strukturierte Programmierung ist ein Programmierparadigma, in welchem einProgramm folgende Kontrollstrukturen benutzt:

I Auswahl (= Verzweigung)

I Wiederholung (= Schleifen = Iterative Kontrollstrukturen)

34 / 51

Kontrollstrukturen: Verzweigung (= Falls-Anweisungen)

Pseudocode 4.6 m = abstimmung(a, b, c)

require: drei Personen stimmen ab, um eine Entscheidung zu treffen; a, b, c sind boo-lesche Variablen, welche darstellen, ob enstprechende Person dafur oder dagegenist.

ensure m ist das Resultat der Abstimmung; m = Wahr, falls die Mehrheit dafur ist,und m = Falsch sonst.

1: if a und b oder a und c oder b und c :2: m := Wahr3: else:4: m := Falsch5: end

I Der Sonst-Block ist nicht obligatorisch.

35 / 51

Kontrollstrukturen: geschachtelte Falls-Anweisungen

Pseudocode 4.7 p = relativePosition(x , a, b)

ensure x , a, b sind reelle Werte und a ≤ b.require: p := −1 falls x links von dem Segment [a, b] liegt, p = 1 falls x rechts von

dem Segment [a, b] liegt und p = 0 falls x ∈ [a, b]1: if x < a :2: p := −13: else if x ≤ b :4: p := 05: else:6: p := 17: end

36 / 51

Solange-Schleife

Pseudocode 4.8 s = Summe(A)

require: A ist Array mit numerischen Wertenensure s ist die Summe aller Komponenten von A

1: i := 1, s := 02: while i ≤ Lange[A] :3: s := s + A[i ]4: i := i + 15: end

37 / 51

Fur-Schleife

Pseudocode 4.9 s = Summe(A)

1: s := 02: for i = 1, . . . ,Lange[A] :3: s := s + A[i ]4: end

38 / 51

Weitere Schleifen und Kontrollstrukturen

I Repeat-Until, Do-While, Loop...

I Goto

I return

39 / 51

Rekursion

Definition 4.14Rekursion ist ein oder mehrere Aufrufe der Prozedur innerhalb von sich selbst.

40 / 51

Rekursion: Einfachstes Beispiel - Fakultat ausrechnen

Pseudocode 4.10 f = Fakultat(n)

require: n ∈ N0.ensure f = n!.

1: if n ≤ 1 :2: f := 13: else:4: f := n · Fakultat(n − 1)5: end

I Entartete Falle werden abgedeckt.

I Mit jedem weiteren rekursiven Aufruf wird der Eingabeparameter einfacher.

I Wie kann man zeigen, dass die Funktion Fakultat terminiert?

41 / 51

Ausfuhrung von Fakultat

Pseudocode 4.11 Verwendung von Fakultat

1: Fakultat(3) in die Standartausgabe schreiben

I Rekursionsbaum fur die Ausfuhrung von Fakultat(3):

I Fakultat(3) −→ Fakultat(2) −→ Fakultat(1)

42 / 51

Details der Ausfuhrung von Fakultat(3)

I Fakultat startet (erste Ausfuhrung). Parameter n, f werden generiert; n := 3.

I Fakultat startet (zweite Ausfuhrung). (Parameter n, f werden generiert; n := 2)

I Fakultat startet (dritte Ausfuhrung) Parameter n, f werden generiert; n := 1

I Fakultat terminiert (dritte Ausfuhrung). Wert 1 wird zuruckgegeben. Parametern, f werden geloscht.

I Fakultat terminiert (zweite Ausfuhrung). Wert 2 wird zuruckgegeben.Parameter n, f werden geloscht.

I Fakultat terminiert (erste Ausfuhrung). Wert 6 wird zuruckgegeben. Parametern, f werden geloscht.

43 / 51

Bemerkungen zur rekursiven Version der Fakultat

I Fur die Ausfurhung von Fakultat(n) brauchen wir O(n) Einheiten im Speicher(ohne es direkt im Programm zu sehen)

44 / 51

Rekursion: Praktisches Beispiel - schnelles Potenzieren; nichtrekursiveVersion

Pseudocode 4.12 p = PotenzNichtRekursiv(a, n)

require: a > 0, n ∈ N0

ensure p = an

1: p := 12: while n > 0 :3: p := p · a4: n := n − 15: end

I Anzahl der Arithmetischen Operationen Θ(nk ) mit k =??.

45 / 51

Rekursion: Praktisches Beispiel - schnelles Potenzieren

Pseudocode 4.13 p = Potenz(a, n)

require: a > 0, n ∈ N0.ensure p = an.

1: if n = 0 :2: p := 13: else if n ist gerade :4: temp := Potenz(a, n/2)5: p := temp · temp6: else:7: temp := Potenz(a, bn/2c)8: p := a · temp · temp9: end

I Schneller als direkte iterative Losung (leichtes Beispiel: n ist Potenz von 2; aberauch fur andere Instanzen)

I Iterative variante ist moglich.

I Rekursive Variante ist naheliegend und einfach.

46 / 51

Rekursion: großter gemeinsamer Teiler

Pseudocode 4.14 g = ggT(a, b)

require: a, b ∈ Z.ensure g ist der großte gemeinsamer Teiler von a, b.

1: a := |a|, b := |b|2: if a > b :3: vertauschen(a, b)4: end5: if a = 0 :6: g := b7: else:8: g := ggT(a, b − a)9: end

I Sehr ineffizient.

I Wir setzen ggT(0, 0) = 0.

47 / 51

Rekursion: Fibonacci-Zahlen

Definition 4.15Die Folge der Fibonacci-Zahlen: F0 = 0, F1 = 1, und Fi = Fi−1 + Fi−2 fur i ≥ 2 miti ∈ N.

Pseudocode 4.15 f = fibonacci(i)

require: i ∈ N0.ensure f ist die i-te Fibonacci Zahl.

1: if i ≤ 1 :2: f := i3: else:4: f := fibonacci(i − 1) + fibonacci(i − 2)5: end

I Rekursionsbaum fur der Ausfuhrung von fibonacci(4) enthalt mehrfache Aufrufevon fibonacci(2), fibonacci(1) und fibonacci(0).

I Daher: nicht effizient.

48 / 51

Rekursion: die Turme von Hanoi

I Gegeben sind drei Stabe (S= Start, Z = Ziel, H - Hilfstab).

I Auf dem Stab S befinden sich n ∈ N gelochte Scheiben verschiedener Große dievon oben nach unten nach der Große aufsteigend sortiert sind.

I Die obersten Scheiben konnen von einem Stab verlegt werden (falls dabei dieScheiben auf jedem Stab sortiert bleiben)

I Ziel: Alle Stabe von S nach Z zu verlegen.

49 / 51

Rekursive losung fur “Turme von Hanoi”

Pseudocode 4.16 LoseTHanoi(n, S ,Z ,H)

require: n ∈ N, S,Z ,H haben verschiedene Werte.ensure Die Losung der Aufgabe “Turme von Hanoi” wird ausgegeben.

1: if n = 1 :2: Ausgeben: Verlege die Scheibe der Große n von S nach Z3: else:4: LoseTHanoi(n − 1,S ,H,Z)5: Ausgeben: Verlege die Scheibe der Große n von S nach Z6: LoseTHanoi(n − 1,H,Z , S)7: end

50 / 51

Weitere Bemerkungen zur Rekursion

I Indirekte rekursive Aufrufe sind moglich (z.B:Funktion1 −→ Funktion2 −→ Funktion3 −→ Funktion1).

I Ausgangsbedingung (die den entarteten Fall behandelt) ist entscheidend fur dieTerminierung.

I Rekursionstiefe ist die maximale Anzahl der geschachtelten rekursiven Aufrufe.

I Rekursion ist eine Alternative zu den Schleifen.

I Rechenprobleme, die man mit Arrays und iterativen Strukturen, lost, kann manmit Rekursion ohne Arrays und ohne iterative Strukturen losen (die Effizienz kannein Problem sein).

I Manche rekursive Algorithmen haben naheliegende nichtrekursive Analoga (z.B.:schnelles Potenzieren)

I Manche Compiler konnen erkennen, wo die Rekursion durch Iteration ersetztwerden kann, und generieren dabei entsprechenden iterativen ausfuhrbaren Code.

I Rekursion ist ein naturliches Mittel fur manche wichtige Klassen der Probleme(Formale Sprachen, Lexikalische Scanner, Suchalgorithmen auf Graphen)

51 / 51