FreitagsrundenWiki - Benutzerbeiträge [de]

Informatik 3/Gedächtnisprotokoll Klausur SS07

2007-07-26T19:16:30Z

84.190.116.34:

== Aufgabe 1: Multiple Choice ==

Kreuzen Sie jeweils wahr bzw. falsch an:
* ..
* Traversierung mit Breitensuche erzeugt einen aufspannenden Baum.
* Die Höhe eines binären Suchbaumes ist immer um 1 größer, als das Maximum der Höhen seiner Teilbäume.
* Für jedes endliche Optimierungsproblem kann man einen Backtrackingalgorithmus finden der dieses löst.
* Für jedes endliche Optimierungsproblem kann man einen Greedy-algorithmus finden der dieses löst.
<br>

== Aufgabe 2: HashTables ==

Hashtabelle der Größe 4.
*Hashfunktion: h(k) = k mod 4
*Kollisonsauflösung"double hashing" a(k) = k+2
<br>
Vier Werte mit Schlüsseln einfügen und Kollisionen zählen.
(A,5) (B,11) (C,9) (D,14)
A -> 1
B -> 3
C -> 1, 3, 1 , 3 .. (kann nicht eingefügt werden)
D -> 2
0 blieb leer.
<br>
Ist die Anzahl der Kollisionen bei double hashing abhängig von der Reihenfolge in der die Elemente eingefügt werden? Begründung, ggf. Beispiel.
<br>

== Aufgabe 3: Suchbäume ==
'''AVL-Bäume'''
*Einfügen in AVL-Baum
*Einfügen in AVL-Baum
*Löschen aus AVL-Baum
<br>

'''Rot/Schwarz-Bäume'''
*Einfügen in RS-Baum
*Java-Programm schreiben für Höhenberechnung eines Rot-Schwarz-Baumes: int getBlackHeight(Node root)
** Rot-Schwarz-Baum als gültig vorausgesetzt.
** Vorgegebene Implementation:
*** boolean isRed(Node node);
*** boolean isBlack(Node node);
*** class Node{ int color; Node left; Node right; }
<br>

'''B-Baum'''
* Element in B-Baum einfügen.
<br>

== Aufgabe 4: Graphen ==
a) Baue eine Adjazenzmatrix zu folgendem Graphen:

[[Bild:Info3-ss2007-4a.png]]

b) Dijkstra auf folgendem Graph ausführen:

[[Bild:Info3-ss2007-4b.png]]

c) Definiere (formal oder als Text) den Begriff "aufspannender Baum".

d) Führe union(D,F) auf folgender, als Wald realisierter disjunkter Menge aus:

[[Bild:Info3-ss2007-4d.png]]

e) Erstelle den Restflussgraphen zu folgendem Flussgraphen:

[[Bild:Info3-ss2007-4e.png]]

== Aufgabe 5: Übungsorganisation ==
Es herrscht grosser Andrang bei der Sprechstunde. Keiner der wartenden Studierenden erinnert sich an die genaue Ankunftsreihenfolge. Einige erinnern sich jedoch noch an die Leute die bereits warteten. Es soll eine ungefähre Ankunftsreihenfolge bestimmt werden.

{| class="prettytable"
! Name || wartete bereits
|-
| Annett || Daniel, Edeltraut
|-
| Bert || Anett, Daniel, Claudia
|-
| Claudia || -
|-
| Daniel || Claudia
|-
| Edeltraut || Claudia
|}

a) Erstelle einen Graph aus den Erinnerungen der wartenden Studierenden.

b) Nun soll die ungefähre Reihenfolge der Studierenden berechnet werden.

Algorithmus:

Ablauf:

== Aufgabe 6: Dynamisches Programmieren ==

[[Bild:Info3-ss2007-6.png]]


a) Geben Sie eine nicht-rekursive Java-Methode an, die g(m,n) für m, n e N \ {0} berechnet. Die Methode soll dafür polynomielle Laufzeit benötigen

b) Kleinste worst-case-Laufzeitklasse angeben:

O( .... )

== Aufgabe 7: Geld wechseln ==
Gegeben ist ein Betrag, welcher durch möglichst wenige Geldstücke der Grössen { 200, 100, 50, 20, 10, 5, 2, 1 } dargestellt werden werden soll.

a) Geben Sie eine günstige Kodierung für die Geldstücke an

