FreitagsrundenWiki - Benutzerbeiträge [de]

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

2006-06-12T22:51:50Z

Kazi:

Gedächntisprotokoll Info B Prüfung(Mündlich, Prof. Heiss) Mai 2006

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)

:d. Hat Hashing größeren Aufwand, wenn man die Keys sortiert ausgeben will oder ein Binär-Baum ?

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 Alg. 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 ?

:::i. Falls 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 ist Virtueller Speicher und wie funktioniert dieser ?

:a. Was ist Paging ?

:b. Was ist Segmentierung ?

:c. was ist eine Tabellenbasisadresse ?

:d. Gibt es einen Bezug zum B-Baum ?

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 Professor legt großen Wert auf die Komplexitä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, d.h. er ist ein fairer Professor. 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.

Und zuletzt .........lernen ist harte Arbeit. Ihr müsst Euch genug Zeit für den Stoff nehmen.
Ich empfehle niemandem Mut zur Lücke, wenn ihm was an dem Studium liegt.

Abschließend noch zu sagen, wenn man dann eigentlich alles verstanden hat, fühlt man sich viel sicherer auf vielen Gebieten der Informatik.

Viel Erfolg

Benutzer Diskussion:Kazi

2006-05-17T21:01:27Z

Kazi:

Ich denke dise Themen sollten zu Info 4 eingefügt werden. Ciao Kazim

: Ich finde es ungünstig, wenn Prüfungsprotokolle in Seiten wie "Grundlagen der Informationsmodellierung" abgelegt werden, weil es durchaus mehrere solcher Protokolle von verschiedenen Personen geben könnte. Lege doch bitte solche Seiten unterhalb deiner eigenen Seite an z.B. [[Benutzer:Kazi/Grundlagen der Informationsmodellierung]] oder schicke uns eine Textdatei, die wir dann hochladen. Vielen Dank --[[Benutzer:Felix|Felix]] 23:08, 14. Mai 2006 (CEST)

: Was bezweckst du mit dem Inhalt auf [[FreitagsrundenWiki:Geschützte_Seiten]]? --[[Benutzer:Felix|Felix]] 23:08, 14. Mai 2006 (CEST)

Hallo Felix, bezwecken möchte ich gar nichts. Es ging mir nur darum, eine Übersicht der Themen anzulegen.

Bei Gelegenheit lösche ich diese Sachen.

:: Hoffentlich nicht ersatzlos ;) Ich finde Dein Engagement sehr gut, leider ist nur manchmal der Ablageort etwas unglücklich, ich denke das ist hier das Problem. Das ist nichts gegen Dich oder Dein Engagement, es wäre nur schön, wenn die Artikel gleich an der richtigen Stelle erscheinen ;) --[[Benutzer:Mutax|mutax]] 21:33, 17. Mai 2006 (CEST)

Ich teile gerne mein Wissen und helfe gerne wo ich kann, da ich denke, dass dies eines der Hauptprobleme an der TU-Berlin ist. Engagement ist imer mit zeit verbunden. Das ist bspw. mein Problem, wenn ich andere an meinem Wissen teihaben lassen möchte, habe ich leider nicht die Zeit, um die gesamte WIKI-Struktur durchzuarbeiten. Es geht hier auch icht, dass ich beleidigte Leberwurst spielen will. Es muss für unqualifizierte eine Instanz geben, die die daten entsprehend umschichtet. Natürlich ist das Mehraufwand für andere, aber ich denke so wächst dieses Portal. Wie auch immer ...Ciao Kazim

Diskussion:Grundlagen der Informationsmodellierung

2006-05-17T13:02:07Z

Kazi:

Ich habe die Daten rausgenommen, ........ nach Aufforderung.

Manchmal kann man Inititiative im Keim ersticken. Möge jemand sich angesprochen fühlen !!

Grundlagen der Informationsmodellierung

2006-05-17T13:00:04Z

Kazi:

Benutzer:Kazi

2006-05-17T12:59:22Z

Kazi:

E-mail rausgenommen wegen privatsphäre.

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

2006-05-17T12:58:17Z

Kazi:

Gedächntisprotokoll Info B Prüfung(Mündlich, Prof. Heiss) Mai 2006

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)

:d. Hat Hashing größeren Aufwand, wenn man die Keys sortiert ausgeben will oder ein Binär-Baum ?

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 Alg. 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 ?

:::i. Falls 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 ist Virtueller Speicher und wie funktioniert dieser ?

:a. Was ist Paging ?

:b. Was ist Segmentierung ?

:c. was ist eine Tabellenbasisadresse ?

:d. Gibt es einen Bezug zum B-Baum ?

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 Professor legt großen Wert auf die Komplexitä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.

Und zuletzt .........lernen ist harte Arbeit. Ihr müsst Euch genug Zeit für den Stoff nehmen. Ich empfehle niemandem Mut zur Lücke, wenn ihm was an dem Studium liegt.

Viel Erfolg

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

2006-05-17T12:58:01Z

Kazi:

Gedächntisprotokoll Info B Prüfung(Mündlich, Prof. Heiss) 2006

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)

:d. Hat Hashing größeren Aufwand, wenn man die Keys sortiert ausgeben will oder ein Binär-Baum ?

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 Alg. 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 ?

:::i. Falls 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 ist Virtueller Speicher und wie funktioniert dieser ?

:a. Was ist Paging ?

:b. Was ist Segmentierung ?

:c. was ist eine Tabellenbasisadresse ?

:d. Gibt es einen Bezug zum B-Baum ?

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 Professor legt großen Wert auf die Komplexitä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.

Und zuletzt .........lernen ist harte Arbeit. Ihr müsst Euch genug Zeit für den Stoff nehmen. Ich empfehle niemandem Mut zur Lücke, wenn ihm was an dem Studium liegt.

Viel Erfolg

Benutzer Diskussion:Kazi

2006-05-17T12:57:10Z

Kazi:

Grundlagen der Informationsmodellierung

2006-05-14T11:24:30Z

Kazi:

Gedächtnisprotokoll GIM Klausur WS05/06

* Quickies
**Sichten auf das System (interne/externe ..)
* ER Diagramm
**Kaufhaus modellieren

*Krankenhaus (Relationalalgebra)
**Patient, Chefarzt etc. (Modellierung per Mathematischen Relationen)

*Relationenalgebra (Join etc. anhand Tabellen formulieren)

*Statechart erstellen

*UML-Modell erstellen

*Metamodell erstellen für ER-Diagramm
** Ohne Aggregation darstellen

* Unterlagen und Musterlösungen: http://cis.cs.tu-berlin.de/Lehre/SS-05/Sonstiges/gim-pages/pub/ueb/?1147605708

Informatik 3 (StuPO90)

2006-05-14T00:03:01Z

Kazi: /* Tipps und nützliche Infos */

<div id="klausuren" style="float:right; width:20%; margin:10px; padding:10px; background-color:#efefef;">
<h2>Klausuren</h2>

SS 2005
* [[Informatik 3/Gedächtnisprotokoll Klausur SS05|Gedächtnisprotokoll]]

WS 2004/2005
* [[Informatik 3/Gedächtnisprotokoll Klausur WS0405|Gedächtnisprotokoll]]

