Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen angezeigt.
| Beide Seiten der vorigen RevisionVorhergehende ÜberarbeitungNächste Überarbeitung | Vorhergehende Überarbeitung | ||
| markow:berechenbarkeit [2017/09/04 22:33] – [Problemkategorien] Tscherter, Vincent | markow:berechenbarkeit [2024/03/03 22:36] (aktuell) – Tscherter, Vincent | ||
|---|---|---|---|
| Zeile 1: | Zeile 1: | ||
| + | ====== Berechenbarkeit ====== | ||
| + | |||
| + | - Komplexität von Algorithmen und Problemen | ||
| + | - Grenzen Aufzeigen | ||
| + | - Berechnungsmodelle | ||
| + | |||
| + | ===== Problemkategorien ===== | ||
| + | |||
| + | - O(1) - Lookup | ||
| + | - O(log n) - Binärsuche in einer Sortierten Liste | ||
| + | - O(n) - majority, max, ... | ||
| + | - O(n log n) - sortieren z.b. heap sort | ||
| + | - O(n^x) - Polynomiell -> P | ||
| + | - O(x^n) - Exponentiell z.B. TSP -> NP | ||
| + | |||
| + | Aber es hängt von Modell ab. Die Muster in erweiterten MA sind mächtig und weisen versteckte laufzeitkosten auf. -> Reduktion auf das einfachste mögliche Modell - ohne prinzipiell etwas zu verlieren. bei den MA -> einzige Textliterale sind zulässig. | ||
| + | |||
| + | ===== Primfaktorzerlegung ===== | ||
| + | Siehe Serie X | ||
| + | |||
| + | ====== Reduktion auf Suchliterale ====== | ||
| + | |||
| + | Bespiel: Eingabe Verdoppeln ''/ | ||
| + | /ατ/1α/ | ||
| + | /0σ/σ0/ | ||
| + | /1σ/σ1/ | ||
| + | /0τ/τ0/ | ||
| + | /1τ/τ1/ | ||
| + | /β1/τ1β/ | ||
| + | /β0/σ0β/ | ||
| + | /α// | ||
| + | /β// ! | ||
| + | //αβ/ | ||
| + | </ | ||
| + | |||
| + | ===== Universeller Markov-Algorithmus ===== | ||
| + | Ist ein MA der als Eingabe I = (ma, i) einen MA m und eine Eingabe i entgegen nimmt und die MA m auf die Eingabe i anwendet (simuliert). | ||
| + | |||
| + | Problem: Hört die Ausführung von ma auf i irgend einmal ab -> Halteproblem. | ||
| + | |||
| + | Interessante Frage Stellung: Gibt es einen Algorithmus der Entscheiden kann ob eine MA m für die Eingabe i haltet? | ||
| + | |||
| + | -> wird | ||
| + | |||