b) Geben Sie eine Zielfunktion und eine Optimierungsrichtung (max/min) an.

c) Geben Sie ein Greedy-Verfahren zur Lösung des Optimierungsproblems an (als Pseudocode oder verbal).

Informatik 3/Gedächtnisprotokoll Klausur SS07

2007-07-26T19:12:10Z

84.190.116.34:

== Aufgabe 1: Multiple Choice ==

* ..
* Traversierung mit Breitensuche erzeugt einen aufspannenden Baum.
* Die Höhe eines binären Suchbaumes ist immer um 1 größer, als das Maximum der Höhen seiner Teilbäume.
* Für jedes endliche Optimierungsproblem kann man einen Backtrackingalgorithmus finden der dieses löst.
* Für jedes endliche Optimierungsproblem kann man einen Greedy-algorithmus finden der dieses löst.
<br>

== Aufgabe 2: HashTables ==

Hashtabelle der Größe 4.
*Hashfunktion: h(k) = k mod 4
*Kollisonsauflösung"double hashing" a(k) = k+2
<br>
Vier Werte mit Schlüsseln einfügen und Kollisionen zählen.
(A,5) (B,11) (C,9) (D,14)
A -> 1
B -> 3
C -> 1, 3, 1 , 3 .. (kann nicht eingefügt werden)
D -> 2
0 blieb leer.
<br>
Ist die Anzahl der Kollisionen bei double hashing abhängig von der Reihenfolge in der die Elemente eingefügt werden? Begründung, ggf. Beispiel.
<br>

== Aufgabe 3: Bäume ==
'''AVL-Bäume'''
*Einfügen in AVL-Baum
*Einfügen in AVL-Baum
*Löschen aus AVL-Baum
<br>

'''Rot/Schwaz-Bäume'''
*Einfügen in RS-Baum
*Java-Programm schreiben für Höhenberechnung eines Rot-Schwarz-Baumes getBlackHeight(Node root)
** Rot-Schwarz-Baum als gültig vorausgesetzt.
** Vorgegebene Implementation:
*** isRed(Node node);
*** isBlack(Node node);
*** class Node{ int color; Node left; Node right; }
<br>

'''B-Baum'''
* Element in B-Baum einfügen.

== Aufgabe 4: Graphen ==
a) Baue eine Adjazenzmatrix zu folgendem Graphen:

[[Bild:Info3-ss2007-4a.png]]

b) Dijkstra auf folgendem Graph ausführen:

[[Bild:Info3-ss2007-4b.png]]

c) Definiere (formal oder als Text) den Begriff "aufspannender Baum".

d) Führe union(D,F) auf folgender, als Wald realisierter disjunkter Menge aus:

[[Bild:Info3-ss2007-4d.png]]

e) Erstelle den Restflussgraphen zu folgendem Flussgraphen:

[[Bild:Info3-ss2007-4e.png]]

== Aufgabe 5: Übungsorganisation ==
Es herrscht grosser Andrang bei der Sprechstunde. Keiner der wartenden Studierenden erinnert sich an die genaue Ankunftsreihenfolge. Einige erinnern sich jedoch noch an die Leute die bereits warteten. Es soll eine ungefähre Ankunftsreihenfolge bestimmt werden.

{| class="prettytable"
! Name || wartete bereits
|-
| Annett || Daniel, Edeltraut
|-
| Bert || Anett, Daniel, Claudia
|-
| Claudia || -
|-
| Daniel || Claudia
|-
| Edeltraut || Claudia
|}

a) Erstelle einen Graph aus den Erinnerungen der wartenden Studierenden.

b) Nun soll die ungefähre Reihenfolge der Studierenden berechnet werden.

Algorithmus:

Ablauf:

== Aufgabe 6: Dynamisches Programmieren ==

<math>g(m, n) = \left\lbrace\begin{matrix} 42 & m = 0 \or n=0 \\ g(m-1, n-1) + g(m, n-1) & m > 0 \and n > 0 \end{matrix}\right.</math>

sobald ich rausfinde wie hier tex geht sieht das da oben auch toll aus :)

a) Geben Sie eine nicht-rekursive Java-Methode an, die g(m,n) für m, n e N \ {0} berechnet. Die Methode soll dafür polynomielle Laufzeit benötigen

b) Kleinste worst-case-Laufzeitklasse angeben:

O( .... )

