Gedächtnisprotokoll DM10-2

Aus Fachschaft_Informatik
Zur Navigation springen Zur Suche springen

Gedächtnisprotokoll zur DM Veranstaltung im WS10/11 gehalten von [Hans-Jürgen Bandelt] (Zweittermin).


1. Wie lautet die Worst Case Komplexität von Quicksort für n zu sortierende Zahlen?

2. Wie lautet der binomische Lehrsatz (laut Hochstättler)? Beweisen Sie ihn. Geben sie die Rekursion an, mittels der die Binominalkoeffizienten sukzessive berechnet werden.

3. Wie viele Äquivalenzrelationen gibt es auf einer 4 elementigen Menge?

4. Wie viele fixpunktfreie Permutationen gibt es auf einer Menge mit fünf Elementen? Wie groß ist der Anteil dieser Permutationen an allen Permutationen (gerundet auf volle Prozent)? Schätzen Sie die Wahrscheinlichkeit, dass eine zufällig gewählte Permutation auf eine Menge mit 50 elementen keinen Fixpunkt besitzt.

5. Bestimmen Sie eine ganze Zahl x zwischen 0 und 1000, die das System [man lese k als "kongruent"] x k 5 mod 8, x k 6 mod 9 und x k 8 mod 13 löst.

6. Bestimmen Sie das ggT der Polynome 2+x+x² und 5+x² in Z7[x]

7. Man nehme den reellen polynomring IR[x] und rechne modulo 2+x: Um welchen Ring handelt es sich dann bei IR[x]2+x?

8. Wie lautet der chinesische Restsatz? Wo wird er in der Informatik angewandt?

9. Wie viele Bitworte der Länge 12, bei denen nicht 2x eine 1 aufeinanderfolgen, gibt es?

10. Welche andere bekannte Gruppe (mit Angabe ihrer Definition) ist isomorph zur Automorphismengruppe des Petersengraph? Wie viele Elemente hat sie?

11. 1011.01(01 periodisch)im Zweiersystem ist darzustellen als Zahl in Stellenwertsystem zur Basis 3

12. Welches ist die Anzahl der Möglichkeiten, aus einer Menge M mit n Elementen erst eine Menge B und aus dieser eine Menge A auszuwählen?

13. Wie ist das direkte Produkt aus Z2 und Z7 definiert? Ist der produktring ein boolscher Ring? Ist er ein Körper?

14. Wie kann schnell und einfach geprüft werden, ob ein Graph eulersch ist?

15. Es war ein LGS zu lösen. Matrix war gegeben, Ergebnisvektor auch. (kann jemand Zahlen nachtragen?)

16. Was sagt der Satz von Lagrange über endliche Gruppen aus? Welche Anwendung hat er für die multiplikative Gruppe Zp*, wobei p Primzahl ist?