Informatik B (StuPO90)/Mündliche Prüfung SoSe 2006

Gedächntisprotokoll Info B Prüfung(Mündlich, Prof. Heiss) 08.05.2006 – kazi@cs.tu-berlin.de

1. Hashing a. Modulares Hashing b. Multiplikatives Hashing c. Aufwand d. Was ist Open Adressing ? e. Wie ist der Aufwand beim Seperate Chainig ? f. Kolliionsauflösung i. Lineares Sondieren ii. Inkrementelles Sondieren iii. Double Hashing g. Welche vermeiden primäre Häufung, Sekundäre Häufung etc. h. Was passiert bei einer Kollision ? i. Was versteht man bei Füllgrad ? i. Wie ist der Füllgrad definiert ? ii. Wann ist rehashing notwendig ? 2. Binär Baum a. Aufwand/ Einsatzgebiete 3. Vergleich Hashing und Bäume a. Komplexität angeben b. Was ist effizienter Hashing oder Bäume? c. Traversierung (Wie erhält man sortierte Zahlenfolge) 4. Was sind rekonfiguriende Bäume ? 5. Was ist ein AVL Baum ? a. Handsimulation zu einem AVL Baum machen. i. Rotieren und benennen um welchen Knoten, einfach oder doppellt 6. Was ist ein B-Baum ? a. Welche Vorteile ? b. Split erklären, Überlauf erklären bei Einfügeoperationen c. Was passiert wenn Mimimalfüllung eines Knotens verletzt ist ? 7. Was ist ein Minimalbaum ? 8. Welche Algorithmen eignen sich zur Bestimmung kürzester Wege ? 9. Welche Algorithemn bestimmen Minimal Spanbbaum? a. Handsimulation Kruskal b. Erklären wie der lg. Arbeitet. c. Komplexität angeben O( | E | * log | E | ) i. Nun erklären wie |E| und das log|E| entstehen. ii. Was macht das find(u) iii. Welchen Aufwand hat das find(u) ? iv. Wie sortieren sie die Kanten? v. Welchen Sortieralgorithmus wäheln Sie ? 1. Fall Quicksort, wie ist die Komplexität des Quicksort ? 10. Rucksackprobleme erklären a. Teilbares Rucksackproblem b. Unteilbares Rucksackproblem c. Welches ist Greedy lösbar d. Wie geht ein Greedy Algorithmus vor ? e. Was bedeutet Greedy Kriterium ? 11. Welcher Algorithmus löst das Unteilbare Rucksackproblem ?

12. Was ist Branch and Bound ? a. Wie geht der Algorithmus vor ? i. Was ist Branching und Boundig? b. Erklären sie die Vorgehensweise, welche im Skript beschrieben wurde. i. In jedem Schritt prüft der Alg. Ob ein Gegenstand mitgenommen wird oder nictht ? c. Was ist eine Obere Schranke und wie finde ich Sie ? d. Analog dazu die Untere Schranke ?

13. Was sind Schlossvariablen ? a. Wie schütze ich einen kritischen Abschnitt mit Schlossvariabekn ? b. Aktives warten erklären c. Lock erklären d. Unlock erklären e. Test und set erklären f. Enable und disable Interrupts erklären g. Was wenn man Mehrprozessorsystem hat i. Kernel Lock erklären ii. Kernellock mit Interrupt Handling erklären 14. Was sind Semaphoren und wozu dienen diese ? a. Wie sind diese Aufgebaut b. Wie funktioniert die Warteschlange? c. Wieviele Prozesse können in einen kritischen Abschnitt ? d. Wenn nur ein Prozess in den kritishen Abschnitt rein darf, wie muss die Semaphore gesetzt sein ? e. Einseitige Synchronisation und mehrseitige Synchronistaion erklären 15. Was idt Virtueller Speicher und wie funktioniert dieser ? 16. Was versteht man unter MMU? 17. Wie läuft die 2 Stufige Adresumsetzung per Segmentierung mit Seitenverwaltung ab ?

Das ist ein Abriß der wichtigsten Fragen. Der Professoer legt großen Wert auf die Koplexität. Dieses Thema sollte man gut verstanden haben. Es werden gerne Fragen zum Pseudo Code gestellt. Darus möchte er dann die Komplexität abgeleitet haben. Also geht und fragt die Assis speziell zur Komplexität, denn alles andere könnt ihr Büffeln, aber die Komplexitätsanalyse ist eine Kunst die seine Zeit braucht. Das kann man nur verstehen, indem man mit den Assistenten eine intensive Unterhaltung führt.

Ich empfehle die Spechstunden der Assistenten regelmäßig zu besuchen und vor allen Dingen, geht vorbereitet in die Sprechstunden !!! Kein Assi wird euch das Thema komplett erklären wollen und können, da diese die Zeit nicht haben. Vor allen Dingen muss ich sagen, dass alle Assis ziemlich kooperativ waren, als sie sahen, dass man gezielte Fragen stellen konnte. Hoffe dieses Protokoll wird euch eine Hilfe sein. Geht mindestens 2-3 Wochen vor eurer mündlichen Prüfung auch zur Sprechtunde des Professors. Prof. Heiss ist ein TOP-Proffessor und nimmt sich der Studenten an. Ich rechne ihm das hoch an. Skript komplett durcharbeiten, d.h. mindestens 3 mal gelesen haben. Zeit gut kalkulieren. Kann bis zu 10 Tage dauern, nur das Info3 Skript durchzuarbeiten.

Viel Erfolg wünscht euch kazi@cs.tu-berlin.de