== Aufgabe 7: Geld wechseln ==
Gegeben ist ein Betrag, welcher durch möglichst wenige Geldstücke der Grössen { 200, 100, 50, 20, 10, 5, 2, 1 } dargestellt werden werden soll.

a) Geben Sie eine günstige Kodierung für die Geldstücke an

b) Geben Sie eine Zielfunktion und eine Optimierungsrichtung (max/min) an.

c) Geben Sie ein Greedy-Verfahren zur Lösung des Optimierungsproblems an (als Pseudocode oder verbal).

Integrierte Veranstaltung

2007-07-26T18:58:48Z

84.190.116.34:

Vorlesung und Tutorium nicht ganz so strickt getrennt, Themengebiete werden schon direkt im Vorlesungsteil genauer besprochen (gelegentlich Gruppenarbeit u.ä.), oft als 4-Stunden-Block mit Pause zu finden.

Informatik 3/Gedächtnisprotokoll Klausur SS07

2007-07-26T15:10:28Z

84.190.116.34: /* 1. Aufgabe: Multiple Choice */

== 1. Aufgabe: Multiple Choice ==

* ..
* Traversierung mit Breitensuche erzeugt einen aufspannenden Baum.
* Die Höhe eines binären Suchbaumes ist immer um 1 größer, als das Maximum der Höhen seiner Teilbäume.
* Für jedes endliche Optimierungsproblem kann man einen Backtrackingalgorithmus finden der dieses löst.
* Für jedes endliche Optimierungsproblem kann man einen Greedy-algorithmus finden der dieses löst.
<br>

== HashTables ==

Hashtabelle der Größe 4.
*Hashfunktion: h(k) = k mod 4
*Kollisonsauflösung"double hashing" a(k) = k+2
<br>
Vier Werte mit Schlüsseln einfügen und Kollisionen zählen.
(A,5) (B,11) (C,9) (D,14)
A -> 1
B -> 3
C -> 1, 3, 1 , 3 .. (kann nicht eingefügt werden)
D -> 2
0 blieb leer.
<br>
Ist die Anzahl der Kollisionen bei double hashing abhängig von der Reihenfolge in der die Elemente eingefügt werden? Begründung, ggf. Beispiel.
<br>

== AVL-Bäume ==
*Einfügen in AVL-Baum
*Einfügen in AVL-Baum
*Löschen aus AVL-Baum
<br>

== Rot-Schwaz-Bäume ==
*Einfügen in RS-Baum
*Java-Programm schreiben für Höhenberechnung eines Rot-Schwarz-Baumes getBlackHeight(Node root)
** Rot-Schwarz-Baum als gültig vorausgesetzt.
** Vorgegebene Implementation:
*** isRed(Node node);
*** isBlack(Node node);
*** class Node{ int color; Node left; Node right; }
<br>

== B-Baum ==
* Element in B-Baum einfügen.

== Aufgabe 4: Graphen ==
a) Baue eine Adjazenzmatrix zu folgendem Graphen:

[[Bild:Info3-ss2007-4a.png]]

b) Dijkstra auf folgendem Graph ausführen:

[[Bild:Info3-ss2007-4b.png]]

c) Definiere (formal oder als Text) den Begriff "aufspannender Baum".

d) Führe union(D,F) auf folgender, als Wald realisierter disjunkter Menge aus:
(Graph folgt)

e) Erstelle den Restflussgraphen zu folgendem Flussgraphen:
(Graph folgt)

== Aufgabe 5: Übungsorganisation ==
Hab ich, trag ich gleich ein [[Benutzer:TomyLobo|TomyLobo]]

== Aufgabe 6: Dynamisches Programmieren ==
Hab ich, trag ich gleich ein [[Benutzer:TomyLobo|TomyLobo]]

== Aufgabe 7: Geld wechseln ==
Hab ich, trag ich gleich ein [[Benutzer:TomyLobo|TomyLobo]]

Informatik 3/Gedächtnisprotokoll Klausur SS07

2007-07-26T14:10:55Z

84.190.116.34:

== 1. Aufgabe: Multiple Choice ==

* ..
* ..
* Die Höhe eines binären Suchbaumes ist immer um 1 größer, als das Maximum der Höhen seiner Teilbäume.
* Für jedes endliche Optimierungsproblem kann man einen Backtrackingalgorithmus finden der dieses löst.
* Für jedes endliche Optimierungsproblem kann man einen Greedy-algorithmus finden der dieses löst.
<br>

