Vom Algorithmus zum Programm - ips.tu-braunschweig.de · Weitere Bezeichnungen für Paradigmen: hybrid, prozedural, deklarativ. Mit welchem Aufwand löst der Algorithmus das Problem?Komplexität

Algorithmus Beispiele: Algorithmen als Programme Sind Programme korrekt? Gibt es Algorithmen? FAZIT

Algorithmusbegriff

Ein Algorithmus ist eine „Berechnungsvorschrift“. Die Aufgabe, die der Algorithmuslö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 undbesitzen Aus- und evtl. Eingabewerte.

Hierbei handelt es ich um eine sog. intuitive Definition. In der Informatik wird aucheine formale Definition benötigt, zum Beispiel zum Nachweis, dass für einbestimmtes Problem kein Algorithmus existiert.

»Intuitiv heißt nicht erlernt.« (Bruce M. Hood)


Eigenschaften von Algorithmen

Algorithmen sollen in der Regel terminieren, d. h. bei jeder Eingabeirgendwann zu einem Ende führen. Es gibt Ausnahmen: z. B.Betriebssysteme oder sogenannte „reaktive Systeme“.

Die Terminierung wird in der Definition des Algorithmusbegriffs nichtverwendet. Ein Grund hierfür ist zum Beispiel das Halteproblem (s. unten):Definitionen müssen überprüfbar sein.

Einen Algorithmus nennt man deterministisch, wenn er bei gleichenEingabedaten stets die gleiche Berechnung ausführt.

Ein Algorithmus heißt determiniert, wenn er bei gleichen Eingabedaten stetsdie gleichen Ausgabedaten liefert.


Programm und Programmiersprache

Ein Programm ist die Formulierung eines Algorithmus mit seiner Datenbereiche ineiner Programmiersprache. Eine Programmiersprache erlaubt es, Algorithmenprä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 Erstellenseines Programms.


Grundlegende Aspekte der Algorithmenentwicklung

Wie wird ein Algorithmus formuliert? Paradigma.Beispiele für Paradigmen: imperativ, objektorientiert, funktional, logisch.Es gibt weitere Paradigmen, diese vier sind aber die am häufigstenerwähnten.Weitere Bezeichnungen für Paradigmen: hybrid, prozedural, deklarativ.

Mit welchem Aufwand löst der Algorithmus das Problem? Komplexität.Beispiele zur Komplexität: benötigte Rechenzeit oder verwendeterSpeicherplatz.

Erfüllt mein Algorithmus seine Spezifikation? Korrektheit.Der Nachweis der Korrektheit wird Verifikation genannt.

Wie werden Datentypen definiert? Abstrakte Datentypen.ADT/Abstrakte Datentypen werden durch algebraische Methoden definiert.



Gibt es für das Problem einen Algorithmus?Berechenbarkeit/Entscheidbarkeit.Zur Beantwortung dieser Frage wird eine formale Definition desAlgorithmenbegriffs benötigt. Beispiel: Turing-Maschine.

Alonzo Church stellte 1936 die folgende These auf, die bisher nicht widerlegtwurde. Church’sche These:

Der intuitive Algorithmenbegriff wird durchdas Modell der Turing-Maschine adäquat definiert.

Die Church’sche These kann natürlich nicht bewiesen werden, da sie denintuitiven Algorithmenbegriff verwendet. Über intuitive Dinge können keineformalen Beweise geführt werden. Es wurde gezeigt, dass viele formaleAlgorithmusdefinitionen äquivalent sind. Daher könnte in der Church’schenThese die Turing-Maschine durch etliche andere formale Definitionen desAlgorithmus ersetzt werden.



Gibt es Vorgehensweisen für die Erstellung von Algorithmen?Entwurf von Algorithmen.Beispiele: Rekursion, Backtracking, Divide-and-Conquer,Greedy-Algorithmus, . . .

Gibt es Algorithmen, die man häufig verwenden kann?Standardalgorithmen für Standardprobleme.Beispiele: Algorithmen zum Suchen und Sortieren, Algorithmen für konkreteDatentypen (zum Beispiel: Graphen, Listen, Keller, Schlangen, . . . )

Gibt es andere Definitionen des Algorithmenbegriffs?Varianten des Algorithmenbegriffs.Beispiele: nichtdeterministische, parallele, randomisierte Algorithmen.


Paradigmen zur Formulierung von Algorithmen

