TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 182

Aus VoWi
Zur Navigation springen Zur Suche springen

Wieviele verschiedene Variablennamen kann man in einer fiktiven Programmiersprache verwenden, wenn diese Namen aus mindestens einem, höchstens aber vier (nicht notwendig verschieden) Buchstaben {A,...,Z} bestehen müssen, und die Befehle AND, OR, IF, THEN und GOTO nicht als Teilwörter enthalten sein dürfen.

Lösungsvorschlag von W wallner[Bearbeiten]

Das Beispiel kann mit dem Inklusions-Exklusions-Prinzip gelöst werden.

Gesucht ist die Menge M der Wörter mit Länge 1 bis 4 ohne die reservierten Teilwörter.

Wir betrachten das Universum E der Wörter mit einer Länge von 1 bis 4. E besteht aus den Mengen E_k der Wörter mit Länge k, k \in \{1,2,3,4\}. Jede Menge E_k enthält alle Variationen mit Wiederholung von k Buchstaben mit jeweils 26 Möglichkeiten, also gilt:

\left|E_1\right| = 26^1
\left|E_2\right| = 26^2
\left|E_3\right| = 26^3
\left|E_4\right| = 26^4

Die Gesamtgröße unseres Universums ist also:


\left|E\right| =
\left|E_1\right| + \left|E_2\right| + \left|E_3\right| + \left|E_4\right| =
26^1 + 26^2 + 26^3 + 26^4

Davon müssen wir jetzt die Vereinigung der Mengen mit den reservierten Teilwörter abziehen. Dabei müssen wir berücksichtigen, dass es Wörter gibt, die mehrere Teilwöter enthalten, und deshalb fälschlicherweise öfters abgezogen werden (z.B.: Das Wort IFOR enthält die beiden Teilwörter IF und OR, darf aber nur einmal abgezogen werden.)

Wir berechnen deshalb die Beträge der reservierten Teilmengen, sowie die Beträge der Vereinigungen mehrerer Teilmengen. Dabei bezeichnet z.B. xOR die Menge aller Wörter, die als erstes einen beliebigen Buchstaben, und als zweiten und dritten die Buchstaben OR enthalten ({AOR, BOR, COR, DOR, ..., ZOR)

Beträge der einzelnen Mengen[Bearbeiten]

\left|OR\right|   = 1
\left|ORx\right|  = 26
\left|xOR\right|  = 26
\left|ORxx\right| = 26^2
\left|xORx\right| = 26^2
\left|xxOR\right| = 26^2

\left|IF\right|   = 1
\left|IFx\right|  = 26
\left|xIF\right|  = 26
\left|IFxx\right| = 26^2
\left|xIFx\right| = 26^2
\left|xxIF\right| = 26^2
 
\left|AND\right|  = 1
\left|ANDx\right| = 26
\left|xAND\right| = 26

\left|THEN\right| = 1

\left|GOTO\right| = 1

Beträge der Vereinigungen[Bearbeiten]

Es gibt bei unsere Angabe nur 4 mögliche Wörter, die mehr als ein Teilwort enthalten können. Beim Test sollte man aber vorsichtig sein, falls z.B. in der Angabe die Teilwörter (GOTO, GO, TO), (FOR, OR), (TO, OR) oder ähnliches genannt werden (siehe Angabe und Lösung weiter unten von mnemetz).

\left|ORxx \cap  xxOR\right| = 1
\left|ORxx \cap xxIF\right| = 1
\left|IFxx \cap xxOR\right| = 1
\left|IFxx \cap xxIF\right| = 1

Alle anderen Vereinigungen von zwei oder mehr Teilmengen sind leer.

Anmerkung mick:

Ist hier nicht geschnitten gemeint?

Anwenden des Inklusions-Exklusions-Prinzips[Bearbeiten]

Einsetzen in die Formel des Inklusions-Exklusions-Prinzip bringt uns zu:


\begin{align}
\left|M\right| = & \left|E\right| \\
 & - \left|OR\right| - \left|IF\right| \\
 & - \left|ORx\right| - \left|xOR\right| - \left|IFx\right| - \left|xIF\right| - \left|AND\right| \\
 & - \left|ORxx\right| - \left|xORx\right| - \left|xxOR\right| \\
 & - \left|IFxx\right| - \left|xIFx\right| - \left|xxIF\right| \\
 & - \left|ANDx\right| - \left|xAND\right| \\
 & - \left|THEN\right| - \left|GOTO\right| \\
 & + \left|ORxx \cap xxOR\right| + \left|ORxx \cap xxIF\right| \\
 & + \left|IFxx \cap xxOR\right| + \left|IFxx \cap xxIF\right|
\end{align}

Einsetzen der uns bereits bekannten Werte bringt uns zu:


\begin{align}
\left|M\right| = & 26^1 + 26^2 + 26^3 + 26^4 \\
 & - 1 - 1 \\
 & - 26 - 26 - 26 - 26 - 1 \\
 & - 26^2 - 26^2 - 26^2 \\
 & - 26^2 - 26^2 - 26^2 \\
 & -26 - 26 \\
 & - 1 - 1 \\
 & + 1 + 1 \\
 & + 1 + 1
\end{align}

Zusammenfassen und ausrechnen ergibt:


\begin{align}
\left|M\right| & = 26^3 + 26^4 - 5*26 - 5*26^2 - 1 \\
 & = 17576 + 456976 - 130 - 3380 - 1 \\
 & = 471041
\end{align}

mfg, --W wallner

PS: Wolfgang, beim Zusammenfassen hast du 2*26 vergessen, habs schon ausgebessert :) --p.paulweber

Lösungsvorschlag von mnemetz (etwas komplexere u. andere Angabe!)[Bearbeiten]

Wieviele verschiedene Variablennamen kann man in einer fiktiven Programmiersprache verwenden, wenn diese Namen aus mindestens einem, höchstens aber vier (nicht notwendig verschieden) Buchstaben {A,...,Z} bestehen müssen, und die Befehle AND, OR, OF, THEN, GO, TO und FOR nicht als Teilwörter enthalten sein dürfen.

Wie sehen, dass in allen Variablennamen, in denen FOR vorkommt, OR schon enthalten ist. Die Einschränkung, dass FOR nicht vorkommen darf, koennen wir uns also sparen!


Wir zählen:

Es gibt 26 Variablennamen der Form x_1 mit x_1 \in \bigtriangleup := \{A, .., Z\}.


Es gibt 26^2 Namen der Form X_1X_2 mit X_1, X_2 \in \bigtriangleup. Von diesen ziehen wir 4 (nämlich OR, OF, GO und TO) wieder ab. Es gibt also 26^2 - 4 Variablennamen der Länge 2.


Es gibt 26^3 Namen der Form X_1X_2X_3 mit X_1, X_2, X_3 \in \bigtriangleup. Davon ziehen wir 8*26+1 wieder ab (nämlich alle der Form X_1OR, X_1OF, X_1GO, X_1TO, ORX_3, OFX_3, GOX_3, TOX_3 für X_1, X_3\in \bigtriangleup, und natürlich AND). Weil das aber zu einfach wäre, müssen wir 4 wieder hinzuaddieren (nämlich GOR, GOF, TOR und TOF), die wir sonst doppelt subtrahiert hätten. Es gibt also 26^3 - (8*26+1) + 4 Variablennamen der Länge 3.


Und jetzt wird es noch komplizierter ... :-/

Es gibt 26^4 Namen der Form X_1X_2X_3X_4 mit X_1, X_2, X_3, X_4 \in \bigtriangleup Von diesen ziehen wir 2*26 + 3*4*26^2 + 1 wieder ab (nämlich alle der Form X_1AND, ANDX_4, X_1X_2OR, X_1X_2OF, X_1X_2GO, X_1X_2TO, X_1ORX_4, X_1OFX_4, X_1GOX_4, X_1TOX_4, ORX_3X_4, OFX_3X_4, GOX_3X_4, TOX_3X_4, und natürlich THEN).

Nun müssen wir wieder 2 *4*26 + 4*4 addieren, die wir sonst doppelt subtrahiert hätten (nämlich X_1GOR, X_1TOR, X_1GOF, X_1TOF, GORX_4, TORX_4, GOFX_4, TOGX_4, und OROR, OROF, ORGO, ORTO, OFOR, OFOF, OFGO, OFTO, GOOR, GOOF, GOGO, GOTO, TOOR, TOOF, TOGO, TOTO). Es gibt also 26^4 - (2*26 + 3*4*26^2 + 1) + 2*4*26 + 4*4 Variablennamen der Länge 4.


Insgesamt haben wir nun: Es gibt 26 + 26^2 - 4 + 26^3 - (8*26+1) + 4 + 26^4 - (2*26 + 3*4*26^2 + 1) + 2*4*26 + 4*4 Variablennamen der Länge höchstens 4. (Das sind: 467104)