== HashTables ==

Hashtabelle der Größe 4.
*Hashfunktion: h(k) = k mod 4
*Kollisonsauflösung"double hashing" a(k) = k+2
<br>
Vier Werte mit Schlüsseln einfügen und Kollisionen zählen.
(A,5) (B,11) (C,9) (D,14)
A -> 1
B -> 3
C -> 1, 3, 1 , 3 .. (kann nicht eingefügt werden)
D -> 2
0 blieb leer.
<br>
Ist die Anzahl der Kollisionen bei double hashing abhängig von der Reihenfolge in der die Elemente eingefügt werden? Begründung, ggf. Beispiel.
<br>

== AVL-Bäume ==
*Einfügen in AVL-Baum
*Einfügen in AVL-Baum
*Löschen aus AVL-Baum
<br>

== Rot-Schwaz-Bäume ==
*Einfügen in RS-Baum
*Java-Programm schreiben für Höhenberechnung eines Rot-Schwarz-Baumes getBlackHeight(Node root)
** Rot-Schwarz-Baum als gültig vorausgesetzt.
** Vorgegebene Implementation:
*** isRed(Node node);
*** isBlack(Node node);
*** class Node{ int color; Node left; Node right; }
<br>

== B-Baum ==
* Element in B-Baum einfügen.

Informatik 3 (StuPO90)

2007-07-26T13:51:14Z

84.190.116.34:

<div id="klausuren" style="float:right; width:20%; margin:10px; padding:10px; background-color:#efefef;">
<h2>Klausuren</h2>
SS 2007
* [[Informatik 3/Gedächtnisprotokoll Klausur SS07|Gedächtnisprotokoll Klausur]]

SS 2006
* [[Informatik 3/Gedächtnisprotokoll Klausur SS06|Gedächtnisprotokoll Klausur]]
* [[Informatik B (StuPO90)/Mündliche Prüfung SoSe 2006|Gedächtnisprotokoll Mündliche Prüfung]]

SS 2005
* [[Informatik 3/Gedächtnisprotokoll Klausur SS05|Gedächtnisprotokoll]]
* [http://docs.freitagsrunde.org/Klausuren/Informatik_3/ss05_bsp_klausur.pdf Probeklausur]

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 Probeklausur]

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>

{{EntsprechungB|[[MPGI 2 (Bachelor)]] und [[TechGI 3 (Bachelor)]]}}

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/ws2006/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 4 (StuPO90)/Gedächtnisprotokoll Klausur SoSe 2007

2007-07-26T13:44:00Z

84.190.116.34: /* Aufgabe 4: Monitore (12 Punkte) */

== Aufgabe 1: Kurze Fragen (10 Punkte) ==
* Unterschiede und Vorteile von synchroner und asynchroner Nachrichtenübertragung?
** blockierend / nicht blockieren vs. Nachricht geht evtl. verloren

* Vorteile von leichtgewichtigen Prozessen
** schnellerer Prozesswechsel, da gemeinsamer Adressraum
** einfache Implementierung
** eigener Scheduler ?

* Erkläre die zwei Stufen von Interruptbehandlung. Grund der Zweistufigkeit?
** Stufe 1: nicht unterbrechbar, nur nötigste Behandlung (speichern).
** Stufe 2: abschließende Behandlung des interrupts...
** Grund: Nicht unterbrechbarer Zeitraum mötlichst klein, damit keine/wenige Interrupts verloren gehen.

<br>

== Aufgabe 2: Assembler (15 Punkte) ==
Programmieren sie in Assembler die Funktion _binom(int *a, int *b)

*Berechne a²+2ab+b² (!) und speichere das ergebnis in *b und gib 0 bei geglückter Operation zurück.
*Falls a<0 oder a>32767 oder b>32767 oder b<-32768 gib sofort -1 zurück.
*Bei der addition der werte a², b² und 2ab kann es zum Überlauf kommen.
**Falls das passiert gib ebenfalls -1 zurück.(Rückgaben erfolgen wie üblich im Register D0)
*Schreibe desweiteren eine Subroutine, die das Quadrat einer Zahl berechnet (geht in 2 Zeilen).
<br>

== Aufgabe 3: Semaphoren (10 Punkte) ==
Elefanten und Mäuse gehen auf ein Schiff.
Dabei sollen immer möglichst doppelt so viele Möuse wie Elefanten auf dem Schiff sein.
Nur eine Differenz von 1 ist erlaubt..
<br>