In einem imperativen Algorithmus gibt es Variable, die verschiedene Werteannehmen können. Die Menge aller Variablen und ihrer Werte sowie derProgrammzähler beschreiben den Zustand zu einem bestimmten Zeitpunkt. EinAlgorithmus bewirkt eine Zustandstransformation.In einem objektorientierten Algorithmus werden Datenstrukturen undMethoden/Funktionen zu einer Klasse zusammengefasst. Von jederKlasse können Objekte gemäß der Datenstruktur erstellt und über die Methodenmanipuliert werden.Ein logischer (deduktiver) Algorithmus führt Berechnungen durch, indem er ausFakten und Regeln durch Ableitungen in einem logischem Kalkül Ziele beweist.Ein funktionaler Algorithmus formuliert die Berechnung durch Funktionen. DieFunktionen können rekursiv sein; auch gibt es Funktionen höherer Ordnung.Unter einem hybriden Paradigma versteht man die Mischung von Paradigmen.


Paradigmen zur Formulierung von Algorithmen

Aus einer übergeordneten Sichtweise werden die folgenden Kategorienunterschieden:

Prozedurale Programmiersprachen: Es wird exakt angegeben, wie dieLösung eines Problems ermittelt werden kann. ImperativeProgrammiersprachen fallen in diese Kategorie.

Deklarative Programmiersprachen: Im Gegensatz zum prozeduralenParadigma fragt man in der deklarativen Programmierung danach, wasberechnet werden soll. Es wird also nicht der Lösungsweg programmiert,sondern angegeben, welches Ergebnis gewünscht ist. DeklarativeParadigmen beruhen auf mathematischen, rechnerunabhängigen Theorien.Beispiele hierfür sind prädikative und – bis zu einem gewissen Grade – auchfunktionale Programmiersprachen.


Formulierung vom Algorithmus

Paradigmen: Formulierung von Programmen. Beispiele:

imperativ

objektorientiert

funktional

logisch

Gemischte Paradigmen:

hybrid

Wie kann die Art der Ausführung formuliert werden?

prozedural

deklarativ


Imperatives Paradigma

Wichtige Grundlagen vom imperativen Paradigma:

Variable,

Ausdrücke,

Anweisungen,

Datenstrukturen,

Funktionen,

...


Beispiel: Algorithmus von Euklid

Der folgende, in einer imperativen Programmiersprache formulierte,

Algorithmus von Euklid (ca. 300 v. Chr.)

berechnet den größten gemeinsamen Teiler der Zahlen x, y ∈ N mit x > 0 undy ≥ 0:

Variable z0 z1 z2 z5 z8 z11 z14

r – – – 36 16 4 0a – 36 36 52 36 16 4b – – 52 36 16 4 0

ggT(36,52) = 4

Durchlaufene Zustände: z0, z1, z2, . . . , z14


Imperatives Paradigma

Der Algorithmus in der Programmiersprache C:

# include <stdio.h>

int ggt(int a, int b) {

int r;

while (b != 0) {

r = a % b;

a = b;

b = r;

}

return a;

}

int main(void) {

printf("ggT(36,52) = %d", ggt(36,52));

return 0;

}

Ausgabe: ggT(36,52) = 4


Objektorientiertes Paradigma

Wichtige Grundlagen vom objektorientierten Paradigma:

Klassen,

Objekte,

Modifikatoren,

Vererbung,

Datentypen,

Ausdrücke,

Anweisungen,

vordefinierte Klasse,

...


Objektorientiertes ParadigmaBeispiel für die Programmiersprache Java:

public class Studie { //Klasse Studie

private String vorname;

private String nachname;

private String Studiengang;

public Studie(String vorname, String nachname) {

this.vorname = vorname;

this.nachname = nachname;

}

public void setGang(String Gang) {

Studiengang = Gang;

}

public String getGang() {

return Studiengang;

}

public void drucken() {

System.out.println(vorname+" "+nachname+

"ist im Studiengang "+Studiengang+".");

}

}


Objektorientiertes ParadigmaAnwendung:

