Sitzung: Jeden Freitag in der Vorlesungszeit ab 16 Uhr c. t. im MAR 0.005. In der vorlesungsfreien Zeit unregelmäßig (Jemensch da?). Macht mit!

Informatik B (StuPO90)/Mündliche Prüfung SoSe 2006: Unterschied zwischen den Versionen

K (grobformatierung)
Zeile 2: Zeile 2:
  
 
1. Hashing
 
1. Hashing
 +
 
a. Modulares Hashing
 
a. Modulares Hashing
 +
 
b. Multiplikatives Hashing
 
b. Multiplikatives Hashing
 +
 
c. Aufwand
 
c. Aufwand
 +
 
d. Was ist Open Adressing ?
 
d. Was ist Open Adressing ?
 +
 
e. Wie ist der Aufwand beim Seperate Chainig ?
 
e. Wie ist der Aufwand beim Seperate Chainig ?
 +
 
f. Kolliionsauflösung
 
f. Kolliionsauflösung
 +
 
i. Lineares Sondieren
 
i. Lineares Sondieren
 +
 
ii. Inkrementelles Sondieren
 
ii. Inkrementelles Sondieren
 +
 
iii. Double Hashing
 
iii. Double Hashing
 +
 
g. Welche vermeiden primäre Häufung, Sekundäre Häufung etc.
 
g. Welche vermeiden primäre Häufung, Sekundäre Häufung etc.
 +
 
h. Was passiert bei einer Kollision ?
 
h. Was passiert bei einer Kollision ?
 +
 
i. Was versteht man bei Füllgrad ?
 
i. Was versteht man bei Füllgrad ?
 +
 
i. Wie ist der Füllgrad definiert ?  
 
i. Wie ist der Füllgrad definiert ?  
 +
 
ii. Wann ist rehashing notwendig ?
 
ii. Wann ist rehashing notwendig ?
 +
 
2. Binär Baum
 
2. Binär Baum
 +
 
a. Aufwand/ Einsatzgebiete
 
a. Aufwand/ Einsatzgebiete
 +
 
3. Vergleich Hashing und Bäume
 
3. Vergleich Hashing und Bäume
 +
 
a. Komplexität angeben
 
a. Komplexität angeben
 +
 
b. Was ist effizienter Hashing oder Bäume?
 
b. Was ist effizienter Hashing oder Bäume?
 +
 
c. Traversierung (Wie erhält man sortierte Zahlenfolge)
 
c. Traversierung (Wie erhält man sortierte Zahlenfolge)
 +
 
4. Was sind rekonfiguriende Bäume ?
 
4. Was sind rekonfiguriende Bäume ?
 +
 
5. Was ist ein AVL Baum ?
 
5. Was ist ein AVL Baum ?
 +
 
a. Handsimulation zu einem AVL Baum machen.
 
a. Handsimulation zu einem AVL Baum machen.
 +
 
i. Rotieren und benennen um welchen Knoten, einfach oder doppellt
 
i. Rotieren und benennen um welchen Knoten, einfach oder doppellt
 +
 
6. Was ist ein B-Baum ?
 
6. Was ist ein B-Baum ?
 +
 
a. Welche Vorteile ?
 
a. Welche Vorteile ?
 +
 
b. Split erklären, Überlauf erklären bei Einfügeoperationen
 
b. Split erklären, Überlauf erklären bei Einfügeoperationen
 +
 
c. Was passiert wenn Mimimalfüllung eines Knotens verletzt ist ?
 
c. Was passiert wenn Mimimalfüllung eines Knotens verletzt ist ?
 +
 
7. Was ist ein Minimalbaum ?
 
7. Was ist ein Minimalbaum ?
 +
 
8. Welche Algorithmen eignen sich zur Bestimmung kürzester Wege ?
 
8. Welche Algorithmen eignen sich zur Bestimmung kürzester Wege ?
 +
 
9. Welche Algorithemn bestimmen Minimal Spanbbaum?
 
9. Welche Algorithemn bestimmen Minimal Spanbbaum?
 +
 
a. Handsimulation Kruskal
 
a. Handsimulation Kruskal
 +
 
b. Erklären wie der lg. Arbeitet.
 
b. Erklären wie der lg. Arbeitet.
 +
 
c. Komplexität angeben O( | E | * log | E | )
 
c. Komplexität angeben O( | E | * log | E | )
 +
 
i. Nun erklären wie |E| und das log|E| entstehen.
 
i. Nun erklären wie |E| und das log|E| entstehen.
 +
 
ii. Was macht das find(u)
 
ii. Was macht das find(u)
 +
 
iii. Welchen Aufwand hat das find(u) ?
 
iii. Welchen Aufwand hat das find(u) ?
 +
 
iv. Wie sortieren sie die Kanten?
 
