GEHNIO
Gesamtschule Duisburg-Hamborn/Neumühl
Informatik in der Oberstufe

> Home
> Algorithmen
> Datenstrukturen
> Probleme
> Highlights
> Themen
> Mindmaps
> Aufgaben
> Programmierung
> Facharbeit
> Abitur
> Projekte
> Informatik-AG
> News
> Impressum
> email
 


Vom Problem zum Programm


Problem und Problemstellung

Eine Problemstellung ist eine mehr oder weniger formale Beschreibung eines Problems (oder einer Frage), die von etwas Bekanntem ausgeht und nach etwas Unbekanntem fragt. In der Problemstellung wird das Bekannte sprachlich durch Angabe von Eingabegrößen, das Gefragte durch Ausgabegrößen beschrieben. Ein Problem ist aber erst dann vollständig gegeben, wenn der funktionale Zusammenhang zwischen Eingangs- und Ausgangsgrößen sprachlich explizit beschrieben wurde.

Funktionale Spezifikation

In der funktionalen Spezifikation wird das Problem präzisiert und - wenn nötig - formalisiert. Die funktionale Spezifikation ist das Ergebnis der Problemanalyse und stellt die Schnittstelle zwischen Problem und Lösungsalgorithmus dar.
Wenn das Problem spezifiziert ist, stehen Ausgangspunkt und Ziel des Lösungsweges fest, der durch den Algorithmus realisiert werden soll. Die Spezifikation eines Problems ist gleichzeitig Spezifikation aller Algorithmen bzw. Programme, die das Problem lösen.

Spezifikationsregel: Beschreibe die Menge gültiger Eingabegrößen und die Menge möglicher Ausgabegrößen mit allen für die Lösung des Problems wichtigen Eigenschaften und den funktionalen Zusammenhang zwischen ihnen.

Die Menge gültiger Eingabegrößen wird auch Definitionsbereich des Algorithmus genannt; die Menge möglicher Ausgabewerte heißt Wertebereich des Algorithmus.

Lösungsansatz

Der Lösungsansatz ist eine Sammlung von Ideen und Ansätzen zur Problemlösung, sowie schon bekannter Eingabe- undAusgabebeispiele, die für die Lösung des Problems nützlich sind. Hier können z.B. Einzelfälle, deren Eingabe- und Ausgabegrößen trivial bekannt sind, betrachtet werden.Aus dem Lösungsansatz sollten sich erste Ideen oder Prinzipien für den Algorithmusentwurf ableiten lassen.

Algorithmus

Definition: Ein Algorithmus ist eine vollständige, präzise und eindeutige Beschreibung eines endlichen Vorgangs.

Anmerkung: Ein Algorithmus muss bestimmten Kriterien genügen. Die wichtigsten sind Eindeutigkeit, Korrektheit und Endlichkeit.

Programm

Definition: Ein Programm ist ein Algorithmus, der in einer der Maschine verständlichen Programmiersprache (z.B. Pascal, Java) formuliert ist und von ihr ausgeführt werden kann.

Korrektheit und Verifikation

Wenn ein Algorithmus bei gültigen Eingabegrößen Ausgabegrößen erarbeitet, die der funktionalen Spezifikation genügen, nennt man ihn partiell korrekt. Wenn der Algorithmus nach endlich vielen Schritten zu einem Ende kommt, sagt man, er terminiert. Ein Algorithmus der partiell korrekt ist und termisiert ist total korrekt. Der Nachweis der Korrektheit heißt Verifikation.

Aufwand und Aufwandsabschätzung

Algorithmen und Programme können auf ihren Zeit- und Platzaufwand hin untersucht werden. Meist wird dabei der Rechenzeit- und Speicherplatzaufwand in Abhängigkeit von der Größe der Eingabe betrachtet.



Fortsetzung folgt ...

 

 

 

 

 

 

 

 

 
  © 2001 Gesamtschule Duisburg-Hamborn/Neumühl.  
Hosted by www.Geocities.ws

1