Archiv für 2013-4

Strukturelle Induktion

Wer sich mit Informatik oder Mathematik beschäftigt, wird früher oder später einen Beweis führen. Etwa bei der Zugabe zu „Mathematische Folgen“ war das der Fall. Bei endlich vielen Fällen ist das eher überschaubar: Um etwa zu beweisen, dass alle Kinder von Hanspeter größer als 1,40m sind, muss man einfach zu Klaus, Franz und Giesela gehen und nachmessen. Spannend wird es, wenn (wie im genannten Beispiel) über unendlich viele Fälle gesprochen wird.

Im vorliegenden Fall wurde die vollständige Induktion benutzt. Diese bietet sich an, wenn über natürliche Zahlen gesprochen wird, die die Fälle durchnummereien. Zunächst wird eine kleinste natürliche Zahl identifiziert und für den zugehörigen (meist trivialen) Fall ein Beweis geführt. Dies ist der Induktionsanfang. Im Anschluss wird eine Induktionsbehauptung aufgestellt, die besagt, dass es eine Zahl n gibt, bis zu der die zu beweisende Behauptung nachgewiesen ist. Im folgenden Induktionsschritt wird nun gezeigt, dass die Behauptung, so sie denn für n gilt, auch für den Nachfolger gilt. Nun ist die Aussage für jeden beliebige der unendlich vielen Fälle bewiesen, da sich jeder natürliche Zahl (also auch jeder Fall) durch entsprechend häufige Anwendung des Induktionsschrits erreichen lässt.

Induktion ohne natürliche Zahlen

Nun kann es sein, dass unsere Menge von Fällen gar nicht über die natürliche sondern etwa rekursiv definiert ist. Das kann so aussehen:

• Die Menge enthält die Worte „UND“, „NUDELN“ und „POMMES“.
• Für jedes Wort der Menge sind auch die Wörter enthalten, die durch Anhängen von „_UND_NUDELN“ und „_UND_POMMES“ entstehen.
• Die Menge ist genau die von den ersten beiden Punkten beschriebe Menge. (Es sind alle so erzeugbaren Wörter enthalten und sonst nichts)

Wie beweist man nun Behauptungen wie „In jedem Wort kommen ‚NUDELN‘ und ‚POMMES‘ höchstens ein mal öfter als ‚UND’ vor.“? Nun, wir haben zwar keine natürlichen Zahlen zu Verfügung, es lässt sich jedoch ein ähnliches Muster erkennen: Der erste Punkt stellt Anfangselemente dar (entspricht 0 oder 1 bei natürlichen Zahlen), der zweite erläutert, wie die Nachfolger der Elemente rekursiv gebildet werden (entspricht n+1 bei natürlichen Zahlen). Ein Beweis funktioniert dann so:

Beispiel einer strukturellen Induktion

Zu zeigen: anzahl_nudeln(w) ≤ anzahl_und(w) + 1 sowie anzahl_pommes(w) ≤ anzahl_und(w) + 1

Induktionsanfang

Sei w das Wort „UND“, „NUDELN“ oder „POMMES“ aus der Sprache.

• w ≡ „UND“: anzahl_und(w) = 1; anzahl_nudeln(w) = anzahl_pommes(w) = 0. ✓
• w ≡ „NUDELN“: anzahl_und(w) = anzahl_pommes(w) = 0; anzahl_nudeln(w) = 1. ✓
• w ≡ „POMMES“: anzahl_und(w) = anzahl_nudeln(w) = 0; anzahl_pommes(w) = 1. ✓

Induktionsvoraussetzung

Die zu zeigende Behauptung gelte für ein Wort w.

Induktionsschritt

Die Behauptung gilt für das Wort w. Zeige nun, dass sie auch für das Wort w*, das durch Anhängen von „_UND_NUDELN“ oder „_UND_POMMES“ entsteht.

• w* entsteht durch Anhängen von „_UND_NUDELN“. anzahl_und(w*) = anzahl_und(w)+1; anzahl_nudeln(w*) = anzahl_nudeln(w)+1; anzahl_pommes(w*) = anzahl_pommes(w); nach IV: anzahl_pommes(w) ≤ anzahl_und(w) + 1 → anzahl_pommes(w*) ≤ anzahl_und(w) + 1 + 1 → anzahl_pommes(w*) ≤ anzahl_und(w*) + 1; Nach IV: anzahl_nudeln(w) ≤ anzahl_und(w) + 1 → anzahl_nudeln(w) + 1 ≤ anzahl_und(w) + 1 + 1 → anzahl_nudeln(w*) ≤ anzahl_und(w*) + 1 ✓
• w* entsteht durch Anhängen von „_UND_POMMES“: analog.

QED

Nun wurde die Aussage für alle Elemente der unendlichen Menge gezeigt, da die elementaren Wörter der Behauptung genügen und die Bildungsvorschriften die Behauptung erhalten. Gut. Das war quick-and-dirty. Die Wikipedia und das Logikskript (2002, Madlener, S.2) erklären das noch mal richtig. Die verwendete Sprache ist übrigens an ein Beispiel aus „Software-Entwicklung 3“ (Gotzhein) angelehnt.

