AuK/Einführung WS13-14

Wiki-Quelltext dieser Seite.

=1. Praktische unlösbare Probleme=
 
Das ist ein Problem, für welche existiert keine Algorithmus, der nachdem endliche Schritte antworten kann, "ja" oder "nein" für dem beliebig Einzustand.

=2. Absolut unlösbare Probleme=
Am bekannste Beispiel ist Halteproblem.
Halteproblem ist wie eine Frage für Algorithmus, ob ein Program halten kann (in endliche Zeit). Die Frage kann nur die Anfangzustande betreffen oder auch alle mögliche Zustande.
Es gibt keine universelle Algorithmus, die das Halteproblem für alle Algorithmen, aber wir können nur einbilden, wie soll diese Algorithmus aussehen.
<code>
prozedur stop(programm, daten): 
  wenn programm(daten) halten sich, das
      züruck ja,
  gegebenenfalls
      züruck nein.

</code>


(mehr hier
[http://www.example.com Link-Text]
)


==Beispiel - Schachmatch und Tic Tac Toe==
Probleme mit der Auflösung können wir in verschiedene Spiele merken. Sehr gute Beispiel auf praktisch unlösbare Probleme sind Denkspiele und die künstliche Intelligenz. Dank die Baumdiagramme können wir schauen, wie Programm planen selbste nächste Schritte in Spiel. Tic Tac Toe ist nicht so ausgebaut wie z.B. Schachmatch und dank dass, wir die Baumdiagramme aus ganz Spiele vorbereiten können. Hier haben wir klein Beispiel, ein Teil aus Spiel:
[[Bild:S3makrza_Kolko.jpg]]
Das Programm sieht mögliche Auflösungen und wählt am beste in diese Situation aus. Schade, aber Situation mit Schachmatch oder Damespiel ist schon nicht so leicht. Damit alle mögliche in Schachmatch vorhersehen, brauchen wir sehr stark Computer und das ist nicht so praktisch Methode durch das. Deshalb können wir sagen dass, in Praktisch diese Problem ist unlösebare aber in Theorie ist das möglich. Programmen werden so geschrieben, um nur einige nächste Schritte in Zukunft vorherzusehen.

<language>Scheme</language>
==Beispiel - Ackermann-Peter-Funktion==
AP Funktion nutzen oft Programmierer in Testen der Qualität den Kompilatore. Auch ist gut Beispiel auf der Berechenbarkeitstheorie. Hier steht das mathematische Muster diese Funktion: 
[[Bild:S3makrza_Ackermann.png]]
Natürlich können wir auch diese Funktion in Scheme-Prozedur schreiben:
<code id="5255a07c70027">
(define ap
  (lambda (m n)
    (cond
      ((= m 0)(+ n 1))
      ((= n 0)(ap (- m 1) 1))
      (else
       (ap (- m 1)(ap m ( - n 1)))))))

</code>
<run id="5255a07c700a9">(ap 2 3)</run>

Die Ergebnis in AP Funktionen steigt sehr rapid. Für die Zahlen m=4 und n=2 beträg schon $2^{65536} - 3$.

=3. Empirische Analyse =
Die Methode für verschiedene Eingabewerte, welche nutzen wir bis Experimenten mit Algorithmen, heißt Zeitmessung. Aufgrund der Testen können wir nicht nur Effizienz aber auch, ob Programm wirklich richtig funktioniert.
Leider, wir können nicht sagen dass, auf Comuter X, Program Y brauch W Sekunden für Einzustände ABC. Deshalb ist wichtig die Beobachtung den Rechnenschritte, d.h ''Grundoperationen''.
Der funktionalen Zusammenhang beschtecht zwischen Problemgröße ''n'' und der zugehörigen Aufwand T(''n'').

'''''T(n) = f(n)'''''

z.B.:
$T(n) = r * n^{2} + k$ mit $r,k = konst, r > 0,$




Wichtig ist, dass die Werte aus welche Problemgröße nutzen, sind näturliche Zahlen größer als null.

=4. Bit-Komplexität=
Fast alle Laptops arbeiten jetzt auf Prozessoren mit 32Bit oder 64Bit. Für "normale" Nutzer ist das groß genung aber für uns (Informatiker) reicht es nicht. Die Problem ist, wenn die Einschränkung die Zeitaufwand durch Konstante ist. Sondern die Addition und Multiplikation wirken als Grundoperation, wir sprechen in diese Fall über ''uniformen Kompläxitätsmaß''.


Uniformen Komplexität nutzt von Registermaschine.

==Abrundungsfunktion und Aufrundungsfunktion (Floor and ceiling functions)==
Floor und ceiling sind Funktionen in Mathematik, die Zahlen von die reellen Zahlen bis die natürliche Zahlen runden. Floor macht das bis unter die Grenze, und ceiling bis oben die Grenze.