== Aufgabe 4: Monitore (12 Punkte) ==
In einem Schwimmbad gibt es ein Schwimmbecken.
Es gibt Turmspringer, Schwimmer und den Bademeister.
Synchronisiere mit den Folgenden Regeln über Monitore:
*Turmspringer und Schwimmer dürfen das Schwimmbecken nicht gleichzeitig benutzen.
*Wenn kein Bademeister anwesend ist, darf kein Schwimmer ins Becken.
*Turmspringer dürfen auch ins Becken springen, wenn Schwimmer warten, weil kein Bademeister da ist.
*Wenn ein Bademeister anwesend ist, haben die Schwimmer vor den Turmspringern Vorrang.
*Der Bademeister darf erst Feierabend machen (weggehen), wenn kein Schwimmer mehr im Becken ist
*Der Bademeister darf insbesondere auch dann gehen, wenn noch Schwimmer am Beckenrand warten (voraussgesetzt, es befindet sich kein Schwimmer im Becken).
*Es kann davon ausgegangen werden, dass es maximal einen Bademeister gibt.
<br>
Irgendwie komme ich nicht auf 50 Punkte :>

Informatik 4 (StuPO90)/Gedächtnisprotokoll Klausur SoSe 2007

2007-07-26T13:41:47Z

84.190.116.34: /* Aufgabe 4: Monitore (12 Punkte) */

Informatik 4 (StuPO90)/Gedächtnisprotokoll Klausur SoSe 2007

2007-07-26T13:41:33Z

84.190.116.34: /* Aufgabe 3: Semaphoren (10 Punkte) */

== Aufgabe 1: Kurze Fragen (10 Punkte) ==
* Unterschiede und Vorteile von synchroner und asynchroner Nachrichtenübertragung?
** blockierend / nicht blockieren vs. Nachricht geht evtl. verloren

* Vorteile von leichtgewichtigen Prozessen
** schnellerer Prozesswechsel, da gemeinsamer Adressraum
** einfache Implementierung
** eigener Scheduler ?

* Erkläre die zwei Stufen von Interruptbehandlung. Grund der Zweistufigkeit?
** Stufe 1: nicht unterbrechbar, nur nötigste Behandlung (speichern).
** Stufe 2: abschließende Behandlung des interrupts...
** Grund: Nicht unterbrechbarer Zeitraum mötlichst klein, damit keine/wenige Interrupts verloren gehen.

<br>

== Aufgabe 2: Assembler (15 Punkte) ==
Programmieren sie in Assembler die Funktion _binom(int *a, int *b)

*Berechne a²+2ab+b² (!) und speichere das ergebnis in *b und gib 0 bei geglückter Operation zurück.
*Falls a<0 oder a>32767 oder b>32767 oder b<-32768 gib sofort -1 zurück.
*Bei der addition der werte a², b² und 2ab kann es zum Überlauf kommen.
**Falls das passiert gib ebenfalls -1 zurück.(Rückgaben erfolgen wie üblich im Register D0)
*Schreibe desweiteren eine Subroutine, die das Quadrat einer Zahl berechnet (geht in 2 Zeilen).
<br>

== Aufgabe 3: Semaphoren (10 Punkte) ==
Elefanten und Mäuse gehen auf ein Schiff.
Dabei sollen immer möglichst doppelt so viele Möuse wie Elefanten auf dem Schiff sein.
Nur eine Differenz von 1 ist erlaubt..
<br>

= Aufgabe 4: Monitore (12 Punkte) =
In einem Schwimmbad gibt es ein Schwimmbecken.
Es gibt Turmspringer, Schwimmer und den Bademeister.
Synchronisiere mit den Folgenden Regeln über Monitore:
*Turmspringer und Schwimmer dürfen das Schwimmbecken nicht gleichzeitig benutzen.
*Wenn kein Bademeister anwesend ist, darf kein Schwimmer ins Becken.
*Turmspringer dürfen auch ins Becken springen, wenn Schwimmer warten, weil kein Bademeister da ist.
*Wenn ein Bademeister anwesend ist, haben die Schwimmer vor den Turmspringern Vorrang.
*Der Bademeister darf erst Feierabend machen (weggehen), wenn kein Schwimmer mehr im Becken ist
*Der Bademeister darf insbesondere auch dann gehen, wenn noch Schwimmer am Beckenrand warten (voraussgesetzt, es befindet sich kein Schwimmer im Becken).
<br>
Irgendwie komme ich nicht auf 50 Punkte :>