---

Warum ich Jabber mag

Jabber ist ein dezentrales Chatsystem auf Basis des freien Standards XMPP. Jabber ermöglicht eine Kontaktliste mit Statusanzeige, Einzelchats, Konferenzen, teilweise auch Audio-/Videoübertragung und vieles mehr. Jeder kann einen eigenen Server aufsetzen oder einen der bestehenden verwenden. Nachrichten, die an Nutzer fremder Server gehen, werden vom eigenen Server an den fremden weitergeschickt.

Viele Nutzer besitzen schon einen Jabber-Account, ohne es zu wissen. E-Mail-Accounts von United Internet (GMX, web.de, 1und1), Google Mail und Yandex sind schon funktionierende Jabber-Accounts. Wer noch keinen Jabber-Account besitzt, kann etwa bei jabber.fsinf.de einen anlegen.

Auch benutzen viele Nutzer Jabber/XMPP-fähige Clients (wie Pidgin), ohne es zu merken. Wer noch einen geeigneten Client sucht, findet eine knappe Auswahl mit Anleitungen bei einfachJabber.de und eine große Liste bei xmpp.org.

Warum ist das gerade jetzt wichtig?

Seit Jahren wird darauf hingewiesen, dass zentralisierte Chatdienste wie ICQ einzelnen Anbietern eine große Macht geben und durchaus gefährlich sind. In erster Linie wurde hierbei auf eine Passage in den Nutzungsbedingungen von ICQ verwiesen, wonach der Betreiber beliebges Material, das an die ICQ-Dienste geschickt wird, beliebig verwenden, verarbeiten, speichern und weitergeben kann (siehe Abschnitt „Materials You Send or Post“ in der ICQ-EULA).

Was ein Betreiber eines zentralisierten Kommunikationsdienstes noch so anstellen kann, demonstriert der ICQ-Eigentümer mail.ru zur Zeit: Die Server filtern Links zu YouTube aus den privaten Chatnachrichten aus.

---

Mathematische Folgen

Die Osterfeiertage sind gerade überstanden, die vorlesungsfreie Zeit ist auf ihrem klausurfreien Höhepunkt und die nächste Vorlesung ist noch fast zwei Wochen entfernt. Langsam, aber sicher stellt sich das suchtartige Verlangen nach mehr Zahlendingen ein. Um es eher ruhig zu beginne, schlage ich vor ein wenig Schulmathe zu praktizieren. Ziel ist es, leicht ein Glücksgefühl dank des überragenden eigenen Erfolgs zu erlangen. Eine angenehme und dennoch sinnvolle Fingerübung ist das Thema „mathematische Folgen“. Eine mathematische Folge ist eine endliche oder unendliche Auflistung von Glidern (auch Komponenten). Die Komponenten sind mit natürlichen Zahlen nummeriert. Hierbei wird vom Index oder einfach von der (Platz-)Nummer gesprochen.

{a_n } bezeichnet die Folge selbst. a_n bezeichnet ein Glied der Folge. Eine Folge kann verschiedene Darstellungen haben. Typische Möglichkeiten zur Datellung sind:

• Die ersten Glieder gefolgt von einem Auslassungzeichen (z.B. 2, 4, 8, 16, …)
• Eine Funktionsvorschrift zur Bildung des n-ten Elements (z.B. a_n = 2ⁿ)
• Die ersten Glieder gefolgt von einer Bildungsvorschrift für nachfolgende Elemente (z.B. a₁ = 2; a_n = 2 * a_n-1 (n ≥ 1))

Der Spaß besteht nun darin, eine Darstellung anzugeben und eine andere zu suchen. Bereit? Los geht’s!

Erste Glieder gegeben, Funktionsvorschrift gesucht

Diesen Aufgabentyp ist aus Intelligenztests bekannt. Gegeben wird eine endliche Auflistung von Gliedern einer Folge. Beim Intelligenztests wird ein weiteres Glied gesucht. Hier ist nach der Bildungsvorschrift gefragt, mit der ein beliebiges Glied der Folge bestimmt werden kann.

Die Folge 2/3, 4/9, 8/27, 16/81, …

Hier lässt sich die Funktionsvorschrift mit dem „mathematischen Auge“ erkennen: Durch scharfes Anstarren wird ersichtlich, dass der Zähler aus Zweierpotenzen und der Nenner aus Dreierpotenzen besteht. Somit gilt: a_n = (2ⁿ)/(3ⁿ) = (2/3)ⁿ

Hierbei wird auch ein Problem dieser Darstellung ersichtlich: Wer legt eigentlich fest, dass das nächste Glied der Folge 32/243 sein muss? Die nächste Komponente könnte ebenso wieder 2/3 sein. Dann wäre a_n = (2/3)^{(n modulo 4) + 1} eine gültige Lösung.

Die Folge 1, -1, 1, -1, 1, -1, …