class Ausfuehrung {

public static void main(String[] args) {

Studie a = new Studie("Hans", "Müller"); // Objekte von Studie

a.setGang("BS-Informatik");

Studie b = new Studie("Karin", "Meier");

b.setGang("BS-Mathematik");

Studie c = new Studie("Dietmar", SSchief");

c.setGang("BS-Physik");

a.drucken();

b.drucken();

c.drucken();

}

}

Dies ist die Ausgabe:

Hans Müller ist im Studiengang BS-Informatik.

Karin Meier ist im Studiengang BS-Mathematik.

Dietmar Schief ist im Studiengang BS-Physik.


Deduktives (logisches) Paradigma

Ein deduktiver (logischer) Algorithmus führt Berechnungen durch, indem eraus Fakten und Regeln weitere Fakten, sogenannte Anfragen (Ziele), beweist.

Fakten:P

Regeln:P if Q1 and Q2 and . . . and Qk

Regeln dieser Form werden auch Horn-Klauseln genannt. Fakten können alsRegeln mit k = 0 gesehen werden.

Das folgende Beispiel wurde in der deduktiven Programmiersprache Prologgeschrieben.



Beispiel in der Programmiersprache Prolog: Eingabe der Fakten und Regeln.

vater(johann,heinrich).

vater(johann,thomas).

vater(heinrich,carla).

vater(thomas,erika).

vater(thomas,klaus).

vater(thomas,golo).

vater(thomas,monika).

vater(thomas,elisabeth).

vater(thomas,michael).

verheiratet(johann,julia).

verheiratet(heinrich,maria).

verheiratet(thomas,katia).

mutter(X,Y) :- vater(Z,Y), verheiratet(Z,X).

geschwister(X,Y) :- vater(Z,X), vater(Z,Y), X = / = Y.



Beispiel in der Programmiersprache Prolog: Eingabe der Anfragen.

Nachdem das Programm eingelesen wurde, können Anfragen gestellt werden, dievon einer Interferenzmaschine, zum Beispiel einem Prolog-Interpreter, beantwortetwerden. Anfragen werden nach der Eingabeaufforderung | ?- gestellt:

| ?- geschwister(thomas, heinrich).

true ? ;

no

| ?- geschwister(thomas, golo).

no

Die Ausgabe true bedeutet, dass die Anfrage positiv beantwortet wurde, das heißt,dass Thomas und Heinrich Geschwister sind. Nach einem Fragezeichen erwartetder Interpreter Anweisungen, wie fortzufahren ist. Ein Semikolon ist dieAufforderung, nach weiteren Lösungen zu suchen.




Falls eine Anfrage eine Variable enthält, werden alle Belegungen für die Variablenermittelt, die die Aussage wahr werden lassen. Wenn wir die Geschwister vonGolo suchen, stellen wir die folgende Anfrage.

| ?- geschwister(X,golo).

X = erika ? ;

X = klaus ? ;

X = monika ? ;

X = elisabeth ? ;

X = michael ? ;

no

Erika, Klaus, Monika, Elisabeth und Michael sind also die Geschwister von Golo.




Eine Anfrage kann mehr als eine Variable enthalten. Durch

| ?- geschwister(X,Y).

werden insgesamt 32 Geschwisterpaare ermittelt, da Paare wegen der Symmetrieder Relation doppelt ausgegeben werden.


Funktionales Paradigma

Bei diesen Sprachen berechnen Programme Funktionen, die Eingabedatenauf Ausgabedaten abbilden. Ein funktionales Programm beschreibt dieBeziehungen zwischen Ein- und Ausgabe mithilfe mathematischerGleichungen.

Ausgehend von elementaren Ausdrücken werden die Beziehungen durchAusdrücke steigender Komplexität festgelegt.

Das wichtigste Konstruktionsprinzip ist hierbei die Rekursion.

Außerdem spielen Funktionen höherer Ordnung, sogenannte Funktionale,eine wichtige Rolle.


Beispiel: Quicksort

Sortieren:

20 9 7 11 13 12 15

Ein Element (hier 12) an die richtige Stelle bringen.

9 7 11 12 20 13 15

So rekursiv weitermachen immer an den Teilen.


Funktionales Paradigma

Der Algorithmus in der Programmiersprache Haskell:

Quicksort, Version 1:

qsort [] = []

qsort (x:xs) = qsort smaller ++ [x] ++ qsort larger

where

smaller = [a | a<-xs, a<=x]

larger = [a | a<-xs, a>x]

Quicksort, Version 2:

qs [] = []

qs (x:xs) = qs (filter (< x) xs) ++ [x] ++ qs (filter (>= x) xs)


Programmiersprachen: Beispiele

Imperative Programmiersprachen:Cobol, Fortran, PL/I, Basic, Algol, Algol68, Pascal, Modula-2, C, Ada, ....

Funktionale Programmiersprachen:Lisp, Scheme, ML, Haskell, Scala, ....

Objektorientierte Programmiersprachen:C++, Eiffel, Smalltalk, Java, C#, Oberon, ....

Logische Programmiersprachen:Prolog.

Hybride Sprachen: z. B. Java, C++, Scala, ....

Skriptsprachen, Spezialsprachen

prozedurales, deklaratives Vorgehen

Wir sehen uns jetzt TIOBE an.

14. November 2017 | Werner Struckmann | Vom Algorithmus zum Programm | Seite 24 / 42


Beispiel 1: Multiplikation zweier Zahlen

Sind Programme korrekt?

public class Mult01 {public s t a t i c void main ( S t r i n g [ ] args ) {

System . out . p r i n t l n ( 1 * 1 ) ;System . out . p r i n t l n (12 *12 ) ;System . out . p r i n t l n (123*123) ;System . out . p r i n t l n (1234*1234) ;System . out . p r i n t l n (12345*12345);System . out . p r i n t l n (123456*123456);

}}

Ausgabe:

1

144

15129

1522756

152399025

-1938485248

Das Quadrat einer Zahl ist nicht negativ. Hat sich der Computer verrechnet?


Beispiel 1: Multiplikation zweier Zahlen

Sind Programme korrekt?


System . out . p r i n t l n ( 1 * 1 ) ;System . out . p r i n t l n (12 *12 ) ;System . out . p r i n t l n (123*123) ;System . out . p r i n t l n (1234*1234) ;System . out . p r i n t l n (12345*12345);System . out . p r i n t l n (123456*123456);

}}