Informatik 4 (StuPO90)/Gedächtnisprotokoll Klausur SoSe 2007

2007-07-26T13:33:46Z

84.190.116.34:

== Aufgabe 1: Kurze Fragen (10 Punkte) ==
* Unterschiede und Vorteile von synchroner und asynchroner Nachrichtenübertragung?
** blockierend / nicht blockieren vs. Nachricht geht evtl. verloren

* Vorteile von leichtgewichtigen Prozessen
** schnellerer Prozesswechsel, da gemeinsamer Adressraum
** einfache Implementierung
** eigener Scheduler ?

* Erkläre die zwei Stufen von Interruptbehandlung. Grund der Zweistufigkeit?
** Stufe 1: nicht unterbrechbar, nur nötigste Behandlung (speichern).
** Stufe 2: abschließende Behandlung des interrupts...
** Grund: Nicht unterbrechbarer Zeitraum mötlichst klein, damit keine/wenige Interrupts verloren gehen.

<br>

== Aufgabe 2: Assembler (15 Punkte) ==
Programmieren sie in Assembler die Funktion _binom(int *a, int *b)

*Berechne a²+2ab+b² (!) und speichere das ergebnis in *b und gib 0 bei geglückter Operation zurück.
*Falls a<0 oder a>32767 oder b>32767 oder b<-32768 gib sofort -1 zurück.
*Bei der addition der werte a², b² und 2ab kann es zum Überlauf kommen.
**Falls das passiert gib ebenfalls -1 zurück.(Rückgaben erfolgen wie üblich im Register D0)
*Schreibe desweiteren eine Subroutine, die das Quadrat einer Zahl berechnet (geht in 2 Zeilen).
<br>

= Aufgabe 3: Semaphoren (10 Punkte) =
Elefanten und Mäuse gehen auf ein Schiff.
Dabei sollen immer möglichst doppelt so viele Möuse wie Elefanten auf dem Schiff sein.
Nur eine Differenz von 1 ist erlaubt..
<br>

= Aufgabe 4: Monitore (12 Punkte) =
In einem Schwimmbad gibt es ein Schwimmbecken.
Es gibt Turmspringer, Schwimmer und den Bademeister.
Synchronisiere mit den Folgenden Regeln über Monitore:
*Turmspringer und Schwimmer dürfen das Schwimmbecken nicht gleichzeitig benutzen.
*Wenn kein Bademeister anwesend ist, darf kein Schwimmer ins Becken.
*Turmspringer dürfen auch ins Becken springen, wenn Schwimmer warten, weil kein Bademeister da ist.
*Wenn ein Bademeister anwesend ist, haben die Schwimmer vor den Turmspringern Vorrang.
*Der Bademeister darf erst Feierabend machen (weggehen), wenn kein Schwimmer mehr im Becken ist
*Der Bademeister darf insbesondere auch dann gehen, wenn noch Schwimmer am Beckenrand warten (voraussgesetzt, es befindet sich kein Schwimmer im Becken).
<br>
Irgendwie komme ich nicht auf 50 Punkte :>

Informatik 4 (StuPO90)/Gedächtnisprotokoll Klausur SoSe 2007

2007-07-26T13:12:15Z

84.190.116.34:

== Kurze Fragen ==
* Unterschiede und Vorteile von synchroner und asynchroner Nachrichtenübertragung?
** blockierend / nicht blockieren vs. Nachricht geht evtl. verloren

* Vorteile von leichtgewichtigen Prozessen
** schnellerer Prozesswechsel, da gemeinsamer Adressraum
** einfache Implementierung
** eigener Scheduler ?

* Erkläre die zwei Stufen von Interruptbehandlung. Grund der Zweistufigkeit?
** Stufe 1: nicht unterbrechbar, nur nötigste Behandlung (speichern).
** Stufe 2: abschließende Behandlung des interrupts...
** Grund: Nicht unterbrechbarer Zeitraum mötlichst klein, damit keine/wenige Interrupts verloren gehen.

Informatik 4 (StuPO90)

2007-07-26T13:06:04Z

84.190.116.34:

