Theoretische und technische Informatik - ganz praktisch
Herzlich willkommen auf der Question/Answer-Plattform zu Grundlagen der Informatik II. Wir wünschen Ihnen viel Spaß beim Lernen und Diskutieren!
Loggen Sie sich mit Ihrem KIT-Account (u...) ein, um loszulegen!
Beachten Sie auch diese Informationen zum Schnelleinstieg.
(Nicht-KIT-Studierende beachten bitte diese Informationen.)

Schöne Ferien!
 

 

c): Was ist die Idee des Ansatzes?

0 Punkte
35 Aufrufe
wie kommt man überhaupt darauf, für \( i = |xz| \) zu wählen, was ist die Idee dahinter und weshalb ist das dann \(1^{i_{y}(i_{x}+i_{z})} \)?
Gefragt 17, Sep 2015 in HU-1-4 von uafjv uafjv Tutor(in) (167,990 Punkte)  

Eine Antwort

0 Punkte

Warum i = |xy| ?

Ich kann dir leider kein allgemeingültiges Kochrezept angeben, mit dem man bei Pumpinglemma-Aufgaben stets und schnell ein geeignetes i finden kann. Teils funktioniert blindes Ausprobieren von i = 0 oder i = 2, aber meist ist eine Idee, wie man zu dem  Widerspruch kommt (hier: keine Primzahl lässt sich als Produkt von zwei natürlichen Zahlen > 1 darstellen -> Länge des gepumpten Wortes als Produkt darstellen) nötig. Dann wählt man i entsprechend. Evtl. muss man auch erst mal verschiedene Ansätze und i ausprobieren, da man nicht jeden Zwischenschritt vollständig überblickt...  Insofern wählt man i = |xy|, weil dann so umformen kann, dass man zum Ziel (Widerspruch) kommt.

Zu deiner zweiten Frage:

\( i= |xy| = |x| + |y| = i_x +i_y \) und \( y = 1^{i_y} \) einsetzen:
\( y^i = (1^{i_y})^i = (1^{i_y})^{i_x + i_y} \)
Mit den Potenzgesetzen \( (a^b)^c = a^{b*c} \) kommt man auf  \(1^{i_y*(i_x + i_y)} \)

Ich hoffe,  zumindest deine zweite Frage beantwortet zu haben.

Tobias (Tutor)

 

EDIT:

Sorry, hab mich vertippt, es muss naturlich \( i = |xz| = |x| + |z| = i_x +i_z \) und \( y^i = ... = (1^{i_y})^{i_x+i_z} \) heißen!

Beantwortet 17, Sep 2015 von uafjv uafjv Tutor(in) (167,990 Punkte)  
Bearbeitet 17, Sep 2015 von uafjv uafjv
...