Ausgabe:

1

144

15129

1522756

152399025

-1938485248

Das Quadrat einer Zahl ist nicht negativ. Hat sich der Computer verrechnet?


Beispiel 2: Multiplikation und Addition


i n t z = 256*256*256*128+2147483647;System . out . p r i n t l n ( z * z ) ;

}}

Ausgabe: 1

Hat sich der Computer schon wieder verrechnet?



Beispiel 2: Multiplikation und Addition


i n t z = 256*256*256*128+2147483647;System . out . p r i n t l n ( z * z ) ;

}}

Ausgabe: 1

Hat sich der Computer schon wieder verrechnet?



Beispiel 3: Kommazahlen

Java:

p u b l i c c lass Numerik {p u b l i c s t a t i c void main ( S t r i n g [ ] args ) {

double a = 1 . 0 / 3 . 0 ,b = 10.0+a−10.0 , c ;

i f ( a==b )c = 0;

elsec = 1 / ( a−b ) ;

System . out . p r i n t f ( " %20.5 f%n " , c ) ;}

}

Ausgabe: -1637672591771089.50000- 1 Billiarde 637 Billionen 672 Milliarden 591 Millionen 771 Tausend und 89,5

korrekter Wert: 0

Kann der Computer nicht rechnen?


Beispiel 3: Kommazahlen

Java:

p u b l i c c lass Numerik {p u b l i c s t a t i c void main ( S t r i n g [ ] args ) {

double a = 1 . 0 / 3 . 0 ,b = 10.0+a−10.0 , c ;

i f ( a==b )c = 0;

elsec = 1 / ( a−b ) ;

System . out . p r i n t f ( " %20.5 f%n " , c ) ;}

}

Ausgabe: -1637672591771089.50000- 1 Billiarde 637 Billionen 672 Milliarden 591 Millionen 771 Tausend und 89,5

korrekter Wert: 0

Kann der Computer nicht rechnen?


Fehler beim Programmieren

In Jahre 1999 wurde durch die Fehlfunktion eines Seitenairbags ein Babygetö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.



Fehler beim Programmieren

Richtige Reihenfolge:

airbag = ein;if (kindersitz == belegt) {

airbag = aus;}

Falsche Reihenfolge:

if (kindersitz == belegt) {airbag = aus;

}airbag = ein;



Semantik ist nicht überall gleich

Diese Funktion

f (x, y) =

{1 x = 0

f (x − 1, f (x − y, y)) x 6= 0

als Methode:

static int f(int x, int y) {if (x==0) return 1; else return f(x-1, f(x-y, y));

}

Was liefert der Aufruf f(1,0)?

1. Möglichkeit: f(1,0) = f(0,f(1,0)) = 1

2. Möglichkeit: f(1,0) = f(0,f(1,0)) = f(0,f(0,f(1,0))) = ...Alle Parameter auswerten liefert kein Ergebnis.

Alle Programmiersprachen machen es mit dem gleichen Programmelement nichtidentisch.


Der intuitive Algorithmus

Ein Algorithmus ist eine „Berechnungsvorschrift“. Die Aufgabe, die der Algorithmuslö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 undbesitzen Aus- und evtl. Eingabewerte.

Hierbei handelt es ich um eine sog. intuitive Definition. In der Informatik wird aucheine formale Definition benötigt. Zum Beispiel zum Beweis, dass für bestimmteProbleme kein Algorithmus existiert.

»Intuitiv heißt nicht erlernt.« (Bruce M. Hood)


Formulierung vom Algorithmus

Paradigmen: Formulierung von Programmen. Beispiele:

imperativ

objektorientiert

funktional

logisch

Gemischte Paradigmen:

hybrid

Wie kann die Art der Ausführung formuliert werden?

prozedural

deklarativ


Berechenbarkeit und Entscheidbarkeit

Gibt es für das Problem einen Algorithmus?

Zur Beantwortung dieser Frage wird eine formale Definition desAlgorithmenbegriffs benötigt. Es gibt mehrere formale Definitionen:

Turing-Maschine

Lambda-Kalkül

Markow-Algorithmus

Partielle Rekursion

Registermaschine

...

Man hat bewiesen, dass diese Definitionen äquivalent sind.


Berechenbarkeit und Entscheidbarkeit

Alonzo Church stellte 1936 die folgende These auf, die bisher nicht widerlegtwurde.

Church’sche These:

Der intuitive Algorithmenbegriff wird durchdas Modell der Turing-Maschine adäquat definiert.

Die Church’sche These kann natürlich nicht bewiesen werden, da sie den intuitivenAlgorithmenbegriff verwendet. Über intuitive Dinge können keine formalen Beweisegeführt werden. Es wurde gezeigt, dass viele formale Algorithmusdefinitionenäquivalent sind. Daher könnte in der Church’schen These die Turing-Maschinedurch etliche andere formale Definitionen des Algorithmus ersetzt werden.



Das Halteproblem ist unentscheidbar. Wir zeigen die Aussage indirekt:

Annahme: Es gibt einen Algorithmus

HALT(algorithmus a, eingabe e),

der für einen Algorithmus a und eine Eingabe e genau dann das Ergebnistrue liefert, wenn a bei Eingabe von e terminiert.

Der Algorithmus TEST(algorithmus a) sei definiert durch

TEST(algorithmus a): while HALT(a,a) { ... } .

TEST(a) terminiert also genau dann nicht, falls a bei Eingabe von a terminiert.

Zwei Fälle können eintreten:

1. Fall: Der Aufruf HALT(TEST, TEST) liefert true.

In diesem Fall terminiert nach Definition von HALT der Aufruf TEST(TEST).Hieraus folgt aus der Definition von TEST, dass der Aufruf TEST(TEST) nichtterminiert, ein Widerspruch.

2. Fall: Der Aufruf HALT(TEST, TEST) liefert false.

In diesem Fall terminiert nach Definition von HALT der Aufruf TEST(TEST)nicht. Hieraus folgt aus der Definition von TEST, dass der Aufruf TEST(TEST)terminiert, ein Widerspruch.

Da in beiden Fällen ein Widerspruch auftritt, gibt es den Algorithmus HALT nicht.


Beispiel für berechenbares Problem

Eine lineare diophantische Gleichung mit zwei Unbekannten x und y ist eineGleichung der Form

ax + by = c (1)

für gegebene ganze Zahlen a, b, c. Gesucht werden ganze Zahlen x und y , die dieGleichung erfüllen.

Die Gleichung besitzt eine Lösung, wenn der ggT(a, b) ein Teiler von c ist.Es gibt dann einen Algorithmus zum Finden einer Lösung.

Beispiel:

36x + 52y = 24

Diese Gleichung besitzt Lösungen, da ggt(36,52) = 4 ein Teiler von 24 ist:

36 · 18 + 52 · (−12) = 24

Zur Lösung von linearen diophantischen Gleichungen gibt es einen Algorithmus.


Beispiel für nichtberechenbares Problem

Definition: Eine allgemeine diophantische Gleichung mit den Unbekanntenx1, 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 allgemeinediophantische 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.

Es gibt Probleme, die mit keinem Computer gelöst werden können!Zum Beispiel das Halteproblem oder das zehnte Hilbertsche Problem.


Respektion von Funktionen

M0,M1,M2, . . . sei eine Aufzählung aller Algorithmen.ϕ0, ϕ1, ϕ2, . . . seien die zugehörigen berechneten Funktionen.

Definition: Eine Menge von Indizes J ⊆ N respektiert Funktionen, wenn für allei , j ∈ N die Aussage

i ∈ J,ϕi = ϕj =⇒ j ∈ J

gilt.

Beispiele: Offenbar respektieren die folgenden Indexmengen Funktionen.

1. A = {i | 7 liegt im Wertebereich von ϕi },2. B = {i | ϕi ist total},3. C = {i | ϕi ist überall undefiniert},4. D = {i | ϕi = ξ} für eine gegebene partielle Funktion ξ : N→ N.

Der Satz von Rice

Satz: Henry Gordon Rice, 1953: Es sei J ⊆ N eine Menge von Indizes, dieFunktionen respektiert. Dann gilt

J ist entscheidbar ⇐⇒ J = ∅ oder J = N.

Beispiele: Da die obigen Indexmengen A,B,C und D nicht leer und ungleich Nsind und Funktionen respektieren, sind die folgenden Probleme nicht entscheidbar.

1. Gibt ein beliebiger Algorithmus für eine geeignete Eingabe die Zahl 7 aus?2. Hält ein beliebiger Algorithmus bei jeder Eingabe?3. Hält ein beliebiger Algorithmus bei keiner Eingabe?4. Berechnet ein beliebiger Algorithmus die gegebene partielle Funktionξ : N→ N?

Erweiterung: Die Definition und der Satz können auf n-stellige IndexmengenJ ⊆ Nn, n ≥ 2, übertragen werden. Man erhält beispielsweise, dass die Menge{(i , j ) |ϕi = ϕj } Funktionen respektiert und daher nicht entscheidbar ist. Also istdas Äquivalenzproblem für Algorithmen nicht entscheidbar.

Es ist also so gut wie kein Problem algorithmisch lösbar.Schon gesehen: Halteproblem, diophantische Gleichungen.


Korrektheit von Progammen

Spezifikation:

Die Spezifikation beschreibt die Aufgabe des Algorithmus

{p} A {q}

p: Vorbedingung, A Algorithmus, q: Nachbedingung.

Wenn es einen Algorithmus für ein Problem gibt, ist er korrekt?

Partielle Korrektheit:

Falls der Algorithmus terminiert wird die Spezifikation erfüllt.

Totale Korrektheit:

Der Algorithmus terminiert und erfüllt die Spezifikation.Wie gesehen: Die Terminierung ist ggf. schwierig zu beweisen.


Fazit: Wir haben gesehen

Wenn es einen Algorithmus gibt, kann er abhängig von den zur Verfügungstehenden Sprachen unterschiedlich formuliert werden.

Der Aufwand kann sehr unterschiedlich sein.

Man hat die Möglichkeit schwere Fehler zu machen.

Für viele Probleme gibt es Algorithmen.

Für viele mehr Probleme gibt es keine Algorithmen.

Auch wenn man eine Lösung gefunden hat und sie sogar schon getestet undauch bewiesen hat, dass sie korrekt ist, kann es zu schweren Fehlern führen.

Man hat also die Chance durch kleine Fehler großenSchaden einzurichten.


Weiteres

Bei der Programmierung (Formulierung von Algorithmen als Programme) gibt esweitere Aspekte:

Beweis der Korrektheit des verwendeten Algorithmus,

Berücksichtigung der Komplexität des Algorithmus,

Datenstrukturen,

Varianten vom Algorithmusbegriff:z. B. parallele oder randomisierte oder nichtdeterministische Programme.

API (application programming interface):Vordefinierte Programmteile für Anwendungen.

Packages

....

Empfehlung:

Wenn Sie Programme schreiben, sehen Sie sich die Aspekte dieses Vortrags an.


Herzlichen Dank für Ihre Aufmerksamkeit!

Gibt es Fragen?

Ich freue mich, Sie als Studi in Braunschweig begrüßen zu dürfen.


Documents

Vom Algorithmus zum Programm - ips.tu-braunschweig.de · Weitere Bezeichnungen für Paradigmen: hybrid, prozedural, deklarativ. Mit welchem Aufwand löst der Algorithmus das Problem?Komplexität