<div id="klausuren" style="float:right; width:20%; margin:10px; padding:10px; background-color:#efefef;">
<h3>Klausuren</h3>
SS 2007
* [[Informatik 4 (StuPO90)/Gedächtnisprotokoll Klausur SoSe 2007|Gedächtnisprotokoll]]

SS 2006
* [[Informatik 4 (StuPO90)/Stichpunkte zur Klausur SoSe 2006|vor-Klausur-Infos]]
* [[Informatik B (StuPO90)/Mündliche Prüfung SoSe 2006|Gedächtnisprotokoll Mündliche Prüfung]]

SS 2005
* [[Informatik 4 (StuPO90)/Gedächtnisprotokoll Klausur SoSe 2005|Gedächtnisprotokoll]]
* [[Informatik 4 (StuPO90)/Stichpunkte zur Klausur SoSe 2005|vor-Klausur-Infos]]

WS 2002/2003
* [http://docs.freitagsrunde.org/Klausuren/Informatik_4/Klausurfragen03.pdf Klausur]

WS 2001/2002
* [http://docs.freitagsrunde.org/Klausuren/Informatik_4/ws0102.pdf Klausur]

WS 2000/2001
* [http://docs.freitagsrunde.org/Klausuren/Informatik_4/ws0001.pdf Klausur]

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

</div>

{{EntsprechungB|[[MPGI 2 (Bachelor)]] und [[TechGI 3 (Bachelor)]]}}

Informatik 4 ist der vierte Teil der [[Informatik (Vorlesung)|Informatik-Vorlesungen]] im [[Grundstudium Informatik]].

= Inhalt =
* Hardwarenahe Programmierung mit Assembler
* Parallele Programmierung in Java
* ...
* Assembler
* Einf. Betriebssysteme
* Nebenläufigkeit und Synchronisation
* Prozeßbeschreibung
* Prozeßverwaltung
* Leichtgewichtige Prozesse
* Betriebssystem-Kern
* Schloßvariablen
* Semaphore
* Monitore
* Nachrichten
* Kommunikationskanäle
* Prozedurfernaufrufe
* Ein- und Ausgabe
* Speicherverwaltung
* Betriebsmittelvergabe

= Tipps =
Man muss am Anfang Assembler für die 68000er Plattform von Motorola schreiben. Das geht hier an der Uni nur im Raum EN 268 für den man den jeweiligen Semester-Tür-Code braucht.
Einfacher und vielleicht auch Lehrreicher ist es den Assemblercode in einem Emulator auszuführen, da man dort z.B. auch genau in die Register hineinschauen kann. Einen solchen Simulator gibts hier:

Motorola 68K Simulator sind mir zwei bekannt: [http://www.informatik.fh-mannheim.de/~ihme/rurd_2005ss/M68k-Programmierung.html BSVC] ([http://ds2.etech.fh-hamburg.de/snd/bsvc.html auch hier]) der theoretisch auch unter Unix läuft und [http://www.monroeccc.edu/ckelly/EASy68K.htm Easy68k] der leider nur unter Windows läuft, dafür aber schöne Dokumentation zu dem 68k Assembler enthält.

BSVC kompiliert auf neueren System evtl. nicht problemlos. [http://user.cs.tu-berlin.de/~felixf/bsvc/README Hier] steht wie es mit Hilfe eines Patches geht, der die Änderungen von [http://www.mdlug.de/bibo/knowhow/prog/howto-bsvc.shtml] und noch etwas mehr in den Quellcode integriert.

Die Assembler Referenz gibt der Lehrbereich nur in gedruckter Form heraus - die [http://www.informatik.fh-mannheim.de/~ihme/Software/BSVC/68k_manual.pdf gibt es anderswo aber auch als PDF].

Zum Thema Semaphoren gibt es [[{{PAGENAME}}/Semaphoren|hier im Wiki eine eigene alternative Erklärung]], die viele Info 4 Teilnehmer einfacher verständlich finden.

==Links==

* [http://pdv.cs.tu-berlin.de/Info4-SS2007/ Informatik 4 (SS07)]
* [http://pdv.cs.tu-berlin.de/ Fachgebiet Prozessdatenverarbeitung]
* [http://pdv.cs.tu-berlin.de/Info4-SS2007/folien/ Folien SS2007 (Passwort-geschützt, Passwort in der Lehrveranstaltung oder per Nachfrage erhältlich)]

[[Kategorie:Lehrveranstaltungen]]
[[Kategorie:Fakultäts-ABC]]

__NOTOC__