Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
7 TheoInf Fragen
Hi,
danke allen für die Antworten auf meine letzten 2 Fragen, aber ich habe noch ein paar Probleme:
- Hat jemand den Pseudocode für QuickSelect?
- Warum sind Primzahlen primitiv-rek.? In der Lösung steht doch nichts von Nachfolgerfunktion oder so, auch nichts von einem LOOP-Programm.
- Weiß jemand, wie ich die Sprache zu einem gegebenen Automaten erstelle (Schöning S. 38)
- Was bedeutet *, +, T oder i+1 über Mengen oder Relationen? Wahrscheinlich weder ‘hoch’ (multiplizieren) noch Konkatenation?
- Wie weise ich nach, dass 4294967297 eine Primzahl ist? (Aufgabe 3-47)?
Vielen Dank für Antworten!
ad 4:
wenn M eine menge ist, dann ist M²={(i, j): i∈M∧j∈M}
M* = Σ von 0 bis ∞ über M^i = {}+M+M^2+…
M+ = Σ von 1 bis ∞ über M^i=M*{}
schöning p.185ff.
educated guess: T steht für eine gewisse repräsentation der wahrheit.
wenn M und L Mengen sind, dann wird durch K=M+L ausgedrückt, dass M∩L={} gilt. ansonsten wird K=M∪L geschrieben.
ad 2:
educated guess: der unterschied zwischen primitiver und µ rekursion ist, dass µ rekursion unendliche suchvorgänge abbilden kann. für den nachweis der primheit braucht es keinen unendlichen vorgang.
ad1:
erster treffer in google.
ad3:
naja die regulären operatoren sind in den automaten als struktur sichtbar. eine prise intuition vielleicht noch 
zu 5
die Zahl ist ja (2^32) + 1
Man könnte hier mit Primzahlzertifikaten loslegen.
Allerdings wird es dann wohl daran scheitern, dass a^((2^32 +1) / 2) mod 2^32 + 1 zu berechnen.
Da würde ich eher den Miller-Rabin drauf loslassen.