PMG/Sammlung alt
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
<language>Pascal</language>
== "Sortieren" - Vergleich zweier Zahlen ==
<font size=1>(Ein Beispiel aus der Wissenschaftlichen Arbeit im Fach Informatik "Bildungsstandards Informatik - Aufgaben für den Unterricht zum Thema "Algorithmen" von Stefan Renz, TU Dresden, 2010)</font>
Am Kölner Dom wurde über 600 Jahre gebaut, als er 1880 fertig wurde, war er
allerdings nur für vier Jahre das höchste Gebäude der Welt. Hier eine Auswahl
sehr hoher Gebäude:
{| border="0"
|-
| '''Name''' || '''Höhe'''
|-
| Kölner Dom || 157m
|-
| Eiffelturm || 300m
|-
| Cheops-Pyramide|| 147m
|-
| Burj Khalifa|| 828m
|-
| Washington Monument|| 169m
|-
| Sendemast Radio Warschau || 646m
|-
| Empire State Building || 449m
|}
# Überlege Dir einen Algorithmus, der zwei Zahlen als Eingabe verarbeitet und die größere von beiden als Ergebnis ausgibt. Halte diesen Algorithmus als Struktogramm fest.
# Was passiert bei Deinem Algorithmus, wenn die beiden Zahlen gleich groß sind?
# Setze den Algorithmus in der vorbereiteten Box um.
<code id="4cc726df708e4"></code>
<eval id="4cc726df709fc"></eval>
== Potenz und Betrag/Abstand ==
Gegeben ist folgendes Struktogramm.
[[Bild:Struktogramm(v2).JPG]]
Teste den dargestellten Algorithmus mit den Werten x = 5, y = 8 und z = 3 sowie anderen, selbst gewählten Werten.
Erläutere die Bedeutung der Variablen.<br>
Schreibe Deine Antwort in die Box hinter ''write'':
<eval id="4cc728e2c48fd">
begin
write(' ');
end.
</eval>
Implementiere den dargestellten Algorithmus in der nachfolgenden Box als function ''xyz1'' (Teilalgorithmus '''Potenz''')<br>
<code id="4cc728e2c47c5">
function xyz1(
</code>
<eval id="4cc728e2c4a12">
begin
writeln(inttostr(xyz1(...)));
end.
</eval>
Implementiere den zweiten Teil des Algorithmus in der nachfolgenden Box als function ''xyz2'' (Teilalgorithmus '''Betrag/Abstand''')
<code id="4cda69bd019f1">
function xyz2(
</code>
<run id="4f62550ebabd8">
begin
writeln(inttostr(xyz2(...)));
end.
</run>
== Zufallszahlen und Würfelspiele ==
In den nächsten (letzten) Übungen mit dem PWiki werden wir noch ein paar "Spiele" mit Zufallszahlen erstellen.
Anschließend werden wir mit einer Anwendersoftware (Fischer-Technik) Modelle bauen und steuern!
Doch zunächst:
=== Erzeugen von Zufallszahlen ===
<code id="4cec1965a9796">
function zufall(a:integer):integer;
begin
result:=random(a);
end;
</code>
<eval id="4cec1965a9ae3">
begin
writeln(inttostr(zufall(100)));
end.
</eval>
=== Würfeln ===
Nun sollen nur Ergebnisse zufällig erzeugt werden, wie sie an einem idealen Würfel eintreten können.<br>
Ergänze die Boxen analog dem obigen Beispiel und teste das Ergebnis.<br>
<code id="4cec1965a98b5">
function wurf(a:integer):integer;
begin
end;
</code>
<eval id="4cec1965a9bf2">
begin
// dein Text
end.
</eval>
Simuliere nun ein Würfelspiel mit einem idealen Würfel.
Für eine Anzahl <math>n</math> von Würfen soll die Anzahl aller geworfenen Augenzahlen ausgegeben werden.<br>
''Hinweis:'' Es soll also für jede mögliche Augenzahl eine Variable vereinbart werden, eine beliebige Anzahl von (simulierten)
Versuchen durchgeführt werden und die ''Anzahl'' der gewürfelten Einsen, Zweien, ..., Sechsen ausgegeben werden.
Stelle den notwendigen Algorithmus in einem Struktogramm dar.<br>
Benutze dazu das Tool ''structorizer''.
* Erstelle mit dem Programm das Struktogramm
* Speichere das Struktogramm als Bild (Format .jpg)
* füge dein Bild im PWiki ein
<br>
{| border="1"
|-
| [[Bild:Struktugramm.jpg|Miniatur|250px]] || ||[[Bild:Nmalwürfeln.jpg|Miniatur|250px]]
|-
| Lucie || Martin || Jennifer
|-
| [[Bild:Wurf.jpg|Miniatur|250px]] || [[Bild:Würfel.jpg|Miniatur|250px]] || [[Bild:Wuerfelspiel.jpg|Miniatur|250px]]
|-
| Till || Florian || Sebastian
|-
| [[Bild:Wuerfeln.jpg|Miniatur|100px]]|| [[Bild:Wuerfel.jpg|Miniatur|100px]] || [[Bild:Structoricer.jpg|Miniatur|250px]]
|-
| Ivan || Ronny || Marko
|-
| [[Bild:Zufall-Würfeln.jpg|Miniatur|100px]]|| [[Bild:Würfeln_matschi.jpg|Miniatur|250px]] || [[Bild:Würfel2.jpg|Miniatur|100px]]
|-
| Claudia || Maximilian || Lucas
|}
<code id="4cec1965a99c4">
</code>
<eval id="4cec1965a9d02">
</eval>
'''Wir stellen fest, dass eine ''function'' nur einen Wert (ein Resultat) zurückliefern kann.'''<br>
'''Daher brauchen wir eine weitere Möglichkeit, die mehrere Ergebnisse liefert.'''<br>
Dies geschieht unter Verwendung einer <font color="darkgreen">''procedure''</font>, wobei die Rückgabewerte (Ergebnisvariablen) mit ''var'' angefügt werden (vergleiche Box).
<code id="4d243865b3fab">
procedure wuerfeln(n:integer;var a,b,c,d,e,f:integer);
</code>
<eval id="4d243865b40ec">
</eval>
Formuliere anhand der Simulation eine Aussage über die Wahrscheinlichkeit der einzelnen Ergebnisse beim Würfeln.
<font color="darkgreen">'''''zum Weiterarbeiten:'''''</font> Zeige durch eine analoge Simulation, dass die Zufallsgröße "[[Augensumme beim Würfeln mit zwei idealen Würfeln]]" nicht gleichverteilt ist.
<br><br>
Die Bezeichnung ''Algorithmus'' geht auf den Namen '''Muhammad ibn Musa, Abu Dscha'far al-Chwarizmi''' (* um 780; † um 850), einem persischen Mathematiker, Astronomen und Geographen, zurück.
Diesem Universalgelehrten verdanken wir nicht nur die Einführung der Null aus dem indischen in das arabische Zahlensystem, sondern auch das Wort "Algebra", das der lateinischen Übersetzung seines Buches ''Kitāb al-muchtasar fi hisab al-dschabr wa-l-muqabala'' ("Rechnen durch Ergänzung und Ausgleich") entnommen ist.<br /><br />
== Der Algorithmusbegriff ==
Es existiert eine Vielzahl von Versuchen einer Definition für den Begriff ''Algorithmus''.<br />
z.B.:
<ol>
<li>Als ”Algorithmus [..] bezeichnet [man] heute in der Arithmetik einen Rechenvorgang (bzw.
die ihn beschreibenden Regeln) der nach einem bestimmten sich wiederholenden
Schema abläuft" (Meyers Enzyklopädie, 1971)
</li>
<li>”Ein Algorithmus [..] ist eine vollständige, präzise und in einer Notation oder
Sprache mit exakter Definition abgefasste, endliche Beschreibung eines schritt-
weisen Problemlösungsverfahrens zur Ermittlung gesuchter Datenobjekte (ihrer
Werte) aus gegebenen Werten von Datenobjekten, in dem jeder Schritt aus
einer Anzahl ausführbarer, eindeutiger Aktionen und einer Angabe über den
nächsten Schritt besteht.”(Pomberger, Gustav; Dobler, Heinz: Algorithmen und Datenstrukturen - Eine
systematische Einführung in die Programmierung. München : Pearson Education Deutschland GmbH, 2008)
</li>
<li>”Ein Algorithmus ist eine detaillierte und explizite Vorschrift zur schrittweisen
Lösung eines Problems.”(Gumm, Heinz P.; Sommer, Manfred: Einführung in die Informatik. München :
Oldenbourg Wissenschaftsverlag, 2006)
</li>
</ol>
Wir begnügen uns mit einer anschaulichen ''(intuitiven)'' Erklärung:
<b>''Ein Algorithmus ist eine endliche Folge von eindeutigen und ausführbaren Anweisungen zur Lösung eines allgemeinen Problems.''</b><br>
== Eigenschaften von Algorithmen ==
<ol>
<li>'''Endlichkeit: (Finitheit)'''
* endliche Notation des Algorithmus, (statische Endlichkeit)
* Nutzung endlicher Ressourcen (z.B. begrenzter Arbeitsspeicher / begrenzte Rechenzeit) - dynamische Endlichkeit
</li>
<li>'''Terminiertheit'''
* endlich viele Abarbeitungsschritte - Endlichkeit im Ablauf (z.B. begrenzte Rekursionstiefe), der Algorithmus liefert also bei jeder Anwendung nach endlich vielen Verarbeitungsschritten ein Resultat <br>
* Bei Nichterfüllung: Endlosschleife (Ausnahmen: OS; interaktive Programme)
</li>
<li>'''Deterministisch'''
* nach jedem Abarbeitungsschritt besteht höchstens eine Möglichkeit der Fortsetzung
</li>
<li>'''Eindeutigkeit: (Determiniertheit)'''
* gleiche Eingabegrößen und Anfangsbedingungen liefern stets das gleiche Ergebnis
</li>
<li>'''Ausführbarkeit:'''
* jede Anweisung ist (z.B. für einen Prozessor) verständlich und ausführbar
</li>
<li>'''Allgemeingültigkeit:'''
* Anwendbarkeit auf gleiche Probleme einer Problemklasse.
</li>
</ol>
== Beispiele ==
=== Syntax von Funktionen ===
Beispiel für eine Funktion in einer imperativen Programmierumgebung
[[Bild:Function.JPG]]
Aufruf der Funktion im Hauptprogramm
[[Bild:Function_2.JPG]]
<br />
''hier nun Beispiele für die Syntax im PWIKI''
=== einfache Addition ===
<code id="4bc596ef036ea">
function addi(a,b:integer):integer;
begin
result:=a+b;
end;
</code>
<eval id="4bc596ef084eb">
begin
writeln(inttostr(addi(3,4)));
end.
</eval>
''Ergänze die ähnliche Funktion addi3 zur Bildung der Summe dreier reeller Zahlen!''
<code id="4bccb71f47f51">
function addi33 (a,b,c:integer):integer;
begin
result:=a+b+c;
end;
</code>
<eval id="4bccb71f48edc">
begin
writeln(floattostr(addi33(3,4,5)));
end.
</eval>
<check>
result := (addi33 (3,4,5) = 12) and (addi33 (8,4,15) = 27);
</check>
=== Quadrat einer Zahl ===
<code id="4bc596ef0560c">
function quadrat (x : integer):integer;
var erg: integer ;
begin
erg := x*x;
result := erg;
end;
</code>
<eval id="4bc4611f3a5f1">
begin
writeln(inttostr(quadrat(2)));
end.
</eval>
=== Beispiel 3 ===
''Untersuche diese Funktion.''<br>
Gib Deine Lösung in der zweiten Zeile zwischen den Anführungszeichen '' an.<br>
<code id="4bc596ef065ab">
function was(x,y,z:integer):integer;
var erg: integer;
begin
y:=x ;
erg:=z;
x:=erg;
erg:=y;
result:=erg;
end;
</code>
<eval id="4bc596ef0a437">
begin
writeln(inttostr(was(2,4,6)));
writeln('');
end.
</eval>
=== Gute Wünsche für den Tag ===
''Ergänze die Anweisungen so, dass in der Ausgabe Wünsche für die Tage 1 bis 5 ausgegeben werden.''<br>
Worin unterscheidet sich der Quelltext von den obigen Beispielen?
<code id="4bc596ef0754b">
var i:integer;
begin
for i:= 1 ....
begin
writeln('Alles Gute am Tag ....+'.');
....
end;
end.
</code>
<eval id="4bc596ef0b3cb"></eval>
'''Grundlagen der Unterprogrammarbeit (Modularisierung)'''
== function ==
Beispiel für eine Funktion in einer imperativen Programmierumgebung
[[Bild:Function.JPG]]
Aufruf der Funktion im Hauptprogramm
[[Bild:Function_2.JPG]]
''hier ein Beispiel für die Syntax im WIKI''
<code id="4b96b9dd4d2d7">
function addi(a,b:integer):integer;
begin
result:=a+b;
end;
</code>
<eval id="4b96b9dd51145">
begin
writeln(inttostr(addi(3,4)));
end.
</eval>
Ergänze die ähnliche Funktion addi3 zur Bildung der Summe dreier reller Zahlen!
<code id="4b96b9dd4e268">
function addi3
</code>
<eval id="4b96b9dd520e6">
begin
writeln(floattostr(addi3(3,4,5)));
end.
</eval>
<check>
result := ((addi3(3,4,5) = 12) and (addi3(8,4,15) = 27));
</check>
== procedure ==
Beispiel für eine Prozedure in einer imperativen Programmierumgebung
[[Bild:Prozeduren.JPG]]
Aufruf der Prozedur im Hauptprogramm
[[Bild:Prozeduren_2.JPG]]
''hier ein Beispiel für die Syntax im WIKI''
<code id="4b96b9dd4f206">
procedure dreieck(a,b,c:real; var erg:string);
begin
if (a*a+b*b=c*c) then erg:='ja'
else erg:='nein';
end;
</code>
<eval id="4b96b9dd53085">
var erg: string;
begin
dreieck(4,3,5.2,erg);
writeln(erg);
end.
</eval>
Neujahrswünsche in Pascal:
<code id="4b96b9dd501a5">
var i:integer;
begin
for i:= 1 to 9 do
begin
writeln('Alles Gute am Tag '+inttostr(i)+'.');
i:=i+1;
end;
end.
</code>
<eval id="4b96b9dd54025"></eval>
'''Die folgenden Übungsaufgaben dienen der Festigung des Umgangs mit den algorithmischen Grundstrukturen.'''
1. Entwickle einen Algorithmus für die Berechnung der Summe der ersten n natürlichen Zahlen.
Setze diesen in Pascal um.
<code id="4bcecd8d173af">
function summe_erste_n(
</code>
<eval id="4bcecd8d1833c">
begin
writeln(inttostr(summe_erste_n(5)));
end.
</eval>
2. Übertrage diesen Algorithmus auf die Berechnung einer Fakultät!
<code id="4bced86215c2c">
function fak_n(
</code>
<eval id="4bced86216bbc">
begin
writeln(inttostr(fak_n(5)));
end.
</eval>
3. Gegeben ist folgendes Struktogramm. Implementiere den damit dargestellten Algorithmus in der nachfolgenden Box als function ''xyz'' und <br>
teste ihn mit den Werten x = 5, y = 8 und z = 3.
Erläutere die Bedeutung der Variablen.<br>
]
[[Bild:Struktogramm(v2).JPG]]
<code id="4bd7d28b3879b">
function xyz(
</code>
<eval id="4bd7d28b3972d">
begin
writeln(inttostr(xyz(...)));
end.
</eval>
'''Eine Funktion gibt nur einen Wert (a oder b) zurück.'''<br><br>
Daher nun diesen Algorithmus als procedure schreiben.
<code id="4bd80bd03dbb3">
procedure xyz(
</code>
<eval id="4bd80bd03eb3a">
begin
writeln(...);
end.
</eval>
4. Abschließend soll ein Programm geschrieben werden, das entscheidet, ob eine quadratische Funktion keine, genau eine oder genau zwei Nullstellen besitzt. Die Werte dieser Nullstellen sind auszugeben.
<br>
''vorher Algorithmus formulieren und z.B. Struktogramm entwerfen!''
<code id="4bd8132f80684">
</code>
<eval id="4bd8132f813eb">
begin
writeln(...);
end.
</eval>
Bei einer Mathematikolympiade wurde folgende Aufgabe gestellt:
''20 m Stoff werden auf einen Stab von 5 cm Durchmesser aufgewickelt.''<br>
''Der Stoff ist 1 mm dick.''
''Wie dick wird die Rolle?''<br><br>
Eine Realisierung des Sachverhalts als Programm könnte folgendermaßen aussehen:
<code id="4bde843d4f91a">
function dick:real;
var d, l:real;
begin
l:=0;
d:=0.05;
repeat
l:=l+pi*d;
d:=d+0.002;
until l>=20;
result:=d
end;
</code>
<eval id="4bde843d508a4">
begin
writeln(floattostr(dick));
end.
</eval>
'''Modifizieren Sie den Quelltext.'''<br>
Verwenden Sie anstelle ''repeat-until'' eine Schleife mit vorangestellter Bedingung.
<code id="4bde84feb8f27">
function dick2:real;
var d, l:real;
begin
....
end;
</code>
<eval id="4bde84feb9e7b">
begin
writeln(floattostr(dick2));
end.
</eval>
<font color="darkgreen">Sie werden festgestellt haben, dass unsere Lösung für die Problemstellung keinem Algorithmus entspricht. Es wird lediglixch ein konkretes Problem durch Programmierung gelöst!</font>
<br>
<font color="darkgreen">'''Die Aufgabe wird im Folgenden also verallgemeinert. Der aufzustellende Algorithmus löst dann eine Klasse gleichartiger Probleme, wobei die Abarbeitung abhängig von den Eingaben eindeutig, endlich erfolgt und unter gleichen Bedingungen zum gleichen Ergebnis führt.'''</font>
'''''Stoff beliebiger Länge wird auf einen Stab mit beliebigem Durchmesser aufgewickelt.''<br>'''
'''''Der Stoff ist beliebig dick.'''''
'''''Wie dick wird die Rolle?''<br><br>'''
<code id="4bde8752380e9">
function dick3(...):real;
begin
....
end;
</code>
<eval id="4bde875239072">
begin
writeln(floattostr(dick3(...)));
end.
</eval>
== Zufallszahlen ==
=== Erzeugen von Zufallszahlen ===
''zunächst als function, die aufgerufen wird:''
<code id="4be10a7306816">
function zufall(a:integer):integer;
begin
result:=random(a);
end;
</code>
<eval id="4be10a1ebb218">
begin
writeln(inttostr(zufall(100)));
end.
</eval>
''andere, kürzere Variante:''
<eval id="4be1207f5f5c1">
begin
writeln(inttostr(random(100)));
end.
</eval>
'''''Ist diese Variante für Programme praktikabel?'''''
=== Würfeln ===
Simulieren Sie ein Würfelspiel mit einem idealen Würfel.
Für eine Anzahl <math>n</math> von Würfen soll die Anzahl der geworfenen Augenzahlen ausgegeben werden.
<code id="4bf2b9d35501b">
</code>
<eval id="4bf2b9d356f46">
</eval>
Formulieren Sie anhand der Simulation eine Aussage über große Zahlen und die Wahrscheinlichkeit. ("Gesetz der großen Zahlen")
<font color="darkgreen">'''''zum Weiterarbeiten:'''''</font> Zeigen Sie durch eine analoge Simulation, dass die Zufallsgröße "[[Augensumme beim Würfeln mit zwei idealen Würfeln]]" nicht gleichverteilt ist.
<br><br><br>
procedure wuerfelsumme(n:integer;var z,d,v,f,s,si,a,ne,ze,e,zw:integer);
var i,zz1,zz2,sum:integer;
begin
z:=0;d:=0;v:=0;f:=0;s:=0;si:=0;a:=0;ne:=0;ze:=0;e:=0;zw:=0;
for i:=1 to n do
begin
zz1:=random(6)+1;
zz2:=random(6)+1;
sum:=zz1+zz2;
if sum=2 then z:=z+1;
if sum=3 then d:=d+1;
if sum=4 then v:=v+1;
if sum=5 then f:=f+1;
if sum=6 then s:=s+1;
if sum=7 then si:=si+1;
if sum=8 then a:=a+1;
if sum=9 then ne:=ne+1;
if sum=10 then ze:=ze+1;
if sum=11 then e:=e+1;
if sum=12 then zw:=zw+1;
end;
end;
== Der Datentyp Feld (Array) ==
Neben den einfachen Datentypen gibt es auch zusammengesetzte, z.B. Felder (auch Listen, Array).
In einem Array werden Werte gleichen Datentyps gespeichert.
Die Deklaration eines Arrays erfolgt folgendermaßen:
var xyz: ''array''[startindex .. endindex] ''of'' Datentyp;
startindex..endindex gibt den Bereich zwischen Startwert und Endwert angeben (Randwerte werden mit eingeschlossen).
Dies entspricht dem bereitgehaltenen Speicherplatz.
Über den Index (meist mit <math>i</math> bezeichnet) kann man auf die einzelnen Werte zugreifen.
var beispiel: ''array''[0..20] ''of'' integer;
Ein Feld wird über den Index gefüllt, z.B. für <math>i=1</math> und <math>i=5</math> so:
beispiel[1]:=3;
beispiel[5]:=22;
Das Feld sei dann z.B. so gefüllt ist: [10,3,6,7,9,22,...].<br>
''Bestimmen Sie die Werte, die dann die Variablen <math>a</math> und <math>b</math> nach den folgenden Anweisungen liefern!''
a:=beispiel[0];
b:=beispiel[2];
'''weitere Hinweise z.B. unter [http://www.delphi-treff.de/object-pascal/komplexe-datentypen/]'''
== Beispiele zu Feldern ==
=== Zufallszahlen und Felder ===
<code id="4bf2b9d355fac">
function zufall2(a:integer):integer;
begin
result:=random(a);
end;
</code>
<eval id="4bf2b9d357ee5">
var z:array[0..10] of integer;
var i:integer;
begin
for i:=0 to 5 do
begin
z[i]:=zufall2(100);
writeln(inttostr(z[i]));
end;
end.
</eval>
<font color="darkgreen">'''''zum Weiterarbeiten:'''''</font> Füllen Sie ein [[Feld mit 5 zufälligen Zahlen]]. Bestimmen Sie die Position (Index) des Maximums. Lassen Sie sich zur Kontrolle die Zufallszahlen anzeigen.
var feld:array[0..4]of integer;
var i,max,index:integer;
begin
max:=0;index:=0;
for i:=1 to 5 do feld[i-1]:=random(100);
for i:=1 to 5 do
if feld[i-1]>max then begin
max:=feld[i-1];
index:=i;
end;
for i:=1 to 5 do writeln(inttostr(feld[i-1]));
writeln('Maximum an Position '+inttostr(index));
end.
=== Hofstadter-Funktion ===
Eine sehr interessante, aber äußerst undurchsichtige Folge natürlicher Zahlen wird durch die Hofstadter-Funktion beschrieben:
<math>h(n) = h(n - h(n - 1) ) + h(n - h(n - 2) )</math> für <math>n > 2</math> mit <math>h(1) = h(2) = 1</math>
''(aus: Douglas R. Hofstadter:"Gödel, Escher, Bach: an eternal golden braid" (1979) - ein Beispiel für eine chaotische Zahlenfolge, die aber doch gesetzmäßig erzeugt wird)
''
<eval id="4bf2f8b405adc">
var hf:array[0..50] of integer;
var j,k:integer;
begin
k:=15;
hf[1]:=1;
hf[2]:=1;
for j:=3 to k do hf[j]:=hf[j-hf[j-1]]+hf[j-hf[j-2]];
for j:=1 to k do write(inttostr(hf[j])+' ');
end.
</eval>
Variieren Sie die Werte für <math>k</math> sowie den endindex des Feldes.<br>
'''''Verdeutlichen Sie sich die Abarbeitung des Quell-Codes anhand eines Ablaufplanes!'''''
== Definition ==
'''Iteration''' bezeichnet das wiederholte Durchlaufen von Anweisungen. Typischerweise wird dabei mitgezählt, wie oft die jeweilige Aktion erledigt wird. Wir kennen dafür die Sprachkonstrukte ''for..to..do, while..do, repeat..until''.
Bei einer '''Rekursion''' erfolgt die Definition eines Problems, einer Funktion oder eines Verfahrens "durch sich selbst". Es handelt sich also wieder um eine Wiederholung, aber <u>ohne Schleife</u>!
Das Ergebnis eines Verfahrens für die Eingabe <math>x</math> wird auf das Ergebnis des gleichen Verfahrens für eine Eingabe <math>y</math> zurückgeführt, das Ergebnis des Verfahrens für die Eingabe <math>y</math> wird wiederum auf das Ergebnis des Verfahrens für eine Eingabe <math>z</math> zurückgeführt, usw.<br>
'''<u>Dabei muss mindestens für einen Wert das Ergebnis des Verfahrens bekannt sein!</u>'''
== Beispiele ==
=== Hofstadter ===
<math>h(n) = h(n - h(n - 1) ) + h(n - h(n - 2) )</math> für <math>n > 2</math> mit <math>h(1) = h(2) = 1</math>
==== iterativ ====
<eval id="4bfc2770153da">
var hf:array[0..50] of integer;
var j,k:integer;
begin
k:=15;
hf[1]:=1;
hf[2]:=1;
for j:=3 to k do hf[j]:=hf[j-hf[j-1]]+hf[j-hf[j-2]];
for j:=1 to k do write(inttostr(hf[j])+' ');
end.
</eval>
==== rekursiv ====
<code id="4bfc2e9e97b1f">
function hof(k:integer):integer;
begin
if k<3 then result:=1
else result:=hof(k-hof(k-1))+hof(k-hof(k-2))
end;
</code>
<eval id="4bfc2a6c95b51">
var n,i:integer;
begin
n:=5;
for i:=1 to n do write(inttostr(hof(i))+' ');
end.
</eval>
=== Fakultät ===
==== iterativ ====
<code id="4bfc2e9e98aa7">
function fak_it(n:integer):integer;
var ergebnis:integer;
begin
ergebnis:=1;
while n>1 do begin
ergebnis:=n*ergebnis;
n:=n-1;
end;
result:=ergebnis;
end;
</code>
<eval id="4bfc2e9e99a45">
begin
writeln(inttostr(fak_it(3)));
end.
</eval>
Abarbeitung für n=4:
<table width="20%" border="1" cellpadding="0" cellspacing="2">
<tr>
<td><b><p align="center">n</p></b></td>
<td><b><p align="center">Ergebnis</p></b></td>
</tr>
<tr>
<td><p align="center"></p></td>
<td><p align="center">1</p></td>
</tr>
<tr>
<td><p align="center">4</p></td>
<td><p align="center">4</p></td>
</tr>
<tr>
<td><p align="center">3</p></td>
<td><p align="center">12</p></td>
</tr>
<tr>
<td><p align="center">2</p></td>
<td><p align="center">24</p></td>
</tr>
<tr>
<td><p align="center">1</p></td>
<td><p align="center">24</p></td>
</tr>
</table>
==== rekursiv ====
<code id="4bfc25fb313c1">
function fak_rek(n:integer):integer;
begin
if n=0 then result:=1
else result:=n*fak_rek(n-1);
end;
</code>
<eval id="4bfc25fb32039">
begin
writeln(inttostr(fak_rek(3)));
end.
</eval>
Abarbeitung für n=4:
Aufruf <math>fak</math>_<math>rek(4):=4*fak</math>_<math>rek(3)</math>;
danach "Abstieg in die Rekursionstiefe":
<math>fak</math>_<math>rek(4):=4*fak</math>_<math>rek(3)</math>;
<math>fak</math>_<math>rek(3):=3*fak</math>_<math>rek(2)</math>;
<math>fak</math>_<math>rek(2):=2*fak</math>_<math>rek(1)</math>;
<math>fak</math>_<math>rek(1):=1*fak</math>_<math>rek(0)</math>;
Für n=0 liefert das Verfahren den bekannten Wert 1.<br>
Der rekursive "Aufstieg" liefert dann:
<math>fak</math>_<math>rek(1):=1*1=1</math>;
<math>fak</math>_<math>rek(2):=2*1=2</math>;
<math>fak</math>_<math>rek(3):=3*2=6</math>;
<math>fak</math>_<math>rek(4):=4*6=24</math>;
=== Aufgabe ===
Schreiben Sie eine rekursive Funktion, die die Summe der ersten n Zahlen berechnet!
<code id="4bfc351cd8698">
function su_rek(n:integer):integer;
begin
end;
</code>
<eval id="4bfc358dbd4fe">
begin
writeln(inttostr(su_rek(3)));
end.
</eval>
passende Iteration vergleiche [[Übungsaufgaben]]
=== Potenz ===
Schreibe passende Funktionen für die Berechnung einer Potenz!
==== iterativ ====
<code id="4c06367e1e836">
</code>
<eval id="4c06367e2075e">
</eval>
==== rekursiv ====
<code id="4c06367e1f7c4">
</code>
<eval id="4c06367e216fb">
</eval>
=== Die Fibonaccizahlen ===
'''Leonardo Fibonacci di Pisa''' (* um 1180; † 1241) beschrieb die Fortpflanzung von Kaninchen mit der Zahlenfolge:
<blockquote><math>1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...</math></blockquote>
'''Definition:'''
<blockquote>
<math>\mbox{fib}(n)=\begin{cases}1,\mbox{wenn}\hspace{0.3em}n=1\\1,\mbox{wenn}\hspace{0.3em}n=2\\\mbox{fib}(n-1)+\mbox{fib}(n-2),\mbox{sonst}\end{cases}</math>
</blockquote>
'''Beschreibung:'''
''Die Kaninchenpaar bekommt nach zwei Monaten Nachwuchs (Pärchen!), dies dann jeden Monat. Die "Kinderpaare" verhalten sich genauso. Die Kaninchen leben "unendlich lange".''
Das bedeutet:
* Die ersten beiden Glieder der Zahlenfolge sind jeweils 1.
* Jedes weitere Glied ergibt sich aus der Summe seiner beiden Vorgänger.
'''''Prüfen!'''''
siehe auch [http://www.ijon.de/mathe/fibonacci/index.html]
==== iterativ ====
Zunächst eine iterative Version:
<code id="4c0ea67f79b09">
function fibo_it(n:integer):int64;
var f1,f2:int64;
begin
result := 1;
f1 := 1;
f2 := 1;
for n := 3 to n do
begin
result := f1 + f2;
f1 := f2;
f2 := result;
end;
end;
</code>
<eval id="4c0ea67f7aa92">
begin
writeln(inttostr(fibo_it(4)));
end.
</eval>
==== rekursiv ====
Schreiben Sie nun eine rekursive Funktion gemäß der oberen Beschreibung:
<code id="4c0ea8075d98e">
function fibo_rek(n:integer):integer;
begin
end;
</code>
function fibo_rek(n:integer):integer;
begin
if (n=1) or (n=2) then result:=1
else result:= fibo_rek(n-1)+fibo_rek(n-2);
end;
<eval id="4c0ea8075e91c">
begin
write(inttostr(fibo_rek(3)));
end.
</eval>
<check>
result := (fibo_rek(3) = 2) and (fibo_rek(6) = 8);
</check>
=== Ackermann-Funktion ===
Die Ackermann-Funktion folgendermaßen definiert:
'''Definition:'''
<blockquote>
<math>Ack(0, y)=y+1</math><br>
<math>Ack(n + 1, 0) = Ack(n, 1)</math><br>
<math>Ack(n +1, y+1) = Ack(n, Ack(n + 1, y))</math>
</blockquote>
<br>
Informationen zur Ackermann-Funktion unter [http://de.wikipedia.org/wiki/Ackermannfunktion]
Stellen Sie die rekursiven Aufrufe für <math>ack(3,1)</math> dar!
Implementieren Sie eine rekursive Funktion:
<code id="4c0f6e18175fc">
</code>
<eval id="4c0f6e181859e">
</eval>
''iterativ''
<code id="4f62575bc4cbf" hidden><code id="4f62575bc4e1e">
function ack_it(n, m:integer):integer;
begin
while n<>0 do
begin
if m = 0 then m := 1
else m := ack_it(n, m - 1);
n := n - 1;
end;
end;
</code>
<code id="4f62575bc4fb4" hidden><eval>
begin
writeln(inttostr(ack_it(2,2)));
end.
</eval></code>
== Zusammenfassung ==
'''Rekursion bietet sich dann an, wenn man ein gestelltes Problem durch eine Funktion schrittweise in ein etwas einfacheres Problem umwandeln kann.'''
'''typischer Aufbau einer rekursiven Funktion'''
* 1. <math>if</math>-Befehl, der das Ende der Selbstaufrufe bestimmt
* 2. ein Aufruf der Funktion selbst
'''Nachteile der Rekursion'''
* 1. Jeder Aufruf kostet Zeit - Rekursion prinzipiell langsamer als Iteration
* 2. jeder Aufruf kostet Speicherplatz - viel Speicher im Stack (Speicherstapel)
Jede Iteration kann als Rekursion formuliert werden, jede Rekursion als Iteration (teilweise schwierig).
Rekursionen werden durch den Compiler bzw. Interpreter der Programmiersprache aufgelöst - der PC-Prozessor arbeitet iterativ.
== Vorbemerkungen ==
Das Sortieren (und Suchen) ist in der Informatik umfassend untersucht worden, weil Sortieralgorithmen in zahlreichen Anwendungen verwendet werden (Datenbanken, Compiler, Betriebssysteme etc.).
Grundsätzlich gibt es drei Methoden zum Sortieren:
* Auswählen
* Einfügen
* Austauschen
Wir besprechen diese Verfahren an Hand des Sortierens von Spielkarten: Beim Auswählen breitet man die Karten auf dem Tisch aus und wählt die niedrigste Karte.
Anschließend wird die nächste Karte gewählt und hinter die niedrigste gereiht, usw. Beim Sortieren durch Einfügen hält man die Karten in der Hand, nimmt jeweils die nächste
und fügt sie in einen am Tisch liegenden Stapel so ein, dass sie jeweils an der richtigen Stelle zu liegen kommt. Die Karten sind sortiert, sobald man keine Karte mehr in der
Hand hält. Um die Karten durch Austauschen zu sortieren, breitet man die Karten in beliebiger Reihenfolge auf dem Tisch aus und tauscht dann die falsch liegenden Karten
solange aus, bis der Satz geordnet ist.
Für die "Güte" eines Sortieralgorithmus sind folgende Kriterien ausschlaggebend:
1. Wie schnell sortiert der Algorithmus durchschnittlich Informationen?
2. Wie schnell ist er im günstigsten und ungünstigsten Fall?
3. Verhält sich der Algorithmus natürlich (d.h. hat er bei gut sortierten Listen wenig und bei ziemlich ungeordneten
Listen viel zu tun)?
4. Ordnet er Elemente mit gleichen Schlüsseln um?
Sortieralgorithmen bieten sich als grundlegendes Thema für die Analyse von Algorithmen an.
== Sortieren durch Auswählen (Minimumsuche) ==
Die Idee einer der einfachsten Sortieralgorithmen ist die folgende: Finde zunächst das kleinste Element im Datenfeld und tausche dieses gegen das an der ersten Stelle
befindliche Element aus. Anschließend finde das zweitkleinste Element, tausche es gegen das zweite Element aus ... usw.
Diese Sortiermethode ist für kleine Dateien sehr gut brauchbar. Zu beachten ist, dass jedes Element tatsächlich nur einmal getauscht wird.
<b>Prinzip: Aus einer Menge wird das kleinste Elelment ausgewählt und mit dem ersten Element vertauscht.
Diese Vorgänge werden wiederholt ,wobei die Anzahl der Elemente bei jeder Wiederholung von vorn um eins verringert wird.
Zuletzt werden nur noch zwei Elemente überprüft und gegebenenfalls vertauscht.</b>
<table border="1" cellpadding="5" cellspacing="2">
<tr>
<td>[[Bild:Auswaehlen2.JPG]]</td>
<td>unsortiertes Feld<br><br><br><br><br><br>36 mit 99 vertauscht,
anschließend kleinstes Element<br> des Restfeldes (roter Pfeil) mit 99 vertauscht<br><br><br><br><br><br><br><br>
77 mit 99 vertauscht,
anschließend kleinstes Element<br> des Restfeldes mit 99 vertauscht...
</td>
<td>[[Bild:Auswaehlen4.JPG]]</td>
</tr>
</table>
'''''Implementiert könnte dies so aussehen: '''''
<eval id="4c1b17ab54d27">
var z:array[0..7] of integer;
var i,j,k,h:integer;
begin
for i:=0 to 7 do
begin
z[i]:=random(20)+1;
write(inttostr(z[i])+' ');
end;
for i:=0 to 7 do
begin
k:=i;
for j:=i to 7 do
if z[j]<z[k] then k:=j;
h:=z[i];
z[i]:=z[k];
z[k]:=h;
end;
writeln('');
writeln('');
for i:=0 to 7 do write(inttostr(z[i])+' ');
end.
</eval>
== Sortieren durch Einfügen ==
<b>Prinzip: Man wählt ein Element (nacheinander vom zweiten bis zum letzten) und fügt es jeweils an die richtige
Stelle der davorstehenden geordneten Teilmenge ein. </b>
<table border="1" cellpadding="5" cellspacing="2">
<tr>
<td>[[Bild:Einfuegen2.JPG]]</td>
<td>unsortiertes Feld; zweites Element herausgenommen und <br>vor dem Ersten eingefügt
<br><br><br><br><br>sechstes Element genommen und als viertes eingefügt,<br>
dabei werden viertes und fünftes (alt) neues<br> fünftes und sechstes Element
<br><br><br><br><br><br>
Letztes Element an die richtige Stelle,
Feld vollständig sortiert
</td>
<td>[[Bild:Einfuegen4.JPG]]</td>
</tr>
</table>
Implementieren Sie das ''Sortieren durch Einfügen'' analog zum Sortieren durch Auswählen!
<eval id="4c1b265b1e11e">
</eval>
== Sortieren durch Austauschen (Bubblesort) ==
Dieses Sortierverfahren wird häufig erklärt, obwohl es wahrscheinlich das ungünstigste Sortierverfahren darstellt, das jemals realisiert worden ist: Durchlaufe immer wieder das
Feld und vertausche jedesmal, wenn es notwendig ist, benachbarte Elemente. Die Datei ist sortiert, wenn kein Austausch mehr notwendig ist.
Der Algorithmus erhält seinen Namen von der Tatsache, dass die Elemente - ähnlich wie Blasen im einem Glas Mineralwasser - aufsteigen, bis sie an der richtigen Stelle sind.
<b>Prinzip: Vom letzten Element einer Menge an werden jeweils zwei benachbarte Elemente verglichen und ausgetauscht, wenn
sie falsch sortiert sein sollten. Dabei wandert da kleinste Element an die erste Stelle.
Das Vergleichen und Austauschen wird mit Ausnahme dieses bereits richtig postierten Elements wiederholt.
Das Sortieren kann aufsteigend (links nach rechts) oder absteigend (umgekehrt) erfolgen.</b>
<table border="1" cellpadding="5" cellspacing="2">
<tr>
<td>[[Bild:Austauschen2.JPG]]</td>
<td><br><br>unsortiertes Ausgangsfeld,<br><br>
die 83 ist falsch sortiert und wird bis zum Feldindex,<br> der einen Wert größer als 83 enthält, verschoben,
anschließend wird<br> die 97 und die 32 vertauscht, wonach die 97 als größte Zahl des<br> Feldes als erste an der richtigen Stelle steht.<br><br>Das Vergleichen beginnt wiederum von vorn, wobei die Zahlen<br> 64 und 41 sowie 90 und 32 vertauscht werden.<br>
Die 90 steht damit als zweite Zahl an der richtigen Stelle.
<br><br><br>
Anschließend wird die 32 nach links durchgereicht<br> und das Feld ist vollständig sortiert.
</td>
<td>[[Bild:Austauschen4.JPG]]</td>
</tr>
</table>
Implementieren Sie ''Bubblesort'' analog zum Sortieren durch Auswählen!
<eval id="4c1f0917ac95b">
</eval>
== Quicksort ==
Das Sortieren durch Minimumsuche (''MinSort'') ist nicht sehr effizient.<br />
Wir betrachten deshalb den nachfolgenden Algorithmus und implementieren ihn.
'''Beschreibung:'''
* Benutze das erste Element einer (numerischen) Liste als Trennelement.
* Erzeuge zwei Teillisten, deren Elemente kleiner bzw. größer als das Trennelement sind.
* Setze dieses Verfahren für jede nichtleere Teilliste fort und
* füge die sortierten Teillisten zur Gesamtliste zusammen.
Den so beschriebenen Sortieralgorithmus bezeichnet man als ''QuickSort'' (schnelles Sortieren). Er wurde 1962 von dem britischen Informatiker Sir '''Charles Antony Richard Hoare''' (* 11. Januar 1934) vorgestellt.
{| border="1"
|-
| '''Prinzip''' || '''Quelltext''' in Pascal || ||
|-
| [[Bild:QuickSort-Beispiel1.gif]] || [[Bild:Quicksort_2.JPG]] || [[Datei:Hoare.jpg|miniatur|C.A.R. Hoare]]
|}
<code id="4f62587ed09ad" hidden>
procedure QUICK_SORT(lowerBound, upperBound: Integer);
var i, j, KEY, X, Y:Integer;
B: boolean;
k: array[1..1000] of integer;
begin
B := true;
If (lowerBound < upperBound) Then
begin
i := lowerBound;
j := upperBound + 1;
KEY := K[lowerBound];
while B do
begin
i := i + 1;
while (K[i] < KEY) AND (i>upperBound) do i := i + 1;
j := j - 1;
while K[j] > KEY do j := j - 1;
If i < j then
begin
X := K[i];
K[i] := K[j];
K[j] := X;
end
else B := false;
end;
Y := K[lowerBound];
K[lowerBound] := K[j];
K[j] := Y;
QUICK_SORT(lowerBound,j - 1);
QUICK_SORT(j + 1, upperBound);
end;
end;
</code>
Der Algorithmus arbeitet nach dem Prinzip '''''Teile und Herrsche'''''.<br />
weitere Informationen unter: [http://www.inf.fh-flensburg.de/lang/algorithmen/sortieren/quick/quick.htm]
== Literatur ==
* Fahldieck, Karl-Heinz: Algorithmen, Frankfurt am Main: Verlag Moritz Diesterweg, 1993
* Sedgewick, Robert: Algorithmen, Bonn:Addison-Wesley Publishing Company, 1992
* Hermann, Dietmar: Algorithmen Arbeitsbuch, Bonn; München; Paris, Addison-Wesley Publishing Company, 1992
* Junger, Hans u.a.: Informatik, Frankfurt am Main; Aarau, Verlag Moritz Diesterweg; Verlag Sauerländer AG, 1988
== Praktisch unlösbare Probleme ==
=== Schachcomputer ===
Es hat viele Jahre gedauert, ehe mit enormem Aufwand ein Schachprogramm vorgelegt werden konnte, dass sich mit einem Weltklassespieler messen konnte.<br />
Dabei ist der erforderliche Algorithmus einfach:<br />
Erzeuge zu jedem Zug des Gegners ''alle'' nach den Spielregeln mögliche Gegenzüge. Danach erzeuge ''alle'' Antwortzüge des Gegners usw.<br />
Unter der Annahme, dass es in jeder Stellung nur 5 Fortsetzungsmöglichkeiten für den nächsten Spielzug gibt, ein Spiel im Mittel aus 60 Zügen (120 Halbzügen) besteht und zur Speicherung jedes Zustandes nur ein Byte gebraucht wird, würde der gesamte Speicherbedarf
<blockquote>
<math>5^0+5^1+5^2+ ... +5^{120} = 1 \cdot \frac{5^{121}-1}{5-1} \approx 9.404 \cdot 10^{83} \mbox{Byte}</math>
</blockquote>
betragen. Zumindest in den nächsten Jahren wird es nicht gelingen, den kompletten "Schachbaum" zu speichern. Der gewaltige Aufwand an Rechenzeit und Speicher verhindert eine ''praktische'' Realisierung.
=== Ackermannn-Peter-Funktion ===
siehe [[http://ux-i-programmingwiki.inf.hs-zigr.de/index.php/Iteration_und_Rekursion#Ackermann-Funktion]]<br>
Es ist möglich, algorithmisch prinzipiell lösbare Probleme anzugeben, die auch von zukünftigen "Supercomputern" nicht bewältigt werden können. Ein Beispiel ist die ''Ackermann-Peter-Funktion'', benannt nach dem deutschen Mathematiker '''Wilhelm Friedrich Ackermann''' (* 29. März 1896; † 24. Dezember 1962) und der ungarischen Mathematikerin '''Rózsa Péter''' (* 17. Februar 1905; † 16. Februar 1977):
Dabei handelt es sich um eine extrem schnell wachsende Funktion, die für die ''Klassifikation berechenbarer Funktionen'' eine große Bedeutung besitzt.<br />
Die nachfolgende Tabelle veranschaulicht einige Funktionswerte:
<table border="1" cellspacing="1" cellpadding="4">
<tr>
<th>n \ m</th><th width="50">0</th><th width="50">1</th><th width="50">2</th width="50">
<th width="50">3</th><th width="50">4</th><th width="50">5</th><th width="50">...</th>
</tr>
<tr align="center">
<th>0</th><td>1</td><td>2</td><td>3</td><td>4</td><td>5</td><td>6</td><td>...</td>
</tr>
<tr align="center">
<th>1</th><td>2</td><td>3</td><td>4</td><td>5</td><td>6</td><td>7</td><td>...</td>
</tr>
<tr align="center">
<th>2</th><td>3</td><td>5</td><td>7</td><td>9</td><td>11</td><td>13</td><td>...</td>
</tr>
<tr align="center">
<th>3</th><td>5</td><td>13</td><td>29</td><td>61</td><td>125</td><td>253</td><td>...</td>
</tr>
<tr align="center">
<th>4</th><td>13</td><td>65533</td><td>...</td><td>...</td><td>...</td><td>...</td><td>...</td>
</tr>
<tr align="center">
<th>5</th><td>65533</td><td>...</td><td>...</td><td>...</td><td>...</td><td>...</td><td>...</td>
</tr>
<tr align="center">
<th>...</th><td>...</td><td>...</td><td>...</td><td>...</td><td>...</td><td>...</td><td>...</td>
</tr>
</table>
Bereits der Funktionswert von <tt>(ack 4 2)</tt> besitzt 19729 Dezimalstellen!<br />
Sollte mit einem Computer die Berechnung <tt>(ack n m)</tt> möglich sein, so wird es immer einen Funktionswert <tt>(ack (+ n 1) (+ m 1))</tt> geben, dessen Berechnung nicht mehr möglich ist. Es gibt also objektive ''Grenzen bei praktischen Problemlösungen''.
== P-Probleme und NP-Probleme ==
Problemen sieht man im Allgemeinen nicht an, ob sie bezüglich ihres Zeitaufwands schwer oder leicht lösbar sind.<br />
Mitunter führt eine geringe Abweichungen in der Formulierung vergleichbarer Problemstellungen dazu, dass der Zeitaufwand zur Lösung fundamental verschieden ist, z.B.:
<table border="1" cellspacing="1" cellpadding="4">
<tr>
<th width="300">leicht, d.h. in <math>\mathcal{O}(n^k),k \ge 1</math></th>
<th width="300">schwer, d.h. in <math>\mathcal{O}(k^n),k > 1</math></th>
</tr>
<tr>
<td>
Finde den ''kürzesten'' Weg zwischen zwei Orten A und B in einem Straßennetz mit angegebenen Entfernungen.
</td>
<td>
Finde den ''längsten'' Weg zwischen zwei Orten A und B in einem Straßennetz mit angegebenen Entfernungen.
</td>
</tr>
</table>
Die Klasse der leichten Probleme heißen ''P-Probleme''. Als ''NP-Probleme'' bezeichnet man schwere Probleme.
'''P''' ist die Klasse von Problemen, die mit ''deterministischen'' (siehe [[http://ux-i-programmingwiki.inf.hs-zigr.de/index.php/Algorithmen_I#Eigenschaften_von_Algorithmen]]) Algorithmen in ''polynomialer'' Zeit gelöst werden können.<br />
Die Klasse der '''NP'''-Probleme ist die Menge aller Probleme, die ''nichtdeterministisch'' in Polynomialzeit gelöst werden können.
Wie muss man sich eine nichtdeterministische Problemlösung vorstellen?<br />
* '''1. Schritt:''' Der Algorithmus "errät" einen Lösungskandidaten.
* '''2. Schritt:''' Der Algorithmus verifiziert, ob der Kandidat tatsächlich eine Lösung ist.
Beide Schritte erfordern einen polynomialen Zeitaufwand.<br />
Jedes Problem aus P liegt auch in NP.
Es konnte aber bisher nicht gezeigt werden, dass es ein Problem gibt, das nachweislich zu NP aber nicht zu P gehört.<br />
Damit ist offen, ob
<blockquote><math>\mbox{P}=\mbox{NP}</math> oder <math>\mbox{P}\subset\mbox{NP}</math></blockquote>
gilt. An die Äquivalenz beider Klassen glaubt allerdings niemand.
<br><br>
'''NP-vollständige Probleme'''
Es gehört zu den herausragenden Leistungen der theoretischen Informatik, die schwersten Probleme zu einer separaten Klasse mit folgender Eigenschaft zusammenfassen zu können: Diese Probleme können in polynomialer Zeit ineinander überführt werden. Probleme dieser Klasse heißen ''NP-vollständig''.<br />
Sollte es je gelingen, einen effizienten (d.h. deterministisch polynomialen) Lösungsalgorithmus für ''ein'' Problem dieser Klasse zu finden, lassen sich auf einen Schlag ''alle'' Probleme dieser Klasse effizient lösen.<br />
Derzeit sind mehr als 1000 NP-vollständiger Probleme bekannt. Dass es bisher nicht gelungen ist, einen effizienten Lösungsalgorithmus zu finden, spricht für die Vermutung <math>\mbox{P}\subset\mbox{NP}</math>.
'''Einige Beispiele für NP-vollständige Probleme:'''
[[Bild:Rucksack1.gif|miniatur|Rucksackproblem]]
<ul>
<li>'''Rucksackproblem:'''<br />
Verschiedene Gegenstände sind mit ihrem Gewicht und ihrem Nutzwert gegeben. Eine Auswahl soll in einen Rucksack mit vorgegebenem Maximalgewicht gepackt werden, so dass der Gesamtwert der eingepackten Gegenstände maximal wird.<br>
Interessante [http://www.math-it.de/Mathematik/OR/Rucksack_de.html Visualisierung] ausprobieren. <br>
Anzahl der Gegenstände schrittweise erhöhen!<br>
Auf Bedeutung der Spalten achten!
</li>
<li>'''Stundenplanproblem:'''<br />
Eine Zuordnung von Klassen und Fachlehrern zu Unterrichtsräumen und -zeiten soll so vorgenommen werden, dass eine möglichst große Zahl an vorgegebenen Nebenbedingungen erfüllt wird.<br>
Diese sind:
Gütekriterien für Stundenpläne
* Minimale Anzahl von Freistunden für die Schüler.
* Die Unterrichtseinheiten finden vorzugsweise am Vormittag und am frühen Nachmittag statt und sind für Schüler gleichmässig über die Wochentage verteilt.
* Die freien Zwischenstunden für Lehrer sollten eine individuell festzulegende Anzahl nicht überschreiten. Die Anzahl der Unterrichtseinheiten pro Tag sollte so festgelegt sein, dass eine ausgewogene Aufteilung der Einheiten erreicht wird.
* Die Anzahl der Raumwechsel für Schüler sollte gering sein. Ein Wechsel zwischen entfernten Gebäudeteilen sollte höchstens einmal pro Tag erfolgen.
* Anstrengende oder ermüdende Unterrichtseinheiten (z.B. Sport) sollten für Schüler möglichst nur am Anfang oder am Ende eines Unterrichtstages geplant werden.
* Eine Klasse soll möglichst viele Unterrichtseinheiten bei ihrem Klassenlehrer bzw. in ihrem Klassenzimmer verbringen.
Die bei der Stundenplanung zwingend vorgeschriebenen Restriktionen sind teilweise komplexe Beziehungen zwischen Unterrichtseinheiten. Ein Stundenplan, der alle Restriktionen erfüllt, heisst vollständiger Plan.<br>
Bestimmungen für einen vollständigen Plan:<br>
# Eine Unterrichtseinheit kann nur zu einer Zeit stattfinden. Alle Lehrer und Gruppen, die an der Einheit beteiligt sind, und mindestens ein ihr zur Auswahl stehender Raum müssen diese Zeit zur Verfügung haben.
# Eine Veranstaltung besteht aus Blöcken. Tauscht man in einem Plan die Zeit- und Raumzuordnungen mehrerer gleich grosser Blöcke untereinander aus, so entsteht ein anderer Plan, der aber die gleichen Eigenschaften wie der Ausgangsplan besitzt.
# Lehrer und Gruppen können nicht zur gleichen Zeit an mehreren Unterrichtseinheiten teilnehmen, deshalb sind die Zeiten aller Unterrichtseinheiten eines Lehrers bzw. einer Gruppe verschieden.
# In einem Raum können zu einer bestimmten Zeit nicht mehrere Unterrichtseinheiten stattfinden, deshalb sind die Räume aller Unterrichtseinheiten, die zur gleichen Zeit stattfinden, verschieden.
sowie
# Eine Zeiteinheit kann höchstens so oft verplant werden, wie Räume diese Zeit verfügbar haben.
# Fachunterricht findet häufig in einem dafür vorgesehenen Fachraum statt (z.B. Sport). Die Zeiten der Unterrichtseinheiten, die nur in einem solchen Fachraum durchgeführt werden, sind verschieden.
</li>
<li>'''Problem des Handlungsreisenden:'''<br />
Die Reihenfolge für den Besuch mehrerer Orte so zu wählen, dass die gesamte Reisestrecke des Handlungsreisenden nach der Rückkehr zum Ausgangsort möglichst kurz ist und jeder Ort nur einmal besucht wird.<br>
hierzu: [http://www.sueddeutsche.de/wissen/mathematik-problem-not-eines-handlungsreisenden-1.588630 Beitrag der Süddeutschen Zeitung]
<br>
</li>
</ul>
== Algorithmisch unlösbare Probleme ==
Hier ein Ausblick auf ''absolut unlösbare Probleme''.
'''Das Halteproblem: ''' Das Halteproblem ist ein Problem aus der Theoretischen Informatik. Es besteht darin, in einem bestimmten Berechnungskalkül zu entscheiden, ob die Ausführung einer bestimmten Berechnungsvorschrift zu einem Ende gelangt.
<br><br>
Die Entdeckung der '''Nichtentscheidbarkeit''' des Halteproblems hatte eine erschütternde Wirkung auf das herrschende mathematische Weltbild. Man versuchte gerade, die Mathematik durch eine strikte Formalisierung zu vereinheitlichen und den Regeln der Logik zu unterwerfen. ''Man ging davon aus, dass sich jedes mathematische Problem durch eine geeignete Formalisierung lösen lässt; dass es also immer möglich sei, eine Aussage so zu formulieren, dass man durch die Regeln der Logik und Mathematik erkennen kann, ob sie wahr oder falsch ist – gesucht war also ein vollständiges und widerspruchfreies System.''<br>
Nach den Erkenntnissen von Turing (vergleiche [http://de.wikipedia.org/wiki/Alan_Turing Alan Turing] oder [http://www.matheprisma.uni-wuppertal.de/Module/Turing/index.htm Turingmaschine]) und Gödel ist so etwas jedoch grundsätzlich nicht möglich: in jedem System, das die Mächtigkeit der Arithmetik besitzt, lassen sich Aussagen formulieren, die ''weder bewiesen noch widerlegt'' werden können: solche Systeme sind grundsätzlich unvollständig. ''Oder anders ausgedrückt: es gibt Funktionen, die zwar wohldefiniert sind, deren Werte sich dennoch im Allgemeinen nicht berechnen lassen.''<br>
Das Halteproblem bedeutet nur, dass es Aufgabenstellungen gibt, die nicht mechanisch gelöst werden können. Eine Beschränkung der Mittel setzt aber keineswegs die Logik außer Kraft.
zum Weiterlesen: [http://theo.cs.uni-magdeburg.de/lehre06s/ti_iif/folien/halteproblem-naiv.pdf]
<br>
== weitere Beispiele ==
[http://www.t-und-j.de/index.php?id=46 Königsberger Brückenproblem]
<br>
[http://de.wikipedia.org/wiki/Damenproblem Damenproblem]
<br>
'''Zusammenfassung:''' [[:file:WB-PraktischeGrenzenDerBerechenbarkeit.zip|Zip_Präsentation]] von Informatik.bildung-rp.de entpacken
oder [http://www.google.de/url?sa=t&source=web&cd=4&ved=0CCgQFjAD&url=http%3A%2F%2Finformatik.bildung-rp.de%2Ffileadmin%2Fuser_upload%2Finformatik.bildung-rp.de%2FWeiterbildung%2Fpps%2FWB-PraktischeGrenzenDerBerechenbarkeit.pps&rct=j&q=stundenplanproblem&ei=YRlxTM3LCcLLswaw4YC6Bg&usg=AFQjCNGt9aZ6NsTyw5hRj8yQ84nx-ZMTyg&cad=rja pps_Präsentation] starten
Folgende Aufgaben und Fragen stellen eine Auswahl dessen dar, was wir in den letzten Monaten mit Hilfe des PWiki behandelt haben. <br>
Einige Inhalte sind auch ergänzend selbstständig zu erarbeiten!<br>
Dokumentieren Sie Ihre Antworten übersichtlich in einer <u>"eigenen"</u> PWikiSeite!
# Datentypen
## Unterscheiden Sie einfache und strukturierte Datentypen.
## Erläutern Sie die Bedeutung des Datentyps Feld anhand eines geeigneten Beipiels.
## Machen Sie sich mit den Verarbeitungsprinzipien LIFO und FIFO vertraut. Gehen Sie dabei auf die höheren Datenstrukturen Stapel und Schlange ein. Erläutern Sie das Prinzip anhand der Eingabe und Ausgabe des Wortes ''Erwin''. Beachten Sie, dass Ein- und Ausgabe zeichenweise erfolgt (E, R, W, I, N) - Datentyp?
# Unterprogramme
## Erläutern Sie die Bedeutung der Verwendung von Unterprogrammen.
## Implementieren Sie je ein Beispiel auf "Ihrer" PWikiSeite!
## Notieren Sie zu dem abgebildeten Struktogramm ein symbolisches Programm (Quelltext).<blockquote>[[Bild:Struktogramm.JPG]]</blockquote>
## In einem Unterprogramm soll geprüft werden, ob sich aus drei eingegebenen Seitenlängen ein rechtwinkliges Dreieck ergibt. Schreiben Sie eine Prozedur ''dreiecksanalyse'', die als Ausgabewert "ja" oder "nein" zurückgibt.
# Algorithmen
## Erläutern Sie Unterschiede von Iteration und Rekursion an einem Beispiel.
## Beschreiben Sie mit eigenen Worten einen Sortieralgorithmus.
## Gegeben sei ein Algorithmus zur Bestimmung des Maximums von n verschiedenen natürlichen Zahlen in einem Array A (siehe Struktogramm): <blockquote>[[Bild:Struktogramm4.JPG]]</blockquote>
##* Implementieren Sie den Algorithmus im PWiki.
##* Die Anzahl der Vergleichsoperationen sei ein Maß für das Zeitverhalten des Algorithmus.
##** Wie viele Vergleichsoperationen finden statt, wenn die Werte im Feld A lauten: [3;4;1;5;2]?
##** Wie viele Vergleichsoperationen finden bei n Werten im Feld A statt (n beliebig > 1)?
##* Die Anzahl der Wertzuweisungen in der Schleife sei ein weiteres Maß für die Komplexität dieses Algorithmus.
##** Wie viele Wertzuweisungen finden statt, wenn die Werte im Feld A lauten: [3;4;1;5;2]?
##** Wie viele Wertzuweisungen finden im ungünstigsten Fall bei n Elementen im Feld A statt?