Knobelaufgaben aus alten Klausuren

Diskrete Strukturen
Tutorium VII – 04. Februar 2016
Tim Weißker
Klausur
Termin


17. März 2016, 11:00 Uhr, Hörsaal D (M13C), Dauer: 120 Minuten
Bitte vorher überprüfen, ob ihr zugelassen seid



alle Übungsblätter wurden bestanden oder
alle Übungsblätter bis auf eins wurden bestanden und mind. zwei
davon wurden gut bestanden
Hilfsmittel: ein doppelseitig, handschriftliches beschriebenes
DIN A4-Blatt

2
Diskrete Strukturen - Tutorium VII
04.02.2016
Knobelaufgaben
Übungsaufgaben
Wir bezeichnen eine natürliche Zahl  als Semi-Primzahl, wenn sie als
Produkt  =  zweier Primzahlen geschrieben werden kann.
Beweisen oder widerlegen Sie die folgenden Aussagen:
azugleich Semi-Primzahl und Primzahl sind
4
Diskrete Strukturen - Tutorium VII
04.02.2016
Übungsaufgaben
Wir bezeichnen eine natürliche Zahl  als Semi-Primzahl, wenn sie als
Produkt  =  zweier Primzahlen geschrieben werden kann.
Beweisen oder widerlegen Sie die folgenden Aussagen:
Die Menge aller Semi-Primzahlen ist über-abzählbar.
Es gibt unendlich viele Semi-Primzahlen, die durch 11 teilbar sind
Es gibt unendlich viele Semi-Primzahlen, die durch 12 teilbar sind
Es gibt unendlich viele Semi-Primzahlen, die durch 13 teilbar sind
Es gibt keine natürlichen Zahlen, die zugleich Semi-Primzahl und
Primzahl sind





5
Diskrete Strukturen - Tutorium VII
04.02.2016
Übungsaufgaben
Wir bezeichnen eine natürliche Zahl  als Beinahe-Primzahl, wenn
 + 1 eine Primzahl ist oder wenn  − 1 eine Primzahl ist. Beweisen
oder widerlegen Sie die folgenden Aussagen.
a
6
Diskrete Strukturen - Tutorium VII
04.02.2016
Übungsaufgaben
Wir bezeichnen eine natürliche Zahl  als Beinahe-Primzahl, wenn
 + 1 eine Primzahl ist oder wenn  − 1 eine Primzahl ist. Beweisen
oder widerlegen Sie die folgenden Aussagen.
Es gibt keine natürlichen Zahlen, die zugleich Semi-Primzahl und
Beinahe-Primzahl sind.
Es gibt keine natürlichen Zahlen, die zugleich Beinahe-Primzahl und
Primzahl sind.


a
7
Diskrete Strukturen - Tutorium VII
04.02.2016
Zusammenfassung
Zusammenfassung
Vollständige Induktion, Programmieren mit Python
Square-and-Multiply, Multiplikatives Inverses
Phi-Funktion, Satz von Euler, RSA-Kryptosystem, Gruppentheorie
Untergruppen, Ringe und Körper, Polynome,
Gruppenisomorphismen
Der Fermat-Test, Binäre Division, Reduktionspolynome
Diskrete Wahrscheinlichkeit, Lagrange-Interpolation,
Graphentheorie
Knobelaufgaben aus alten Klausuren
1.
2.
3.
4.
5.
6.
7.
9
Diskrete Strukturen - Tutorium VII
04.02.2016
The End
https://en.wikiquote.org/wiki/File:James_Burke_(science_historian).jpg
10
Diskrete Strukturen - Tutorium VII
04.02.2016
The End
„But maybe a good start would
be to recognize within yourself
the ability to understand
anything. Because that ability is
there, as long as it is explained
clearly enough. And then go and
ask for explanations.“
https://en.wikiquote.org/wiki/File:James_Burke_(science_historian).jpg
11
Diskrete Strukturen - Tutorium VII
-- James Burke
(British Science Historian)
04.02.2016