WS 2003/2004
* [http://docs.freitagsrunde.org/Klausuren/Informatik_3/ws0304.pdf Klausur]

SS 2003
* [http://docs.freitagsrunde.org/Klausuren/Informatik_3/ss03.pdf Klausur]

WS 2002/2003
* [http://docs.freitagsrunde.org/klausuren/Informatik_3/ws02-03%20Probeklausur.pdf Probeklausur]

SS 2000
* [http://docs.freitagsrunde.org/Klausuren/Informatik_3/ss00.pdf Klausur]

WS 1999/2000
* [http://docs.freitagsrunde.org/Klausuren/Informatik_3/ws99-00.pdf Klausur]

WS 1997/1998
* [http://docs.freitagsrunde.org/Klausuren/Informatik_3/ws97-98.pdf Klausur]

SS 1997
* [http://docs.freitagsrunde.org/Klausuren/Informatik_3/ss97.pdf Klausur]

</div>

Informatik 3 ist der dritte Teil der [[Informatik (Vorlesung)|Informatik-Vorlesungen]] im [[Grundstudium Informatik]].

== Inhalt ==
Algorithmen und Datenstrukturen in Java und/oder Pseudocode.

* Hashverfahren
* Skip-Listen
* Binäre Suchbäume
* Rekonfigurierende Suchbäume
* B-Bäume
* Graphen: Begriffe und Datenstrukturen
** Breiten-/Tiefensuche
** Minimale Spannbäume
** Kürzeste Wege
* Algorithmen für Optimierungsprobleme
** Dynamisches Programmieren
** Greedy-Algorithmen
** Branch and Bound
** Heuristische Suche

== Tipps und nützliche Infos ==

Die Themen AVL-, Rot-Schwarz Baum kommen immer wieder in Info 3 Klausuren vor. Dabei ist es nicht getan, wenn man die Rotationen bißchen geübt hat, man muss auch spezialfälle üben und sozusagen blind anwenden können. Dabei ist es hilfreich, wenn man Testweise ein Applet zur visuellen Unterstützung einsetzt.

AVL-Baum: http://webpages.ull.es/users/jriera/Docencia/AVL/AVL%20tree%20applet.htm

B-Baum: http://www.fh-augsburg.de/~mweiss/applets/bTree.shower2.html

RB-Baum: http://fbim.fh-regensburg.de/~saj39122/gikasch/start.html

Graphen: http://links.math.rpi.edu/applets/appindex/graphtheory.html

== Weblinks ==
* http://kbs.cs.tu-berlin.de/teaching/ws2005/info3/
* [http://user.cs.tu-berlin.de/~xantippe/Glossar/glossar.html Glossar für Informatik 3]

== Persönliche Kommentare ==
:(Nicht unterschriebene Kommentare werden gelöscht!)

[[Kategorie:Lehrveranstaltungen]]
Deckt viele INFO3-Themen ab: http://www.grundstudium.info/algorithmen/ --Kazim Karadag 1:12, 9. Apr 2006 (CEST)
[[Kategorie:Fakultäts-ABC]]

__NOTOC__

Grundlagen der Informationsmodellierung

2006-05-13T23:40:30Z

Kazi:

Gedächtnisprotokoll GIM Klausur WS05/06

* Quickies
**Sichten auf das System (interne/externe ..)
* ER Diagramm
**Kaufhaus modellieren

*Krankenhaus
**Patient, Chefarzt etc. (Modellierung per Mathematischen Relationen)

*Statechart erstellen

*UML-Modell erstellen

*Metamodell erstellen für ER-Diagramm
**

Benutzer Diskussion:Kazi

2006-05-13T23:04:23Z

Kazi:

Ich denke dise Themen sollten zu Info 4 eingefügt werden. Ciao Kazim

FreitagsrundenWiki:Geschützte Seiten

2006-05-13T23:03:25Z

Kazi:

Themen Informatik 4

*Assembler Programmierung

*Prozessabzweigungen (fork/join)

*Synchronisation
**Schlossvariablen
**Semaphoren
***Einseitige (Kooperierende Prozesse)
***Mehrseitige (Konkurrierende Prozesse)
**Monitore
**Threads (wait/noify/notifyAll)

*Client-Server

*RMI

*Speicherverwaltung/Segmentverwaltung
**Best Fit, Next Fit, Worst Fit (Segmentverw.)
**FIFO, LRU, Second Chance (Seitenverw.)

*Betriebsmittelverwaltung
**FCFS, SJF, Round Robin

Informatik 3 (StuPO90)

2006-05-13T22:53:00Z

Kazi: /* Tipps und nützliche Infos */

<div id="klausuren" style="float:right; width:20%; margin:10px; padding:10px; background-color:#efefef;">
<h2>Klausuren</h2>

SS 2005
* [[Informatik 3/Gedächtnisprotokoll Klausur SS05|Gedächtnisprotokoll]]

WS 2004/2005
* [[Informatik 3/Gedächtnisprotokoll Klausur WS0405|Gedächtnisprotokoll]]

WS 2003/2004
* [http://docs.freitagsrunde.org/Klausuren/Informatik_3/ws0304.pdf Klausur]

SS 2003
* [http://docs.freitagsrunde.org/Klausuren/Informatik_3/ss03.pdf Klausur]

WS 2002/2003
* [http://docs.freitagsrunde.org/klausuren/Informatik_3/ws02-03%20Probeklausur.pdf Probeklausur]

SS 2000
* [http://docs.freitagsrunde.org/Klausuren/Informatik_3/ss00.pdf Klausur]

WS 1999/2000
* [http://docs.freitagsrunde.org/Klausuren/Informatik_3/ws99-00.pdf Klausur]

WS 1997/1998
* [http://docs.freitagsrunde.org/Klausuren/Informatik_3/ws97-98.pdf Klausur]

SS 1997
* [http://docs.freitagsrunde.org/Klausuren/Informatik_3/ss97.pdf Klausur]

</div>

Informatik 3 ist der dritte Teil der [[Informatik (Vorlesung)|Informatik-Vorlesungen]] im [[Grundstudium Informatik]].

== Inhalt ==
Algorithmen und Datenstrukturen in Java und/oder Pseudocode.

* Hashverfahren
* Skip-Listen
* Binäre Suchbäume
* Rekonfigurierende Suchbäume
* B-Bäume
* Graphen: Begriffe und Datenstrukturen
** Breiten-/Tiefensuche
** Minimale Spannbäume
** Kürzeste Wege
* Algorithmen für Optimierungsprobleme
** Dynamisches Programmieren
** Greedy-Algorithmen
** Branch and Bound
** Heuristische Suche

== Tipps und nützliche Infos ==

Die Themen AVL-, Rot-Schwarz Baum kommen immer wieder in Info 3 Klausuren vor. Dabei ist es nicht getan, wenn man die Rotationen bißchen geübt hat, man muss auch spezialfälle üben und sozusagen blind anwenden können. Dabei ist es hilfreich, wenn man Testweise ein Applet zur visuellen Unterstützung einsetzt.

AVL-Baum: http://webpages.ull.es/users/jriera/Docencia/AVL/AVL%20tree%20applet.htm

RB-Baum: http://fbim.fh-regensburg.de/~saj39122/gikasch/start.html

Graphen: http://links.math.rpi.edu/applets/appindex/graphtheory.html

== Weblinks ==
* http://kbs.cs.tu-berlin.de/teaching/ws2005/info3/
* [http://user.cs.tu-berlin.de/~xantippe/Glossar/glossar.html Glossar für Informatik 3]

== Persönliche Kommentare ==
:(Nicht unterschriebene Kommentare werden gelöscht!)

[[Kategorie:Lehrveranstaltungen]]
Deckt viele INFO3-Themen ab: http://www.grundstudium.info/algorithmen/ --Kazim Karadag 1:12, 9. Apr 2006 (CEST)
[[Kategorie:Fakultäts-ABC]]

__NOTOC__

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

2006-05-10T12:44:07Z

Kazi:

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)

:d. Hat Hashing größeren Aufwand, wenn man die Keys sortiert ausgeben will oder ein Binär-Baum ?

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 Alg. 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 ?

:::i. Falls 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 ist Virtueller Speicher und wie funktioniert dieser ?

:a. Was ist Paging ?

:b. Was ist Segmentierung ?

:c. was ist eine Tabellenbasisadresse ?

:d. Gibt es einen Bezug zum B-Baum ?

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 Professor legt großen Wert auf die Komplexitä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.

Und zuletzt .........lernen ist harte Arbeit. Ihr müsst Euch genug Zeit für den Stoff nehmen. Ich empfehle niemandem Mut zur Lücke, wenn ihm was an dem Studium liegt.

Viel Erfolg wünscht euch

kazi@cs.tu-berlin.de

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

2006-05-10T12:38:51Z

Kazi:

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 ist 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 Professor legt großen Wert auf die Komplexitä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.

Und zuletzt .........lernen ist harte Arbeit. Ihr müsst Euch genug Zeit für den Stoff nehmen. Ich empfehle niemandem Mut zur Lücke, wenn ihm was an dem Studium liegt.

Viel Erfolg wünscht euch

kazi@cs.tu-berlin.de

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

2006-05-10T12:27:01Z

Kazi:

Hey Mutax, danke für deine Hilfe, ich war so müde, wollte aber es trotzdem gepostet haben. Ciao Kazim