Entscheidbarkeit von ganzzahligen Polynomen

14.12.2012, 15:51	Stefan1991	Auf diesen Beitrag antworten »
Entscheidbarkeit von ganzzahligen Polynomen Hallo, diese Aufgabe hat sowohl mit LA als auch mit Informatik zu tun. Ich hoffe, ich bin hier richtig. Ich soll zeigen, dass die Sprache der ganzzahligen Polynome (und zwar müssen die nicht normiert sein) entscheidbar ist. Also dass man algorithmisch alle Nullstellen finden kann. Ich habe gelesen, dass jede Nullstelle ein Teiler von a_0 (das "Glied" mit Grad 0) ist. Aber das gilt, soweit ich weiß, nur für normierte Polynome, wo a_n (Koeffizient des Glieds höchsten Grades) = 1 ist. Das ist bei meiner Aufgabe nicht der Fall. Wie könnte man denn noch argumentieren?
14.12.2012, 16:34	Huggy	Auf diesen Beitrag antworten »
RE: Entscheidbarkeit von ganzzahligen Polynomen Ein nicht normiertes Polynom mit ganzzahligen Koeffizienten lässt sich immer zu einem normierten Polynom mit ganzzahligen Koeffizienten machen. Allerdings kann ein solches Polynom auch nicht rationale Nullstellen haben, wie z. B. $\begin{eqnarray} x^2-2=0 \end{eqnarray}$
14.12.2012, 16:37	Stefan1991	Auf diesen Beitrag antworten »
Habe gerade gesehen, dass ich die Aufgabe total falsch verstanden habe. Tatsächlich soll ich nur einen Algorithmus finden, der ausgibt, ob es mindestens eine Ganzzahlige Nullstelle gibt oder nicht. Das ist nicht mehr soooo schwer. Ich gehe einfach alle ganzen Zahlen von -S bis S durch und schaue, ob P(x) = 0 ist. Falls ja, return 1. Falls die Schleife zuende ist und ich noch nichts zurückgegeben habe, return 0. Soo, die Frage ist jetzt nur: Wie bestimme ich S? Also eine obere Schranke für die möglichen Nullstellen. Ich denke, das geht irgendwie auch über die Sache mit der Teilbarkeit, oder?
14.12.2012, 16:41	Stefan1991	Auf diesen Beitrag antworten »
Kann ich sagen, dass wenn es eine ganzzahlige NST gibt, dass diese dann auf jeden Fall im Intervall [-a0, a0] liegen muss? Weil nur dann kann sie ja Teiler von a0 sein, oder? (a0 ist der Koeffizient des Polynoms mit Grad 0)
14.12.2012, 16:58	Stefan1991	Auf diesen Beitrag antworten »
Ich habe jetzt ein paar Polynome ausprobiert und kein Gegenbeispiel gefunden. Mein Ergebnis ist jetzt: Falls a_o = 0 => 0 ist eine ganzzahlige NST. Sonst: Entweder es gibt keine ganzzahlige NST oder diese liegt in [-a_0, a_0]. Kann das jemand bestätigen?
14.12.2012, 17:04	Huggy	Auf diesen Beitrag antworten »
Stimmt.
Anzeige

14.12.2012, 17:07	Stefan1991	Auf diesen Beitrag antworten »
Das erste Mal, dass eine von mir aufgestellte Behauptung tatsächlich stimmt. Ich danke dir! :-D

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »