BuK/IIm20/Vorlesung 2 Belkouchi
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
<language>Javascript</language>
== Folie 8 ==
[[ ÜA:Zeigen Sie, dass die folgenden Mengen abzählbar unendlich sind: Z,Q, die Menge der Primzahlen, die geraden Zahlen.
]]
Nehmen wir die Funktion : f:N↦Z mit [[Bild:Soufiane_1.PNG]]
Für Z:
[[Bild:Soufiane_2.PNG]]
So wurde gezeigt, dass die ganzen Zahlen abzählbar unendlich sind.
mit Hilfe das Cantorschen Diagonalisierungsverfahren :
[[Bild:Soufiane_3.PNG]]
'''Für die Menge der Primzahlen:'''
. nach Satz von Euklid, Die Menge der Primzahlen P ist unendlich.
. Die Menge der Primzahlen P ist abzählbar unendlich, so gilt: P ⊂N.
'''Für die Menge der geraden Zahlen:'''
. per Definition sind die geraden Zahlen unendlich und abzählbar unendlich, so gilt: G ⊂Z.
== Folie 9 ==
Verifizieren Sie, dass die folgende Funktion f:N+→Q+ eine bijektive Funktion ist und implementieren Sie eine Prozedur, die die zugehörige Umkehrfunktion f−1 berechnet.
<code id="606045ec42536">
function f(n){
if(n===1)
return 1;
if(n%2==0)
return (f(n/2)+1);
return (1/(f(n-1)));
}
</code>
<run id="606046031d589">f(3);</run>
Berechnen Sie f(n) für n = 1, 2, . . . , 7 mit der Hand:
f(1)=1
f(2)=2
f(3)=0,5
f(4)=3
f(5)=13
f(6)=1,5
f(7)=23
== Folie 13 ==
Zeigen Sie, dass die Menge überabzählbar unendlich ist:
Annahme: R ist abzählbar unendlich.
Die Realen Zahl werden wie folgenden geschrieben :
[[Bild:Soufiane_WhatsApp_Image_2021-03-28_at_11.27.47.jpeg]]
Nehmen wir an, die reellen Zahlen wären abzählbar, dann wären sicher auch die Zahlen im Intervall [0,1][0,1] abzählbar unendlich.
Nehmen wir an, wir hätten eine Abzählung in Dezimalbruchschreibweise:
[[Bild:Soufiane_WhatsApp_Image_2021-03-28_at_11.28.04.jpeg]]
Jetzt konstruieren wir eine reelle Zahl s\in [0,1]s∈[0,1], die nicht in der obigen Aufzählung vorkommen kann.
<div class="paraDiv">Wenn <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>s</mi><mo>=</mo><mn>0</mn><mo separator="true">,</mo><msub><mi>s</mi><mn>1</mn></msub><msub><mi>s</mi><mn>2</mn></msub><msub><mi>s</mi><mn>3</mn></msub><msub><mi>s</mi><mn>4</mn></msub><mo>…</mo></mrow><annotation encoding="application/x-tex">s=0,s_1s_2s_3s_4\ldots</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.43056em;vertical-align:0em;"></span><span class="mord mathdefault">s</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.8388800000000001em;vertical-align:-0.19444em;"></span><span class="mord">0</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord"><span class="mord mathdefault">s</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.30110799999999993em;"><span style="top:-2.5500000000000003em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">1</span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span><span class="mord"><span class="mord mathdefault">s</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.30110799999999993em;"><span style="top:-2.5500000000000003em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">2</span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span><span class="mord"><span class="mord mathdefault">s</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.30110799999999993em;"><span style="top:-2.5500000000000003em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">3</span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span><span class="mord"><span class="mord mathdefault">s</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.30110799999999993em;"><span style="top:-2.5500000000000003em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">4</span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="minner">…</span></span></span></span> in Dezimalschreibweise gegeben ist, dann soll <span class="katex"><span class="katex-mathml"><math><semantics><mrow><msub><mi>s</mi><mi>i</mi></msub><mo>=</mo><mo>(</mo><msub><mi>r</mi><mrow><mi>i</mi><mi>i</mi></mrow></msub><mo>+</mo><mn>1</mn><mo>)</mo><mspace></mspace><mspace width="0.6666666666666666em"></mspace><mrow><mi mathvariant="normal">m</mi><mi mathvariant="normal">o</mi><mi mathvariant="normal">d</mi></mrow><mtext> </mtext><mtext> </mtext><mn>10</mn></mrow><annotation encoding="application/x-tex">s_i=(r_{ii}+1) \mod 10</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.58056em;vertical-align:-0.15em;"></span><span class="mord"><span class="mord mathdefault">s</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.31166399999999994em;"><span style="top:-2.5500000000000003em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mathdefault mtight">i</span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mopen">(</span><span class="mord"><span class="mord mathdefault" style="margin-right:0.02778em;">r</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.31166399999999994em;"><span style="top:-2.5500000000000003em;margin-left:-0.02778em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mathdefault mtight">i</span><span class="mord mathdefault mtight">i</span></span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord">1</span><span class="mclose">)</span><span class="mspace allowbreak"></span><span class="mspace" style="margin-right:0.6666666666666666em;"></span></span><span class="base"><span class="strut" style="height:0.69444em;vertical-align:0em;"></span><span class="mord"><span class="mord"><span class="mord mathrm">m</span><span class="mord mathrm">o</span><span class="mord mathrm">d</span></span></span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord">1</span><span class="mord">0</span></span></span></span> sein. </div>