Informatik Vorkurs – Sommersemester 2015
Vom Algorithmus zum Programm
Werner Struckmann / Marvin Priedigkeit, Stephan Mielke
31. März – 10. April 2015
Kann ein Computer rechnen?
Ist das Programm korrekt?
Wiederholung: Algorithmusbegriff
Kann ein Computer rechnen?
Ist das Programm korrekt?
Wiederholung: Algorithmusbegriff
Vom Algorithmus zum Programm
1. Was ist ein Algorithmus?
2. Was ist ein Programm?
3. Wie wird ein Algorithmus aufgeschrieben?
4. Mit welchem Aufwand löst der Algorithmus das Problem?
5. Löst der Algorithmus das Problem?
6. Gibt es einen Algorithmus für das Problem?
7. Vom kleinen zum großen Programm
8. Weitere Aspekte
Vom Algorithmus zum Programm
Kann ein Computer rechnen?
Ist das Programm korrekt?
Wiederholung: Algorithmusbegriff
Kann ein Computer rechnen? Ein Java-Beispiel
public static void main(String[] args) {
System.out.println(1*1);
System.out.println(12*12);
System.out.println(123*123);
System.out.println(1234*1234);
System.out.println(12345*12345);
System.out.println(123456*123456);
}
Ausgabe:
1
144
15129
1522756
152399025
31. März – 10. April 2015 | Werner Struckmann | Seite 3 / 35
Vom Algorithmus zum Programm
Kann ein Computer rechnen?
Ist das Programm korrekt?
Wiederholung: Algorithmusbegriff
Vom Algorithmus zum Programm
Kann ein Computer rechnen? Ein Java-Beispiel
public static void main(String[] args) {
System.out.println(1*1);
System.out.println(12*12);
System.out.println(123*123);
System.out.println(1234*1234);
System.out.println(12345*12345);
System.out.println(123456*123456);
}
Ausgabe:
1
144
15129
1522756
152399025
-1938485248
Diese Ausgabe ist offensichtlich falsch!
31. März – 10. April 2015 | Werner Struckmann | Seite 3 / 35
Kann ein Computer rechnen?
Ist das Programm korrekt?
Wiederholung: Algorithmusbegriff
Kann ein Computer rechnen? Ein zweites Java-Beispiel
public static void main(String[] args) {
int z = 256*256*256*128+2147483647;
System.out.println(z*z);
}
31. März – 10. April 2015 | Werner Struckmann | Seite 4 / 35
Vom Algorithmus zum Programm
Kann ein Computer rechnen?
Ist das Programm korrekt?
Wiederholung: Algorithmusbegriff
Kann ein Computer rechnen? Ein zweites Java-Beispiel
public static void main(String[] args) {
int z = 256*256*256*128+2147483647;
System.out.println(z*z);
}
Ausgabe:
1
Hat er sich schon wieder verrechnet?
31. März – 10. April 2015 | Werner Struckmann | Seite 4 / 35
Vom Algorithmus zum Programm
Kann ein Computer rechnen?
Ist das Programm korrekt?
Wiederholung: Algorithmusbegriff
Kann ein Computer rechnen? Ein drittes Java-Beispiel
double a = 1.0/3.0;
double b = 10.0 + a - 10.0, c;
if (a == b)
c = 0;
else
c = 1/(a-b);
System.out.printf("%20.5f%n",c);
31. März – 10. April 2015 | Werner Struckmann | Seite 5 / 35
Vom Algorithmus zum Programm
Kann ein Computer rechnen?
Ist das Programm korrekt?
Wiederholung: Algorithmusbegriff
Vom Algorithmus zum Programm
Kann ein Computer rechnen? Ein drittes Java-Beispiel
double a = 1.0/3.0;
double b = 10.0 + a - 10.0, c;
if (a == b)
c = 0;
else
c = 1/(a-b);
System.out.printf("%20.5f%n",c);
Ausgabe: -1637672591771089.50000
- 1 Billiarde 637 Billionen 672 Milliarden 591 Millionen 771 Tausend und 89,5
korrekter Wert:
0
31. März – 10. April 2015 | Werner Struckmann | Seite 5 / 35
Kann ein Computer rechnen?
Ist das Programm korrekt?
Wiederholung: Algorithmusbegriff
Vom Algorithmus zum Programm
Kann ein Computer rechnen?
Warum sich der Computer hier dreimal verrechnet hat,
werden wir in Programmieren 1 lernen.
31. März – 10. April 2015 | Werner Struckmann | Seite 6 / 35
Kann ein Computer rechnen?
Ist das Programm korrekt?
Wiederholung: Algorithmusbegriff
Kann ein Computer rechnen?
Ist das Programm korrekt?
Wiederholung: Algorithmusbegriff
Vom Algorithmus zum Programm
1. Was ist ein Algorithmus?
2. Was ist ein Programm?
3. Wie wird ein Algorithmus aufgeschrieben?
4. Mit welchem Aufwand löst der Algorithmus das Problem?
5. Löst der Algorithmus das Problem?
6. Gibt es einen Algorithmus für das Problem?
7. Vom kleinen zum großen Programm
8. Weitere Aspekte
Vom Algorithmus zum Programm
Kann ein Computer rechnen?
Ist das Programm korrekt?
Wiederholung: Algorithmusbegriff
Vom Algorithmus zum Programm
Ist das Programm korrekt?
In Jahre 1999 wurde durch die Fehlfunktion eines Seitenairbags ein Baby
getötet.
Die Untersuchungen ergaben einen Softwarefehler:
Die Ausführungsreihenfolge zweier Anweisungen war vertauscht worden.
Der Fehler trat nur in der Software eines speziellen Fahrzeugmodells auf.
Es wurde vergessen, diese spezielle Software zu testen.
31. März – 10. April 2015 | Werner Struckmann | Seite 8 / 35
Kann ein Computer rechnen?
Ist das Programm korrekt?
Wiederholung: Algorithmusbegriff
Ist das Programm korrekt?
Richtige Reihenfolge:
airbag = ein;
if (kindersitz == belegt) {
airbag = aus;
}
Falsche Reihenfolge:
if (kindersitz == belegt) {
airbag = aus;
}
airbag = ein;
31. März – 10. April 2015 | Werner Struckmann | Seite 9 / 35
Vom Algorithmus zum Programm
Kann ein Computer rechnen?
Ist das Programm korrekt?
Wiederholung: Algorithmusbegriff
Kann ein Computer rechnen?
Ist das Programm korrekt?
Wiederholung: Algorithmusbegriff
Vom Algorithmus zum Programm
1. Was ist ein Algorithmus?
2. Was ist ein Programm?
3. Wie wird ein Algorithmus aufgeschrieben?
4. Mit welchem Aufwand löst der Algorithmus das Problem?
5. Löst der Algorithmus das Problem?
6. Gibt es einen Algorithmus für das Problem?
7. Vom kleinen zum großen Programm
8. Weitere Aspekte
Vom Algorithmus zum Programm
Kann ein Computer rechnen?
Ist das Programm korrekt?
Wiederholung: Algorithmusbegriff
Vom Algorithmus zum Programm
Der intuitive Algorithmusbegriff
Gegeben sei ein „Problem“. Eine Handlungsvorschrift, deren mechanisches
Befolgen ohne Verständnis des Problems zur Lösung des Problems führt, wird
„Algorithmus“ genannt.
Kann ein Computer rechnen?
Ist das Programm korrekt?
Wiederholung: Algorithmusbegriff
Vom Algorithmus zum Programm
Der intuitive Algorithmusbegriff
Gegeben sei ein „Problem“. Eine Handlungsvorschrift, deren mechanisches
Befolgen ohne Verständnis des Problems zur Lösung des Problems führt, wird
„Algorithmus“ genannt.
Etwas präziser: Ein Algorithmus ist eine wohldefinierte „Rechenvorschrift“, die eine
(evtl. leere) Menge von Größen als Eingabe verwendet und eine Menge von
Größen als Ausgabe erzeugt. Ein Algorithmus ist also eine Abfolge von Schritten,
die die (evtl. leere) Eingabe in eine Ausgabe umwandelt.
Kann ein Computer rechnen?
Ist das Programm korrekt?
Wiederholung: Algorithmusbegriff
Vom Algorithmus zum Programm
Der intuitive Algorithmusbegriff
Gegeben sei ein „Problem“. Eine Handlungsvorschrift, deren mechanisches
Befolgen ohne Verständnis des Problems zur Lösung des Problems führt, wird
„Algorithmus“ genannt.
Etwas präziser: Ein Algorithmus ist eine wohldefinierte „Rechenvorschrift“, die eine
(evtl. leere) Menge von Größen als Eingabe verwendet und eine Menge von
Größen als Ausgabe erzeugt. Ein Algorithmus ist also eine Abfolge von Schritten,
die die (evtl. leere) Eingabe in eine Ausgabe umwandelt.
Der Algorithmus muss durch einen endlichen Text in einer wohldefinierten
Sprache beschrieben sein.
Die Objekte der Aktionen müssen klar sein.
Die Operationen müssen mechanisch ausführbar sein.
Die Reihenfolge der Operationen muss evtl. feststehen.
Kann ein Computer rechnen?
Ist das Programm korrekt?
Wiederholung: Algorithmusbegriff
Vom Algorithmus zum Programm
Der intuitive Algorithmusbegriff
Gegeben sei ein „Problem“. Eine Handlungsvorschrift, deren mechanisches
Befolgen ohne Verständnis des Problems zur Lösung des Problems führt, wird
„Algorithmus“ genannt.
Etwas präziser: Ein Algorithmus ist eine wohldefinierte „Rechenvorschrift“, die eine
(evtl. leere) Menge von Größen als Eingabe verwendet und eine Menge von
Größen als Ausgabe erzeugt. Ein Algorithmus ist also eine Abfolge von Schritten,
die die (evtl. leere) Eingabe in eine Ausgabe umwandelt.
Der Algorithmus muss durch einen endlichen Text in einer wohldefinierten
Sprache beschrieben sein.
Die Objekte der Aktionen müssen klar sein.
Die Operationen müssen mechanisch ausführbar sein.
Die Reihenfolge der Operationen muss evtl. feststehen.
Ein Problem, für dessen Lösung ein Algorithmus existiert, heißt berechenbar. In
der Definition wird nicht gefordert, dass die Abfolge der Rechenschritte stets
terminiert (Halteproblem).
Kann ein Computer rechnen?
Ist das Programm korrekt?
Wiederholung: Algorithmusbegriff
Vom Algorithmus zum Programm
Beispiele
Zerlegung handwerklicher Arbeiten in einzelne Schritte,
Kochrezepte,
Verfahren zur schriftlichen Multiplikation,
Algorithmus zur Bestimmung des größten gemeinsamen Teilers zweier
natürlicher Zahlen.
Zwei dieser Beispiele sehen wir uns jetzt an.
31. März – 10. April 2015 | Werner Struckmann | Seite 12 / 35
Kann ein Computer rechnen?
Ist das Programm korrekt?
Beispiel: Multiplikation zweier Zahlen
12 · 23 = ?
Wiederholung: Algorithmusbegriff
Vom Algorithmus zum Programm
Kann ein Computer rechnen?
Ist das Programm korrekt?
Beispiel: Multiplikation zweier Zahlen
12 · 23 = ?
2
7
6
Wiederholung: Algorithmusbegriff
Vom Algorithmus zum Programm
Kann ein Computer rechnen?
Ist das Programm korrekt?
Wiederholung: Algorithmusbegriff
Vom Algorithmus zum Programm
Beispiel: Multiplikation zweier Zahlen
12 · 23 = ?
2
12
6
3
1
7
6
23
46
92
184
276
*
*
Kann ein Computer rechnen?
Ist das Programm korrekt?
Wiederholung: Algorithmusbegriff
Vom Algorithmus zum Programm
Beispiel: Multiplikation zweier Zahlen
12 · 23 = ?
2
12
6
3
1
7
1
6
23
46
92
184
276
2
·
2
2
*
*
2
4
3
7
3
6
6
Kann ein Computer rechnen?
Ist das Programm korrekt?
Wiederholung: Algorithmusbegriff
Vom Algorithmus zum Programm
Beispiel: Multiplikation zweier Zahlen
12 · 23 = ?
2
12
6
3
1
7
1
6
23
46
92
184
276
2
·
2
2
*
*
2
4
3
7
3
6
6
12·23 = (1·10+2)·(2·10+3) = 1·2·100+(1·3+2·2)·10+2·3 = 2·100+7·10+6 = 276
Kann ein Computer rechnen?
Ist das Programm korrekt?
Wiederholung: Algorithmusbegriff
Beispiel: Größter gemeinsamer Teiler
Es sollen zwei Brüche addiert werden:
1 23
13 23
36
4·9
9
+
=
+
=
=
=
4 52
52 52
52
4 · 13
13
Bestimme den Hauptnenner.
Erweitere die Brüche.
Addiere die Zähler.
Bestimme den ggT von Zähler und Nenner.
Kürze den Bruch.
Wie berechnet man den ggT?
31. März – 10. April 2015 | Werner Struckmann | Seite 14 / 35
Vom Algorithmus zum Programm
Kann ein Computer rechnen?
Ist das Programm korrekt?
Wiederholung: Algorithmusbegriff
1. Algorithmus: Teilermengen
a = 52, b = 36:
Ta = T52 = {1, 2, 4, 13, 26, 52}
Tb = T36 = {1, 2, 3, 4, 6, 12, 18, 36}
Ta ∩ Tb = T52 ∩ T36 = {1, 2, 4}
ggT(52, 36) = max(Ta ∩ Tb ) = max{1, 2, 4} = 4
Bestimme die Teilermengen Ta und Tb .
Bestimme die Durchschnittsmenge Ta ∩ Tb .
Bestimme das Maximum von Ta ∩ Tb .
31. März – 10. April 2015 | Werner Struckmann | Seite 15 / 35
Vom Algorithmus zum Programm
Kann ein Computer rechnen?
Ist das Programm korrekt?
Wiederholung: Algorithmusbegriff
Vom Algorithmus zum Programm
2. Algorithmus: Primfaktorzerlegung
a = 52, b = 36:
2
0
0
0
0
1
2
0
0
0
0
0
52
36
=
=
2 · 3 · 5 · 7 · 11 · 13
2
2
0
0
0
0
2 · 3 · 5 · 7 · 11 · 13
ggT(52, 36)
=
2 · 3 · 5 · 7 · 11 · 13
= 4
Bestimme die Primfaktorzerlegungen von a und b .
Bestimme die Primfaktorzerlegung des ggTs:
Bilde dazu das jeweilige Minimum der Exponenten von a und b.
31. März – 10. April 2015 | Werner Struckmann | Seite 16 / 35
Kann ein Computer rechnen?
Ist das Programm korrekt?
Wiederholung: Algorithmusbegriff
3. Algorithmus: Verfahren von Euklid (ca. 300 v. Chr.)
a = 52, b = 36:
Berechne r = a mod b.
Setze a = b und b = r.
Wiederhole diese Schritte bis b = 0 ist.
a ist das Ergebnis.
r
16
4
0
a
52
36
16
4
b
36
16
4
0
31. März – 10. April 2015 | Werner Struckmann | Seite 17 / 35
Vom Algorithmus zum Programm
Kann ein Computer rechnen?
Ist das Programm korrekt?
Wiederholung: Algorithmusbegriff
Fragestellungen für Algorithmen: Korrektheit und Komplexität
Partielle Korrektheit:
Falls der Algorithmus terminiert wird die Spezifikation erfüllt.
Totale Korrektheit:
Der Algorithmus terminiert und erfüllt die Spezifikation.
Komplexität:
Speicherplatz des Algorithmus
Laufzeit des Algorithmus
31. März – 10. April 2015 | Werner Struckmann | Seite 18 / 35
Vom Algorithmus zum Programm
Kann ein Computer rechnen?
Ist das Programm korrekt?
Wiederholung: Algorithmusbegriff
Vom Algorithmus zum Programm
Programm und Programmiersprache
Ein Programm ist die Formulierung eines Algorithmus und seiner Datenbereiche in
einer Programmiersprache.
Eine Programmiersprache erlaubt es, Algorithmen präzise zu beschreiben.
Insbesondere legt eine Programmiersprache
die elementaren Operationen,
die Möglichkeiten zu ihrer Kombination und
die zulässigen Datenbereiche
eindeutig fest.
Unter „programmieren“ versteht man den Vorgang des Erstellens eines
Programms. Die Programmierausbildung der ersten Semester erfolgt in der
Sprache Java. Später werden weitere Sprachen gelehrt.
31. März – 10. April 2015 | Werner Struckmann | Seite 19 / 35
Kann ein Computer rechnen?
Ist das Programm korrekt?
Wiederholung: Algorithmusbegriff
Vom Algorithmus zum Programm
Beispiel: Der euklidische Algorithmus in fünf Programmiersprachen
Java (objektorientierte Sprache)
s t a t i c i n t ggT ( i n t a , i n t b ) {
int r ;
while ( b != 0 ) {
r = a % b;
a = b;
b = r;
}
return a ;
}
Kann ein Computer rechnen?
Ist das Programm korrekt?
Wiederholung: Algorithmusbegriff
Vom Algorithmus zum Programm
Beispiel: Der euklidische Algorithmus in fünf Programmiersprachen
Java (objektorientierte Sprache)
s t a t i c i n t ggT ( i n t a , i n t b ) {
int r ;
while ( b != 0 ) {
r = a % b;
a = b;
b = r;
}
return a ;
}
Prolog (logische Sprache)
g g t ( A, 0 , A ) .
g g t ( A , B , Z ) : − U i s A mod B , g g t ( B , U, Z ) .
Kann ein Computer rechnen?
Ist das Programm korrekt?
Wiederholung: Algorithmusbegriff
Vom Algorithmus zum Programm
Beispiel: Der euklidische Algorithmus in fünf Programmiersprachen
Java (objektorientierte Sprache)
s t a t i c i n t ggT ( i n t a , i n t b ) {
int r ;
while ( b != 0 ) {
r = a % b;
a = b;
b = r;
}
return a ;
}
Prolog (logische Sprache)
g g t ( A, 0 , A ) .
g g t ( A , B , Z ) : − U i s A mod B , g g t ( B , U, Z ) .
Haskell (funktionale Sprache)
g g t : : I n t e g e r −> I n t e g e r −> I n t e g e r
g g t a b | b == 0
= a
| otherwise = g g t b ( a ‘mod‘ b )
Kann ein Computer rechnen?
Ist das Programm korrekt?
Wiederholung: Algorithmusbegriff
Vom Algorithmus zum Programm
Beispiel: Der euklidische Algorithmus in fünf Programmiersprachen
Java (objektorientierte Sprache)
C-Shell (Skriptsprache)
s t a t i c i n t ggT ( i n t a , i n t b ) {
int r ;
while ( b != 0 ) {
r = a % b;
a = b;
b = r;
}
return a ;
}
set a = . . . ; set b = . . .
while ( $b != 0 )
@ r = $a % $b
s e t a = $b
set b = $r
end
echo $a
Prolog (logische Sprache)
g g t ( A, 0 , A ) .
g g t ( A , B , Z ) : − U i s A mod B , g g t ( B , U, Z ) .
Haskell (funktionale Sprache)
g g t : : I n t e g e r −> I n t e g e r −> I n t e g e r
g g t a b | b == 0
= a
| otherwise = g g t b ( a ‘mod‘ b )
Kann ein Computer rechnen?
Ist das Programm korrekt?
Wiederholung: Algorithmusbegriff
Vom Algorithmus zum Programm
Beispiel: Der euklidische Algorithmus in fünf Programmiersprachen
Java (objektorientierte Sprache)
C-Shell (Skriptsprache)
s t a t i c i n t ggT ( i n t a , i n t b ) {
int r ;
while ( b != 0 ) {
r = a % b;
a = b;
b = r;
}
return a ;
}
set a = . . . ; set b = . . .
while ( $b != 0 )
@ r = $a % $b
s e t a = $b
set b = $r
end
echo $a
Prolog (logische Sprache)
g g t ( A, 0 , A ) .
g g t ( A , B , Z ) : − U i s A mod B , g g t ( B , U, Z ) .
Haskell (funktionale Sprache)
g g t : : I n t e g e r −> I n t e g e r −> I n t e g e r
g g t a b | b == 0
= a
| otherwise = g g t b ( a ‘mod‘ b )
C (imperative Sprache)
i n t ggt ( i n t a , i n t b ) {
int r ;
while ( b != 0 ) {
r = a % b;
a = b;
b = r;
}
return a ;
}
Kann ein Computer rechnen?
Ist das Programm korrekt?
Wiederholung: Algorithmusbegriff
Vom Algorithmus zum Programm
Beispiel: Lineare diophantische Gleichungen
Definition
Eine lineare diophantische Gleichung mit zwei Unbekannten x und y ist eine
Gleichung der Form
ax + by = c
(*)
für gegebene ganze Zahlen a, b, c. Gesucht werden ganze Zahlen x und y, die die
Gleichung erfüllen.
Kann ein Computer rechnen?
Ist das Programm korrekt?
Wiederholung: Algorithmusbegriff
Vom Algorithmus zum Programm
Beispiel: Lineare diophantische Gleichungen
Definition
Eine lineare diophantische Gleichung mit zwei Unbekannten x und y ist eine
Gleichung der Form
ax + by = c
(*)
für gegebene ganze Zahlen a, b, c. Gesucht werden ganze Zahlen x und y, die die
Gleichung erfüllen.
Satz
Die Gleichung (*) besitzt genau dann eine Lösung, wenn ggT(a, b) | c gilt.
Kann ein Computer rechnen?
Ist das Programm korrekt?
Wiederholung: Algorithmusbegriff
Vom Algorithmus zum Programm
Beispiel: Lineare diophantische Gleichungen
Definition
Eine lineare diophantische Gleichung mit zwei Unbekannten x und y ist eine
Gleichung der Form
ax + by = c
(*)
für gegebene ganze Zahlen a, b, c. Gesucht werden ganze Zahlen x und y, die die
Gleichung erfüllen.
Satz
Die Gleichung (*) besitzt genau dann eine Lösung, wenn ggT(a, b) | c gilt.
Beispiel
Zum Beispiel besitzt die Gleichung 36x + 52y = 24 eine ganzzahlige Lösung, weil
ggT(36, 52) = 4 ein Teiler von 24 ist: 36 · 18 − 52 · 12 = 24. Mithilfe eines
erweiterten euklidischen Algorithmus können Lösungen von linearen
diophantischen Gleichungen bestimmt werden, falls sie existieren.
Kann ein Computer rechnen?
Ist das Programm korrekt?
Wiederholung: Algorithmusbegriff
Vom Algorithmus zum Programm
Beispiel: Allgemeine diophantische Gleichungen
Definition
Eine allgemeine diophantische Gleichung mit den Unbekannten x1 , x2 , . . . , xn ist
eine Gleichung der Form
p(x1 , x2 , . . . , xn ) = 0,
wobei p ein ganzzahliges Polynom mit n Variablen ist.
Kann ein Computer rechnen?
Ist das Programm korrekt?
Wiederholung: Algorithmusbegriff
Vom Algorithmus zum Programm
Beispiel: Allgemeine diophantische Gleichungen
Definition
Eine allgemeine diophantische Gleichung mit den Unbekannten x1 , x2 , . . . , xn ist
eine Gleichung der Form
p(x1 , x2 , . . . , xn ) = 0,
wobei p ein ganzzahliges Polynom mit n Variablen ist.
Problem
Gibt es einen Algorithmus, der entscheiden kann, ob eine allgemeine
diophantische Gleichung ganzzahlige Lösungen besitzt? Dies ist das berühmte
zehnte Hilbertsche Problem aus dem Jahr 1900.
Kann ein Computer rechnen?
Ist das Programm korrekt?
Wiederholung: Algorithmusbegriff
Vom Algorithmus zum Programm
Beispiel: Allgemeine diophantische Gleichungen
Definition
Eine allgemeine diophantische Gleichung mit den Unbekannten x1 , x2 , . . . , xn ist
eine Gleichung der Form
p(x1 , x2 , . . . , xn ) = 0,
wobei p ein ganzzahliges Polynom mit n Variablen ist.
Problem
Gibt es einen Algorithmus, der entscheiden kann, ob eine allgemeine
diophantische Gleichung ganzzahlige Lösungen besitzt? Dies ist das berühmte
zehnte Hilbertsche Problem aus dem Jahr 1900.
Fakt
Solch einen Algorithmus gibt es nicht. Dies wurde von Yuri Matijasevič im Jahre
1970 bewiesen.
Kann ein Computer rechnen?
Ist das Programm korrekt?
Wiederholung: Algorithmusbegriff
Vom Algorithmus zum Programm
Beispiel: Allgemeine diophantische Gleichungen
Definition
Eine allgemeine diophantische Gleichung mit den Unbekannten x1 , x2 , . . . , xn ist
eine Gleichung der Form
p(x1 , x2 , . . . , xn ) = 0,
wobei p ein ganzzahliges Polynom mit n Variablen ist.
Problem
Gibt es einen Algorithmus, der entscheiden kann, ob eine allgemeine
diophantische Gleichung ganzzahlige Lösungen besitzt? Dies ist das berühmte
zehnte Hilbertsche Problem aus dem Jahr 1900.
Fakt
Solch einen Algorithmus gibt es nicht. Dies wurde von Yuri Matijasevič im Jahre
1970 bewiesen.
Folgerung
Es gibt Probleme, die mit keinem Computer gelöst werden können!
Zum Beispiel das Halteproblem oder das zehnte Hilbertsche Problem.
Kann ein Computer rechnen?
Ist das Programm korrekt?
Wiederholung: Algorithmusbegriff
Vom Algorithmus zum Programm
Der intuitive Algorithmusbegriff (Wiederholung)
Ein Algorithmus ist eine „Berechnungsvorschrift“. Die Aufgabe, die der Algorithmus
lösen soll, wird durch eine Spezifikation festgelegt.
Die Berechnungsvorschrift wird durch einen endlichen Text kodiert.
Sie beschreibt die auszuführenden Berechnungen „hinreichend präzise“.
Die Berechnungen sind aus „elementaren“ Operationen aufgebaut und
besitzen Aus- und evtl. Eingabewerte.
Hierbei handelt es ich um eine sog. intuitive Definition. In der Informatik wird auch
eine formale Definition benötigt, zum Beispiel zum Nachweis, dass für ein
bestimmtes Problem kein Algorithmus existiert.
»Intuitiv heißt nicht erlernt.« (Bruce M. Hood)
31. März – 10. April 2015 | Werner Struckmann | Seite 23 / 35
Kann ein Computer rechnen?
Ist das Programm korrekt?
Wiederholung: Algorithmusbegriff
Kann ein Computer rechnen?
Ist das Programm korrekt?
Wiederholung: Algorithmusbegriff
Vom Algorithmus zum Programm
1. Was ist ein Algorithmus?
2. Was ist ein Programm?
3. Wie wird ein Algorithmus aufgeschrieben?
4. Mit welchem Aufwand löst der Algorithmus das Problem?
5. Löst der Algorithmus das Problem?
6. Gibt es einen Algorithmus für das Problem?
7. Vom kleinen zum großen Programm
8. Weitere Aspekte
Vom Algorithmus zum Programm
Kann ein Computer rechnen?
Ist das Programm korrekt?
Wiederholung: Algorithmusbegriff
Was ist ein Algorithmus? Wichtige Aspekte
s. oben: intuitiver Algorithmusbegriff
„intuitiv“ heißt „nicht erlernt“ (Bruce M. Hood)
Spezifikation
Terminierung
primitive und komplexe Datentypen, abstrakte Datentypen
Varianten des Algorithmusbegriffs:
deterministisch, determiniert, nichtdeterministisch,
randomisiert, parallel, verteilt, ...
31. März – 10. April 2015 | Werner Struckmann | Seite 25 / 35
Vom Algorithmus zum Programm
Kann ein Computer rechnen?
Ist das Programm korrekt?
Wiederholung: Algorithmusbegriff
Vom Algorithmus zum Programm
Was ist ein Programm?
Umsetzung eines Algorithmus in eine Sprache, die ein Computer versteht.
Sprachen:
Maschinensprachen
maschinenorientierte Sprachen (Assemblersprachen)
problemorientierte Sprachen
Verarbeitung von Programmen:
Compiler
Interpreter
Mischverfahren
Bestandteile einer Programmiersprache:
Lexik
Syntax
Semantik
Pragmatik einer Programmiersprache
31. März – 10. April 2015 | Werner Struckmann | Seite 26 / 35
Kann ein Computer rechnen?
Ist das Programm korrekt?
Wiederholung: Algorithmusbegriff
Vom Algorithmus zum Programm
Java-Mischverfahren
Java-Quellprogramm
javac
Java-Bytecode
java
JVM: Windows
java
JVM: Linux
31. März – 10. April 2015 | Werner Struckmann | Seite 27 / 35
Kann ein Computer rechnen?
Ist das Programm korrekt?
Wiederholung: Algorithmusbegriff
Wie wird ein Algorithmus aufgeschrieben?
Paradigmen:
Imperatives Paradigma: Algol, Pascal, C
Objektorientiertes Paradigma: Smalltalk, Eiffel
Funktionales Paradigma: ML, Lisp, Haskell
Logisches Paradigma: Prolog
Hybride Paradigmen:
Imperativ und objektorientiert: Java, C++
Java 8 geht in die Richtung weiteres Paradigma: funktional
Imperativ und funktional: Scheme
Imperativ, objektorientiert und funktional: Scala
Deklaratives vs. prozedurales Paradigma
31. März – 10. April 2015 | Werner Struckmann | Seite 28 / 35
Vom Algorithmus zum Programm
Kann ein Computer rechnen?
Ist das Programm korrekt?
Wiederholung: Algorithmusbegriff
Vom Algorithmus zum Programm
Mit welchem Aufwand löst der Algorithmus das Problem?
Komplexität
Laufzeitkomplexität, Speicherkomplexität
best case, average case, worst case Komplexität
Es gibt weitere Komplexitätsfragen!
O-Notation, Landau-Symbole
Θ(g) = {f : N −→ R | ∃c1 > 0, c2 > 0, n0 > 0 ∀n ≥ n0 . 0 ≤ c1 g(n) ≤ f (n) ≤ c2 g(n)}
O(g) = {f : N −→ R | ∃c > 0, n0 > 0 ∀n ≥ n0 . 0 ≤ f (n) ≤ cg(n)}
Ω(g) = {f : N −→ R | ∃c > 0, n0 > 0 ∀n ≥ n0 . 0 ≤ cg(n) ≤ f (n)}
o(g) = {f : N −→ R | ∀c > 0 ∃n0 > 0 ∀n ≥ n0 . 0 ≤ f (n) < cg(n)}
ω(g) = {f : N −→ R | ∀c > 0 ∃n0 > 0 ∀n ≥ n0 . 0 ≤ cg(n) < f (n)}
31. März – 10. April 2015 | Werner Struckmann | Seite 29 / 35
Kann ein Computer rechnen?
Ist das Programm korrekt?
Wiederholung: Algorithmusbegriff
Vom Algorithmus zum Programm
Löst der Algorithmus das Problem?
Spezifikation
Korrektheit: partielle Korrektheit, totale Korrektheit
Verifikation: Nachweis der Korrektheit
Validation: Als Validierung bezeichnet man den Test eines Softwaresystems
unter Bedingungen, wie sie im späteren Einsatz herrschen werden. Auch
wenn das zu erstellende Programm verifiziert wurde, kann auf eine
Validierung nicht verzichtet werden, da ein mathematischer Nachweis der
Korrektheit beispielsweise nichts über das Laufzeitverhalten des Programms
oder die Auslastung von Ressourcen aussagt.
Gibt es einen Algorithmus, der alle Algorithmen verifizieren kann?
Der Satz von R ICE gibt viele konkrete Probleme an, die algorithmisch nicht
behandelt werden können.
31. März – 10. April 2015 | Werner Struckmann | Seite 30 / 35
Kann ein Computer rechnen?
Ist das Programm korrekt?
Wiederholung: Algorithmusbegriff
Vom Algorithmus zum Programm
Gibt es einen Algorithmus für das Problem?
Berechenbarkeit, Entscheidbarkeit
Formale Algorithmendefinition
Turing-Maschine
Markov-Algorithmus
λ-Kalkül
Primitiv rekursive Funktionen
...
Diese Modelle sind alle äquivalent.
Beispiele: Halteproblem, diophantische Gleichungen, . . .
Abzählbar viele Probleme sind berechenbar.
Überabzählbar viele Probleme sind nicht berechenbar.
D. h., so gut wie kein Problem kann ein Computer lösen.
31. März – 10. April 2015 | Werner Struckmann | Seite 31 / 35
Kann ein Computer rechnen?
Ist das Programm korrekt?
Wiederholung: Algorithmusbegriff
Vom Algorithmus zum Programm
Church’sche These
A LONZO C HURCH stellte 1936 die folgende These auf, die bis heute nicht widerlegt
wurde:
Church’sche These: Der intuitive Algorithmenbegriff
wird durch das Modell der Turing-Maschine adäquat definiert.
Die Church’sche These kann natürlich nicht bewiesen werden, da sie den intuitiven
Algorithmenbegriff verwendet. Über intuitive Dinge können keine formalen
Beweise geführt werden. Es wurde gezeigt, dass alle oben erwähnten formalen
Algorithmusdefinitionen äquivalent sind. Daher kann in der Church’schen These
die Turing-Maschine durch andere Definitionen des Algorithmus ersetzt werden.
31. März – 10. April 2015 | Werner Struckmann | Seite 32 / 35
Kann ein Computer rechnen?
Ist das Programm korrekt?
Wiederholung: Algorithmusbegriff
Vom Algorithmus zum Programm
Vom kleinen zum großen Programm
Software Engineering Manifest (2006):
Das Software Engineering zielt auf die ingenieurmäßige Entwicklung, Wartung,
Anpassung und Weiterentwicklung großer Softwaresysteme unter Verwendung
bewährter systematischer Vorgehensweisen, Prinzipien, Methoden und
Werkzeuge.
Analysephase
Entwurfsphase
Implementierungsphase
Testphase
Betriebs- und Wartungsphase
31. März – 10. April 2015 | Werner Struckmann | Seite 33 / 35
Kann ein Computer rechnen?
Ist das Programm korrekt?
Wiederholung: Algorithmusbegriff
Vom Algorithmus zum Programm
Weitere Aspekte (Beispiele)
Standardalgorithmen
Datenstrukturen, Typsysteme, abstrakte Datentypen
Prinzipien zum Entwurf von Algorithmen
Divide-and-Conquer-Algorithmen
Backtracking-Algorithmen
Greedy-Algorithmen
Dynamische Algorithmen, . . .
Variationen des Algorithmusbegriffs
Randomisierte Algorithmen
Nichtdeterministische Algorithmen
Parallele, verteilte Algorithmen, . . .
Sprachen der Informatik
GPL (General purpose languages): Programmiersprachen
DSL (Domain specific languages): Datenbanksprachen, HTML, XML, . . .
31. März – 10. April 2015 | Werner Struckmann | Seite 34 / 35
Kann ein Computer rechnen?
Ist das Programm korrekt?
Wiederholung: Algorithmusbegriff
Vom Algorithmus zum Programm
Herzlichen Dank für Ihre Aufmerksamkeit!
Viel Erfolg im Studium.
31. März – 10. April 2015 | Werner Struckmann | Seite 35 / 35
© Copyright 2024 ExpyDoc
