https://wiki.mafiasi.de/index.php?action=history&feed=atom&title=Ged%C3%A4chtnisprotokoll_DM10-2Gedächtnisprotokoll DM10-2 - Versionsgeschichte2026-10-18T02:59:00ZVersionsgeschichte dieser Seite in Fachschaft InformatikMediaWiki 1.46.2https://wiki.mafiasi.de/index.php?title=Ged%C3%A4chtnisprotokoll_DM10-2&diff=12751&oldid=prev78.54.144.207: Die Seite wurde neu angelegt: 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 ...2011-04-03T20:10:46Z<p>Die Seite wurde neu angelegt: 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 ...</p>
<p><b>Neue Seite</b></p><div>Gedächtnisprotokoll zur DM Veranstaltung im WS10/11 gehalten von [Hans-Jürgen Bandelt] (Zweittermin). <br />
<br />
<br />
1. Wie lautet die Worst Case Komplexität von Quicksort für n zu sortierende Zahlen?<br />
<br />
2. Wie lautet der binomische Lehrsatz (laut Hochstättler)? Beweisen Sie ihn. Geben sie die Rekursion an, mittels der die Binominalkoeffizienten sukzessive berechnet werden.<br />
<br />
3. Wie viele Äquivalenzrelationen gibt es auf einer 4 elementigen Menge?<br />
<br />
4. Wie viele fixpunktfreie Permutationen gibt es auf einer Menge mit fünf Elementen? Wie groß ist der Anteil dieser Permutationen <br />
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.<br />
<br />
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.<br />
<br />
6. Bestimmen Sie das ggT der Polynome 2+x+x² und 5+x² in Z7[x]<br />
<br />
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?<br />
<br />
8. Wie lautet der chinesische Restsatz? Wo wird er in der Informatik angewandt?<br />
<br />
9. Wie viele Bitworte der Länge 12, bei denen nicht 2x eine 1 aufeinanderfolgen, gibt es?<br />
<br />
10. Welche andere bekannte Gruppe (mit Angabe ihrer Definition) ist isomorph zur Automorphismengruppe des Petersengraph? Wie viele Elemente hat sie?<br />
<br />
11. 1011.01(01 periodisch)im Zweiersystem ist darzustellen als Zahl in Stellenwertsystem zur Basis 3<br />
<br />
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?<br />
<br />
13. Wie ist das direkte Produkt aus Z2 und Z7 definiert? Ist der produktring ein boolscher Ring? Ist er ein Körper?<br />
<br />
14. Wie kann schnell und einfach geprüft werden, ob ein Graph eulersch ist?<br />
<br />
15. Es war ein LGS zu lösen. Matrix war gegeben, Ergebnisvektor auch. (kann jemand Zahlen nachtragen?)<br />
<br />
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?</div>78.54.144.207