iv. Wie sortieren sie die Kanten?
 +
 
v. Welchen Sortieralgorithmus wäheln Sie ?
 
v. Welchen Sortieralgorithmus wäheln Sie ?
 +
 
1. Fall Quicksort, wie ist die Komplexität des Quicksort ?
 
1. Fall Quicksort, wie ist die Komplexität des Quicksort ?
 +
 
10. Rucksackprobleme erklären
 
10. Rucksackprobleme erklären
 +
 
a. Teilbares Rucksackproblem
 
a. Teilbares Rucksackproblem
 +
 
b. Unteilbares Rucksackproblem
 
b. Unteilbares Rucksackproblem
 +
 
c. Welches ist Greedy lösbar
 
c. Welches ist Greedy lösbar
 +
 
d. Wie geht ein Greedy Algorithmus vor ?
 
d. Wie geht ein Greedy Algorithmus vor ?
 +
 
e. Was bedeutet Greedy Kriterium ?
 
e. Was bedeutet Greedy Kriterium ?
 +
 
11. Welcher Algorithmus löst das Unteilbare Rucksackproblem ?
 
11. Welcher Algorithmus löst das Unteilbare Rucksackproblem ?
 +
 
   
 
   
 +
 
12. Was ist Branch and Bound ?
 
12. Was ist Branch and Bound ?
 +
 
a. Wie geht der Algorithmus vor ?
 
a. Wie geht der Algorithmus vor ?
 +
 
i. Was ist Branching und Boundig?
 
i. Was ist Branching und Boundig?
 +
 
b. Erklären sie die Vorgehensweise, welche im Skript beschrieben wurde.
 
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 ?
 
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 ?
 
c. Was ist eine Obere Schranke und wie finde ich Sie ?
 +
 
d. Analog dazu die Untere Schranke ?
 
d. Analog dazu die Untere Schranke ?
 +
 +
  
 
13. Was sind Schlossvariablen ?
 
13. Was sind Schlossvariablen ?
 +
 
a. Wie schütze ich einen kritischen Abschnitt mit Schlossvariabekn ?
 
a. Wie schütze ich einen kritischen Abschnitt mit Schlossvariabekn ?
 +
 
b. Aktives warten erklären
 
b. Aktives warten erklären
 +
 
c. Lock erklären
 
c. Lock erklären
 +
 
d. Unlock erklären
 
d. Unlock erklären
 +
 
e. Test und set erklären
 
e. Test und set erklären
 +
 
f. Enable und disable Interrupts erklären
 
f. Enable und disable Interrupts erklären
 +
 
g. Was wenn man Mehrprozessorsystem hat
 
g. Was wenn man Mehrprozessorsystem hat
 +
 
i. Kernel Lock erklären
 
i. Kernel Lock erklären
 +
 
ii. Kernellock mit Interrupt Handling erklären
 
ii. Kernellock mit Interrupt Handling erklären
 +
 
14. Was sind Semaphoren und wozu dienen diese ?
 
14. Was sind Semaphoren und wozu dienen diese ?
 +
 
a. Wie sind diese Aufgebaut
 
a. Wie sind diese Aufgebaut
 +
 
b. Wie funktioniert die Warteschlange?
 
b. Wie funktioniert die Warteschlange?
 +
 
c. Wieviele Prozesse können in einen kritischen Abschnitt ?
 
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 ?
+
 
 +
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  
 
e. Einseitige Synchronisation und mehrseitige Synchronistaion erklären  
 +
 
15. Was idt Virtueller Speicher und wie funktioniert dieser ?
 
15. Was idt Virtueller Speicher und wie funktioniert dieser ?
 +
 
16. Was versteht man unter MMU?
 
16. Was versteht man unter MMU?
 +
 
17. Wie läuft die 2 Stufige Adresumsetzung per Segmentierung mit Seitenverwaltung ab ?
 
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.
 
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 !!!  
 
Ich empfehle die Spechstunden der Assistenten regelmäßig zu besuchen und vor allen Dingen, geht vorbereitet in die Sprechstunden !!!  
Zeile 85: Zeile 163:
 
Skript komplett durcharbeiten, d.h. mindestens 3 mal gelesen haben. Zeit gut kalkulieren.
 
Skript komplett durcharbeiten, d.h. mindestens 3 mal gelesen haben. Zeit gut kalkulieren.
 
Kann bis zu 10 Tage dauern, nur das Info3 Skript durchzuarbeiten.
 
Kann bis zu 10 Tage dauern, nur das Info3 Skript durchzuarbeiten.
 +
  
 
Viel Erfolg wünscht euch  
 
Viel Erfolg wünscht euch  
 +
 
kazi@cs.tu-berlin.de
 
kazi@cs.tu-berlin.de

Version vom 9. Mai 2006, 10:25 Uhr

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