Hier ist es ein guter Ansatz, den Schritt von einem Folgeglied zum nächsten zu betrachten. Offensichtlich wird mit a₁ = 1 begonnen und jedes folgende Glied durch Negieren (mit -1 multiplizieren) des Vergängers bestimmt. Die Folgeglieder lassen sich schön als Potenzen zur Basis -1 darstellen: a_n = (-1)ⁿ⁺¹ Der Exponent ist n+1, damit das erste Glied der Folge einen geraden Exponenten hat und somit mit 1 begonnen wird.

Die Folge 1, 1/2, 3, 1/4, 5, 1/6, 7, 1/8, …

Diese Folge besteht offenbar aus zwei Arten von Komponenten:

• Bei ungeradem Index: 1, 3, 5, 7, … oder einfach: n
• Bei geradem Index: 1/2, 1/4, 1/6, … oder einfach: 1/n

Erinnern wir uns daran, was wir über negative Exponenten gelernt haben und bringen die beiden Berechnungsvorschriften in eine einheitliche Form:

• Bei ungeradem Index: n = n¹
• Bei geradem Index: 1/n = n^-1

Die beiden Vorschriften lassen sich zu einer einzigen zusammenfassen, indem 1 und -1 durch Glieder der Folge {b_n} ersetzt werden: a_n = n^b_n Nun muss nur noch eine Folge {b_n} bestimmt werden, deren Komponenten 1 bei ungeradem und -1 bei geradem Index sind. Irgendwie erscheint diese Folge doch so vertraut, nicht wahr? Die zuvor bestimmte Folge leistet das Gewünschte! Folglich muss einfach einfach b_n = (-1)ⁿ⁺¹ in a_n eingesetzt werden: a_n = n^b_n = n^(-1)n+1

Noch eine kurze Probe:

• a₁ = 1^(-1)1-1 = 1^(-1)0 = 1¹ = 1 ✓
• a₂ = 2^(-1)2-1 = 2^(-1)1 = 2^-1 = 1/2 ✓
• a₃ = 3^(-1)3-1 = 3^(-1)2 = 3¹ = 3 ✓
• a₄ = 4^(-1)4-1 = 4^(-1)3 = 4^-1 = 1/4 ✓
• a₅ = 5^(-1)5-1 = 5^(-1)4 = 5¹ = 5 ✓
• a₆ = 6^(-1)6-1 = 6^(-1)5 = 6^-1 = 1/6 ✓
• a₇ = 7^(-1)7-1 = 7^(-1)6 = 7¹ = 7 ✓
• a₈ = 8^(-1)8-1 = 8^(-1)7 = 8^-1 = 1/8 ✓

Schaut gut aus!

Rekursive Funktionsvorschrift gegeben, erste Elemente gesucht

Zum Ausklang etwas Gemütliches: Durch Einsetzen die ersten fünf Komponenten einer rekursiv definierten Folge bestimmen. Das macht Spaß!

Die Folge a₁ = -2; a_n = n + a_n-1

Das ist echt einfach: Konstanten niederschreiben und die anderen Komponenten durch Einsetzen der schon bekannten Glieder bestimmen:

• a₁ = -2
• a₂ = 2 + a_2-1 = 2 + (-2) = 0
• a₃ = 3 + a_3-1 = 3 + 0 = 3
• a₄ = 4 + a_4-1 = 4 + 3 = 7
• a₅ = 5 + a_5-1 = 5 + 7 = 12
• a₆ = 6 + a_6-1 = 6 + 12 = 18

Das war schön, nicht wahr?

Zugabe: Nicht-rekursive Funktionsvorschrift aus einer rekursiven Funktionsvorschrift bilden

Weil die letzte Folge so schön war, gibt es gleich noch eine Übung hierzu: Jetzt ist eine nicht-rekursive Funktionsvorschrift gesucht. Im Wesentlichen wird hierzu einfach ein Muster geraten:

• Alle Komponenten rekursiv entfalten
• a_n = n + a_n-1 = n + (n-1) + a_n-2 = … = n + (n-1) + … 2 + a₁
• Oh! Eine Summe von 2 bis n … Ab in die Formel damit!
• = ∑ⁿ_{i = 2}(i) + a₁
• Indexverschiebung: Die Summe wird nun von 1 an begonnen. Der zusätzliche Summand 1 wird direkt nach der Summe wieder angezogen
• = ∑ⁿ_{i = 1}(i) - 1 + a₁
• Das schreit doch förmlich nach dem kleinen Gauß!
• = n*(n+1)/2 - 1 + a₁
• Oh, noch a₁ = -2 einsetzen!
• = n*(n+1)/2 - 1 + (-2) = n*(n+1)/2 - 3

Fertig! Eigentlich fehlt jetzt natürlich noch der Beweis für das geratene Muster. Dies funktioniert mit einer vollständigen Induktion: Als Induktionsanfang wird einfach n = 1 eingesetzt und gezeigt, dass a₁ = -2 herauskommt. Im Induktionsschritt wird angenommen, dass die gefundene Formel für a_n-1 stimmt. Nun wird das direkt berechnete a_n-1 in die rekursive Formel für a_n eingesetzt und gezeigt, dass dieses genau der direkten Formel für a_n entspricht.

---