FreitagsrundenWiki - Benutzerbeiträge [de]

Softwaretechnik

2007-10-15T04:22:18Z

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

<div id="protokolle" style="float:right; width:20%; margin:10px; padding:10px; background-color:#efefef;">
=== Klausuren ===
WS 2004/2005
* [http://docs.freitagsrunde.org/Klausuren/Softwaretechnik/klausur-WS0405.ps Klausur]

SS 2004
* [http://docs.freitagsrunde.org/klausuren/Softwaretechnik/klausur-SS04.ps Musterlösung]

WS 2003/2004
* [http://docs.freitagsrunde.org/Klausuren/Softwaretechnik/klausur-WS0304.ps Klausur]

SS 2003
* [http://docs.freitagsrunde.org/Klausuren/Softwaretechnik/klausur-SS03.ps Klausur]

WS 2002/2003
* [http://docs.freitagsrunde.org/Klausuren/Softwaretechnik/klausur-WS0203.ps Klausur]

SS 2002
* [http://docs.freitagsrunde.org/Klausuren/Softwaretechnik/ss2002.ps.gz Klausur]
* [http://docs.freitagsrunde.org/Klausuren/Softwaretechnik/ss02_musterloesung.ps.gz Musterlösung]

SS 2001
* [http://docs.freitagsrunde.org/Klausuren/Softwaretechnik/ss2001.ps.gz Klausur]
* [http://docs.freitagsrunde.org/Klausuren/Softwaretechnik/SWT-Basis_SS2001_Musterloesung.ps.gz Musterlösung]

WS 2000/2001
* [http://docs.freitagsrunde.org/Klausuren/Softwaretechnik/ws0001_musterloesung.ps.gz Musterlösung]

SS 2000
* [http://docs.freitagsrunde.org/Klausuren/Softwaretechnik/SWT-Basis_SS2001_Musterloesung.ps.gz Musterlösung]

WS 1999/2000
* [http://docs.freitagsrunde.org/Klausuren/Softwaretechnik/ws9900_musterloesung.ps.gz Musterlösung]

SS 1999
* [http://docs.freitagsrunde.org/Klausuren/Softwaretechnik/SWT-Basis_SS1999_Musterloesung.ps.gz Musterlösung]

WS 1998/1999
* [http://docs.freitagsrunde.org/Klausuren/Softwaretechnik/ws9899.ps.gz Musterlösung]

SS 1998
* [http://docs.freitagsrunde.org/Klausuren/Softwaretechnik/ss98_musterloesung.ps.gz Musterlösung]

WS 1997/1998
* [http://docs.freitagsrunde.org/Klausuren/Softwaretechnik/ws9798_musterloesung.ps.gz Musterlösung]

SS 1997
* [http://docs.freitagsrunde.org/Klausuren/Softwaretechnik/ss1997.ps.gz Musterlösung]

WS 1996/1997
* [http://docs.freitagsrunde.org/Klausuren/Softwaretechnik/ws9697_musterloesung.ps.gz Musterlösung]

SS 1996
* [http://docs.freitagsrunde.org/Klausuren/Softwaretechnik/ss96.ps.gz Musterlösung]

WS 1995/1996
* [http://docs.freitagsrunde.org/Klausuren/Softwaretechnik/ws9596_musterloesung.ps.gz Musterlösung]

</div>

'''Softwaretechnik''' ist eine [[Basisveranstaltung]] im Fachgebiet SWT (Studiengebiet SSG) im [[Hauptstudium|Informatik-Hauptstudium]].

== Inhalt ==
In der Lehrveranstaltung werden Methoden und Techniken zur Softwareentwicklung behandelt, die die Grundlage für weitere Vertiefung in das Studiengebiet Softwaretechnik und Systemgestaltung bilden. Schwerpunkte sind: Anforderungsermittlung, Software-Entwurf und -Konstruktion, Spezifikationstechniken, Qualitätssicherung und Software-Architektur.

== Tipps und nützliche Infos ==

Die Vorlesung gliedert sich in drei Teile: Fusion, Object-Z und Statecharts. In jedem Bereich gibt es eine Übungsaufgabe, wobei die Fusion-Aufgabe 50% zählt (und äußerst umfangreich und schreibintensiv ist)

Literatur:
unwichtig, gibt diverse Unterlagen zu den einzelnen Bereichen

Zitat von der [[MPGI 3 (Bachelor)|MPGI3]]-Seite:

Für Diplomstudiengänge ([[Lehrveranstaltungen Informatik Diplom (StuPO90)|Informatik]], TI, TWM, Wi-Ing, ITM u.A.) [ist MPGI 3] auch als [[Basisveranstaltung]] [[Softwaretechnik]] anrechenbar.

== Weblinks ==
* [http://www.swt.cs.tu-berlin.de/lehre/swt/index.html/ Softwaretechnik (jeweils aktuelles Semester)]

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

* WS05/06: Im Informatik-Studium muß man viel Unsinn machen - aber dieser Kurs übertrifft nochmal alles. Die Krönung erwartet einen mitunter bei der Klausur. Hier muß man in sich windeseile in die Logik Anderer reindenken, um teilweise recht komplizierte Spezifikationen vornehmen zu können. Ich bin von diesem Kurs maßlos enttäuscht. Was mich am meisten stört, ist die unselige Zettelwirtschaft. Anstatt sich an einem Lehrbuch zu orientieren, hantiert man mit hunderten von Zettel rum. Unmöglich. Und eines ist klar: Wenn auf diese Weise in der Realität Software entwicklelt wird, dann verzichte ich freiwillig auf jede weitere Flugreise...TimoS.

* WS04/05 (Veranstalter: Stephan Herrmann): Man sollte es sich wirklich mehrfach ueberlegen, ob man diese Veranstaltung belegt. Positiv ist lediglich, dass es ein A-Kurs ist und dass bei der Klausur 35% zum Bestehen reichen. Alles andere ist sehr negativ. Die Tutoren wirken extrem unmotiviert und korrigieren ziemlich willkuerlich.

Die Vorlesung muss man nicht besuchen. Der Dozent labert ewig lange bei voellig unwichtigen Sachen rum und zieht dann die interessanten 10 Folien am Schluss in maximal 5 Minuten durch...

Totaler Mist. NICHT BELEGEN! FelixB

* Völlig sinnloser Spezifikationsmarathon. Nur belegen, wenn man Vertiefungsveranstaltungen bei SWT besuchen will/muss. Wenn schon, dann im SS besuchen, wenn Jähnichen die VL macht. --[[Benutzer:Felix|Felix]] 12:14, 12. Aug 2005 (CEST)

* Hmm - ich fand die Veranstaltung ehrlich gesagt nicht ganz so schlecht. Vielleicht sollte ich dazu sagen, dass ich seit 5 Jahren neben dem Studium in einer Firma arbeite, in der viel und professionell Software entwickelt wird. Natuerlich sind die Beispiele der Veranstaltung extrem an den Haaren herbeigezogen (wer spezifiziert schon eine Autowerkstatt komplett durch) - aber man kann dennoch viel lernen. Und sei es die Einsicht, dass man nicht alles spezifizieren kann und muss [Vor allem nicht mit den gelehrten Methoden...]. Jedenfalls ist das, was hier einige als sinnloses Geschwafel abtun, in der Praxis ziemlich wichtig. Es geht einfach nichts ohne eine (vernünftige) Spezifikation und Qualitätssicherung. Das muss man nicht toll finden, aber es is leider so, dass man ohne Pflichtenhefte und Projektmanagement verloren hat. Das es kein Lehrbuch gibt finde ich hervorragend, besser als wieder 30 Euro für ein Buch ausgeben zu müssen, von dem dann nur 20% benutzt werden. Ausserdem werden die Aufgaben immer wieder verändert und angepasst. Mein Tutor war Rodger, ich muss sagen das Tut war einfach nur Klasse! Die Vorlesung habe ich maximal dreimal besucht, Dozent war Kammüller. --[[Benutzer:Mutax|florian]] 14:02, 19. Feb. 2007 (CET)

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

__NOTOC__

Softwaretechnik

2007-10-15T04:21:37Z

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

<div id="protokolle" style="float:right; width:20%; margin:10px; padding:10px; background-color:#efefef;">
=== Klausuren ===
WS 2004/2005
* [http://docs.freitagsrunde.org/Klausuren/Softwaretechnik/klausur-WS0405.ps Klausur]

SS 2004
* [http://docs.freitagsrunde.org/klausuren/Softwaretechnik/klausur-SS04.ps Musterlösung]

WS 2003/2004
* [http://docs.freitagsrunde.org/Klausuren/Softwaretechnik/klausur-WS0304.ps Klausur]

SS 2003
* [http://docs.freitagsrunde.org/Klausuren/Softwaretechnik/klausur-SS03.ps Klausur]

WS 2002/2003
* [http://docs.freitagsrunde.org/Klausuren/Softwaretechnik/klausur-WS0203.ps Klausur]

SS 2002
* [http://docs.freitagsrunde.org/Klausuren/Softwaretechnik/ss2002.ps.gz Klausur]
* [http://docs.freitagsrunde.org/Klausuren/Softwaretechnik/ss02_musterloesung.ps.gz Musterlösung]

SS 2001
* [http://docs.freitagsrunde.org/Klausuren/Softwaretechnik/ss2001.ps.gz Klausur]
* [http://docs.freitagsrunde.org/Klausuren/Softwaretechnik/SWT-Basis_SS2001_Musterloesung.ps.gz Musterlösung]

WS 2000/2001
* [http://docs.freitagsrunde.org/Klausuren/Softwaretechnik/ws0001_musterloesung.ps.gz Musterlösung]

SS 2000
* [http://docs.freitagsrunde.org/Klausuren/Softwaretechnik/SWT-Basis_SS2001_Musterloesung.ps.gz Musterlösung]

WS 1999/2000
* [http://docs.freitagsrunde.org/Klausuren/Softwaretechnik/ws9900_musterloesung.ps.gz Musterlösung]

SS 1999
* [http://docs.freitagsrunde.org/Klausuren/Softwaretechnik/SWT-Basis_SS1999_Musterloesung.ps.gz Musterlösung]

WS 1998/1999
* [http://docs.freitagsrunde.org/Klausuren/Softwaretechnik/ws9899.ps.gz Musterlösung]

SS 1998
* [http://docs.freitagsrunde.org/Klausuren/Softwaretechnik/ss98_musterloesung.ps.gz Musterlösung]

WS 1997/1998
* [http://docs.freitagsrunde.org/Klausuren/Softwaretechnik/ws9798_musterloesung.ps.gz Musterlösung]

SS 1997
* [http://docs.freitagsrunde.org/Klausuren/Softwaretechnik/ss1997.ps.gz Musterlösung]

WS 1996/1997
* [http://docs.freitagsrunde.org/Klausuren/Softwaretechnik/ws9697_musterloesung.ps.gz Musterlösung]

SS 1996
* [http://docs.freitagsrunde.org/Klausuren/Softwaretechnik/ss96.ps.gz Musterlösung]

WS 1995/1996
* [http://docs.freitagsrunde.org/Klausuren/Softwaretechnik/ws9596_musterloesung.ps.gz Musterlösung]

</div>

'''Softwaretechnik''' ist eine [[Basisveranstaltung]] im Fachgebiet SWT (Studiengebiet SSG) im [[Hauptstudium|Informatik-Hauptstudium]].

== Inhalt ==
In der Lehrveranstaltung werden Methoden und Techniken zur Softwareentwicklung behandelt, die die Grundlage für weitere Vertiefung in das Studiengebiet Softwaretechnik und Systemgestaltung bilden. Schwerpunkte sind: Anforderungsermittlung, Software-Entwurf und -Konstruktion, Spezifikationstechniken, Qualitätssicherung und Software-Architektur.

== Tipps und nützliche Infos ==

Die Vorlesung gliedert sich in drei Teile: Fusion, Object-Z und Statecharts. In jedem Bereich gibt es eine Uebungsaufgabe, wobei die Fusion-Aufgabe 50% zaehlt (und äußerst umfangreich und schreibintensiv ist)

Literatur:
unwichtig, gibt diverse Unterlagen zu den einzelnen Bereichen

Zitat von der [[MPGI 3 (Bachelor)|MPGI3]]-Seite:

Für Diplomstudiengänge ([[Lehrveranstaltungen Informatik Diplom (StuPO90)|Informatik]], TI, TWM, Wi-Ing, ITM u.A.) [ist MPGI 3] auch als [[Basisveranstaltung]] [[Softwaretechnik]] anrechenbar.

== Weblinks ==
* [http://www.swt.cs.tu-berlin.de/lehre/swt/index.html/ Softwaretechnik (jeweils aktuelles Semester)]

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

* WS05/06: Im Informatik-Studium muß man viel Unsinn machen - aber dieser Kurs übertrifft nochmal alles. Die Krönung erwartet einen mitunter bei der Klausur. Hier muß man in sich windeseile in die Logik Anderer reindenken, um teilweise recht komplizierte Spezifikationen vornehmen zu können. Ich bin von diesem Kurs maßlos enttäuscht. Was mich am meisten stört, ist die unselige Zettelwirtschaft. Anstatt sich an einem Lehrbuch zu orientieren, hantiert man mit hunderten von Zettel rum. Unmöglich. Und eines ist klar: Wenn auf diese Weise in der Realität Software entwicklelt wird, dann verzichte ich freiwillig auf jede weitere Flugreise...TimoS.

* WS04/05 (Veranstalter: Stephan Herrmann): Man sollte es sich wirklich mehrfach ueberlegen, ob man diese Veranstaltung belegt. Positiv ist lediglich, dass es ein A-Kurs ist und dass bei der Klausur 35% zum Bestehen reichen. Alles andere ist sehr negativ. Die Tutoren wirken extrem unmotiviert und korrigieren ziemlich willkuerlich.

Die Vorlesung muss man nicht besuchen. Der Dozent labert ewig lange bei voellig unwichtigen Sachen rum und zieht dann die interessanten 10 Folien am Schluss in maximal 5 Minuten durch...

Totaler Mist. NICHT BELEGEN! FelixB

* Völlig sinnloser Spezifikationsmarathon. Nur belegen, wenn man Vertiefungsveranstaltungen bei SWT besuchen will/muss. Wenn schon, dann im SS besuchen, wenn Jähnichen die VL macht. --[[Benutzer:Felix|Felix]] 12:14, 12. Aug 2005 (CEST)

* Hmm - ich fand die Veranstaltung ehrlich gesagt nicht ganz so schlecht. Vielleicht sollte ich dazu sagen, dass ich seit 5 Jahren neben dem Studium in einer Firma arbeite, in der viel und professionell Software entwickelt wird. Natuerlich sind die Beispiele der Veranstaltung extrem an den Haaren herbeigezogen (wer spezifiziert schon eine Autowerkstatt komplett durch) - aber man kann dennoch viel lernen. Und sei es die Einsicht, dass man nicht alles spezifizieren kann und muss [Vor allem nicht mit den gelehrten Methoden...]. Jedenfalls ist das, was hier einige als sinnloses Geschwafel abtun, in der Praxis ziemlich wichtig. Es geht einfach nichts ohne eine (vernünftige) Spezifikation und Qualitätssicherung. Das muss man nicht toll finden, aber es is leider so, dass man ohne Pflichtenhefte und Projektmanagement verloren hat. Das es kein Lehrbuch gibt finde ich hervorragend, besser als wieder 30 Euro für ein Buch ausgeben zu müssen, von dem dann nur 20% benutzt werden. Ausserdem werden die Aufgaben immer wieder verändert und angepasst. Mein Tutor war Rodger, ich muss sagen das Tut war einfach nur Klasse! Die Vorlesung habe ich maximal dreimal besucht, Dozent war Kammüller. --[[Benutzer:Mutax|florian]] 14:02, 19. Feb. 2007 (CET)

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

__NOTOC__

Softwaretechnik

2007-10-15T04:20:34Z

TomyLobo: /* Tipps und nützliche Infos */ kann das jemand noch irgendwo einordnen bitte?

<div id="protokolle" style="float:right; width:20%; margin:10px; padding:10px; background-color:#efefef;">
=== Klausuren ===
WS 2004/2005
* [http://docs.freitagsrunde.org/Klausuren/Softwaretechnik/klausur-WS0405.ps Klausur]

SS 2004
* [http://docs.freitagsrunde.org/klausuren/Softwaretechnik/klausur-SS04.ps Musterlösung]

WS 2003/2004
* [http://docs.freitagsrunde.org/Klausuren/Softwaretechnik/klausur-WS0304.ps Klausur]

SS 2003
* [http://docs.freitagsrunde.org/Klausuren/Softwaretechnik/klausur-SS03.ps Klausur]

WS 2002/2003
* [http://docs.freitagsrunde.org/Klausuren/Softwaretechnik/klausur-WS0203.ps Klausur]

SS 2002
* [http://docs.freitagsrunde.org/Klausuren/Softwaretechnik/ss2002.ps.gz Klausur]
* [http://docs.freitagsrunde.org/Klausuren/Softwaretechnik/ss02_musterloesung.ps.gz Musterlösung]

SS 2001
* [http://docs.freitagsrunde.org/Klausuren/Softwaretechnik/ss2001.ps.gz Klausur]
* [http://docs.freitagsrunde.org/Klausuren/Softwaretechnik/SWT-Basis_SS2001_Musterloesung.ps.gz Musterlösung]

WS 2000/2001
* [http://docs.freitagsrunde.org/Klausuren/Softwaretechnik/ws0001_musterloesung.ps.gz Musterlösung]

SS 2000
* [http://docs.freitagsrunde.org/Klausuren/Softwaretechnik/SWT-Basis_SS2001_Musterloesung.ps.gz Musterlösung]

WS 1999/2000
* [http://docs.freitagsrunde.org/Klausuren/Softwaretechnik/ws9900_musterloesung.ps.gz Musterlösung]

SS 1999
* [http://docs.freitagsrunde.org/Klausuren/Softwaretechnik/SWT-Basis_SS1999_Musterloesung.ps.gz Musterlösung]

WS 1998/1999
* [http://docs.freitagsrunde.org/Klausuren/Softwaretechnik/ws9899.ps.gz Musterlösung]

SS 1998
* [http://docs.freitagsrunde.org/Klausuren/Softwaretechnik/ss98_musterloesung.ps.gz Musterlösung]

WS 1997/1998
* [http://docs.freitagsrunde.org/Klausuren/Softwaretechnik/ws9798_musterloesung.ps.gz Musterlösung]

SS 1997
* [http://docs.freitagsrunde.org/Klausuren/Softwaretechnik/ss1997.ps.gz Musterlösung]

WS 1996/1997
* [http://docs.freitagsrunde.org/Klausuren/Softwaretechnik/ws9697_musterloesung.ps.gz Musterlösung]

SS 1996
* [http://docs.freitagsrunde.org/Klausuren/Softwaretechnik/ss96.ps.gz Musterlösung]

WS 1995/1996
* [http://docs.freitagsrunde.org/Klausuren/Softwaretechnik/ws9596_musterloesung.ps.gz Musterlösung]

</div>

'''Softwaretechnik''' ist eine [[Basisveranstaltung]] im Fachgebiet SWT (Studiengebiet SSG) im [[Hauptstudium|Informatik-Hauptstudium]].

== Inhalt ==
In der Lehrveranstaltung werden Methoden und Techniken zur Softwareentwicklung behandelt, die die Grundlage für weitere Vertiefung in das Studiengebiet Softwaretechnik und Systemgestaltung bilden. Schwerpunkte sind: Anforderungsermittlung, Software-Entwurf und -Konstruktion, Spezifikationstechniken, Qualitätssicherung und Software-Architektur.

== Tipps und nützliche Infos ==

Die Vorlesung gliedert sich in drei Teile: Fusion, Object-Z und Statecharts. In jedem Bereich gibt es eine Uebungsaufgabe, wobei die Fusion-Aufgabe 50% zaehlt (und äußerst umfangreich und schreibintensiv ist)

Literatur:
unwichtig, gibt diverse Unterlagen zu den einzelnen Bereichen

Zitat von der [[MPGI 3 (Bachelor)|MPGI3]]-Seite:

Für Diplomstudiengänge ([[Lehrveranstaltungen Informatik Diplom (StuPO90)|Informatik]], TI, TWM, Wi-Ing, ITM u.A.) auch als [[Basisveranstaltung]] [[Softwaretechnik]] anrechenbar.

== Weblinks ==
* [http://www.swt.cs.tu-berlin.de/lehre/swt/index.html/ Softwaretechnik (jeweils aktuelles Semester)]

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

* WS05/06: Im Informatik-Studium muß man viel Unsinn machen - aber dieser Kurs übertrifft nochmal alles. Die Krönung erwartet einen mitunter bei der Klausur. Hier muß man in sich windeseile in die Logik Anderer reindenken, um teilweise recht komplizierte Spezifikationen vornehmen zu können. Ich bin von diesem Kurs maßlos enttäuscht. Was mich am meisten stört, ist die unselige Zettelwirtschaft. Anstatt sich an einem Lehrbuch zu orientieren, hantiert man mit hunderten von Zettel rum. Unmöglich. Und eines ist klar: Wenn auf diese Weise in der Realität Software entwicklelt wird, dann verzichte ich freiwillig auf jede weitere Flugreise...TimoS.

* WS04/05 (Veranstalter: Stephan Herrmann): Man sollte es sich wirklich mehrfach ueberlegen, ob man diese Veranstaltung belegt. Positiv ist lediglich, dass es ein A-Kurs ist und dass bei der Klausur 35% zum Bestehen reichen. Alles andere ist sehr negativ. Die Tutoren wirken extrem unmotiviert und korrigieren ziemlich willkuerlich.

Die Vorlesung muss man nicht besuchen. Der Dozent labert ewig lange bei voellig unwichtigen Sachen rum und zieht dann die interessanten 10 Folien am Schluss in maximal 5 Minuten durch...

Totaler Mist. NICHT BELEGEN! FelixB

* Völlig sinnloser Spezifikationsmarathon. Nur belegen, wenn man Vertiefungsveranstaltungen bei SWT besuchen will/muss. Wenn schon, dann im SS besuchen, wenn Jähnichen die VL macht. --[[Benutzer:Felix|Felix]] 12:14, 12. Aug 2005 (CEST)

* Hmm - ich fand die Veranstaltung ehrlich gesagt nicht ganz so schlecht. Vielleicht sollte ich dazu sagen, dass ich seit 5 Jahren neben dem Studium in einer Firma arbeite, in der viel und professionell Software entwickelt wird. Natuerlich sind die Beispiele der Veranstaltung extrem an den Haaren herbeigezogen (wer spezifiziert schon eine Autowerkstatt komplett durch) - aber man kann dennoch viel lernen. Und sei es die Einsicht, dass man nicht alles spezifizieren kann und muss [Vor allem nicht mit den gelehrten Methoden...]. Jedenfalls ist das, was hier einige als sinnloses Geschwafel abtun, in der Praxis ziemlich wichtig. Es geht einfach nichts ohne eine (vernünftige) Spezifikation und Qualitätssicherung. Das muss man nicht toll finden, aber es is leider so, dass man ohne Pflichtenhefte und Projektmanagement verloren hat. Das es kein Lehrbuch gibt finde ich hervorragend, besser als wieder 30 Euro für ein Buch ausgeben zu müssen, von dem dann nur 20% benutzt werden. Ausserdem werden die Aufgaben immer wieder verändert und angepasst. Mein Tutor war Rodger, ich muss sagen das Tut war einfach nur Klasse! Die Vorlesung habe ich maximal dreimal besucht, Dozent war Kammüller. --[[Benutzer:Mutax|florian]] 14:02, 19. Feb. 2007 (CET)

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

__NOTOC__

Informatik 3/Gedächtnisprotokoll Klausur SS07

2007-08-02T10:16:29Z

TomyLobo: /* Aufgabe 1: Multiple Choice (7 Punkte) */

== Aufgabe 1: Multiple Choice (7 Punkte) ==

Kreuzen Sie jeweils wahr bzw. falsch an:
* ..
* Ein zusammenhängender, ungerichteter Graph mit |V| Knoten hat immer |V| * (|V| - 1) / 2 Kanten.
* 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.
 

Worst Case Aufwand von
* Wert in eine Hashliste mit Separate Chaining einfuegen
* Einen Wert in einer Skipliste finden
* Rotieren in einem AVL-Baum
* Tiefensuch
* Kruskal
* Edmonds Karp Alg

== Aufgabe 2: HashTables (7 Punkte) ==

Hashtabelle der Größe 4.
*Hashfunktion: h(k) = k mod 4
*Kollisonsauflösung"double hashing" a(k) = k+2

Vier Werte mit Schlüsseln einfügen und Kollisionen zählen.

(A,5) (B,11) (C,9) (D,14)

Lösung:
A -> 1
B -> 3
C -> 1,0
D -> 2

Ist die Anzahl der Kollisionen bei double hashing abhängig von der Reihenfolge in der die Elemente eingefügt werden? Begründung, ggf. Beispiel.

== Aufgabe 3: Suchbäume (11 Punkte) ==
'''AVL-Bäume'''
*Einfügen von 3 in den folgenden AVL-Baum:
[[Bild:Info3-ss2007-3-avltree.png]]

*Löschen von 10 aus dem folgenden AVL-Baum:
[[Bild:Info3-ss2007-3-avltree.png]]

'''Rot/Schwarz-Bäume'''
*Einfügen von '9' in den folgenden Rot/Schwarz-Baum:
[[Bild:Info3-ss2007-3-rbtree.png]]

*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; }
 

'''B-Baum'''
* Element in B-Baum einfügen.
[[Bild:Info3-ss2007-3-btree.png]]
 

== Aufgabe 4: Graphen (10 Punkte) ==
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 (4 Punkte) ==
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 (5 Punkte) ==

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


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

b) Kleinste worst-case-Laufzeitklasse angeben:

O( .... )

== Aufgabe 7: Geld wechseln (6 Punkte) ==
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).

== Siehe auch ==

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

Informatik 3/Gedächtnisprotokoll Klausur SS07

2007-08-02T09:49:29Z

TomyLobo: /* Aufgabe 1: Multiple Choice (7 Punkte) */

== Aufgabe 1: Multiple Choice (7 Punkte) ==

Kreuzen Sie jeweils wahr bzw. falsch an:
* ..
* Ein zusammenhängender, ungerichteter Graph mit |V| Knoten hat immer |V| * (|V| - 1) / 2 Kanten.
* 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.
 

Worst Case Aufwand von
* Hash einfuegen
* Einen Wert in einer Skipliste finden
* Rotieren in einem AVL-Baum
* Tiefensuch
* Kruskal
* Edmonds Karp Alg

== Aufgabe 2: HashTables (7 Punkte) ==

Hashtabelle der Größe 4.
*Hashfunktion: h(k) = k mod 4
*Kollisonsauflösung"double hashing" a(k) = k+2

Vier Werte mit Schlüsseln einfügen und Kollisionen zählen.

(A,5) (B,11) (C,9) (D,14)

Lösung:
A -> 1
B -> 3
C -> 1,0
D -> 2

Ist die Anzahl der Kollisionen bei double hashing abhängig von der Reihenfolge in der die Elemente eingefügt werden? Begründung, ggf. Beispiel.

== Aufgabe 3: Suchbäume (11 Punkte) ==
'''AVL-Bäume'''
*Einfügen von 3 in den folgenden AVL-Baum:
[[Bild:Info3-ss2007-3-avltree.png]]

*Löschen von 10 aus dem folgenden AVL-Baum:
[[Bild:Info3-ss2007-3-avltree.png]]

'''Rot/Schwarz-Bäume'''
*Einfügen von '9' in den folgenden Rot/Schwarz-Baum:
[[Bild:Info3-ss2007-3-rbtree.png]]

*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; }
 

'''B-Baum'''
* Element in B-Baum einfügen.
[[Bild:Info3-ss2007-3-btree.png]]
 

== Aufgabe 4: Graphen (10 Punkte) ==
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 (4 Punkte) ==
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 (5 Punkte) ==

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


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

b) Kleinste worst-case-Laufzeitklasse angeben:

O( .... )

== Aufgabe 7: Geld wechseln (6 Punkte) ==
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).

== Siehe auch ==

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

Informatik 3/Gedächtnisprotokoll Klausur SS07

2007-07-31T11:15:56Z

TomyLobo: /* Aufgabe 2: HashTables (7 Punkte) */

== Aufgabe 1: Multiple Choice (7 Punkte) ==

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.
 

Worst Case Aufwand von
* Hash einfuegen
* Einen Wert in einer Skipliste finden
* Rotieren in einem AVL-Baum
* Tiefensuch
* Kruskal
* Edmonds Karp Alg

== Aufgabe 2: HashTables (7 Punkte) ==

Hashtabelle der Größe 4.
*Hashfunktion: h(k) = k mod 4
*Kollisonsauflösung"double hashing" a(k) = k+2

Vier Werte mit Schlüsseln einfügen und Kollisionen zählen.

(A,5) (B,11) (C,9) (D,14)

Lösung:
A -> 1
B -> 3
C -> 1,0
D -> 2

Ist die Anzahl der Kollisionen bei double hashing abhängig von der Reihenfolge in der die Elemente eingefügt werden? Begründung, ggf. Beispiel.

== Aufgabe 3: Suchbäume (11 Punkte) ==
'''AVL-Bäume'''
*Einfügen von 3 in den folgenden AVL-Baum:
[[Bild:Info3-ss2007-3-avltree.png]]

*Löschen von 10 aus dem folgenden AVL-Baum:
[[Bild:Info3-ss2007-3-avltree.png]]

'''Rot/Schwarz-Bäume'''
*Einfügen von '9' in den folgenden Rot/Schwarz-Baum:
[[Bild:Info3-ss2007-3-rbtree.png]]

*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; }
 

'''B-Baum'''
* Element in B-Baum einfügen.
[[Bild:Info3-ss2007-3-btree.png]]
 

== Aufgabe 4: Graphen (10 Punkte) ==
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 (4 Punkte) ==
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 (5 Punkte) ==

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


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

b) Kleinste worst-case-Laufzeitklasse angeben:

O( .... )

== Aufgabe 7: Geld wechseln (6 Punkte) ==
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).

== Siehe auch ==

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

Datei:Info3-ss2007-3-rbtree.png

2007-07-30T17:46:39Z

TomyLobo:

Informatik 3/Gedächtnisprotokoll Klausur SS07

2007-07-30T17:46:30Z

TomyLobo: /* Aufgabe 3: Suchbäume (11 Punkte) */

== Aufgabe 1: Multiple Choice (7 Punkte) ==

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.
 

== Aufgabe 2: HashTables (7 Punkte) ==

Hashtabelle der Größe 4.
*Hashfunktion: h(k) = k mod 4
*Kollisonsauflösung"double hashing" a(k) = k+2

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) - Unsinn, bitte korrigieren [[Benutzer:TomyLobo|TomyLobo]]

D -> 2

0 blieb leer.

Andere Lösung:
A -> 1
B -> 3
C -> 1,0
D -> 2
 
Ist die Anzahl der Kollisionen bei double hashing abhängig von der Reihenfolge in der die Elemente eingefügt werden? Begründung, ggf. Beispiel.
 

== Aufgabe 3: Suchbäume (11 Punkte) ==
'''AVL-Bäume'''
*Einfügen von 3 in den folgenden AVL-Baum:
[[Bild:Info3-ss2007-3-avltree.png]]

*Löschen von 10 aus dem folgenden AVL-Baum:
[[Bild:Info3-ss2007-3-avltree.png]]

'''Rot/Schwarz-Bäume'''
*Einfügen von '9' in den folgenden Rot/Schwarz-Baum:
[[Bild:Info3-ss2007-3-rbtree.png]]

*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; }
 

'''B-Baum'''
* Element in B-Baum einfügen.
[[Bild:Info3-ss2007-3-btree.png]]
 

== Aufgabe 4: Graphen (10 Punkte) ==
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 (4 Punkte) ==
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 (5 Punkte) ==

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


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

b) Kleinste worst-case-Laufzeitklasse angeben:

O( .... )

== Aufgabe 7: Geld wechseln (6 Punkte) ==
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).

== Siehe auch ==

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

Datei:Info3-ss2007-3-avltree.png

2007-07-30T17:32:16Z

TomyLobo:

Diskussion:Informatik 3/Gedächtnisprotokoll Klausur SS07

2007-07-30T14:11:12Z

TomyLobo: /* Ergebnisse meiner Klausureinsicht */

== Ergebnisse meiner Klausureinsicht ==

der Abschnitt mit den Hash-Tabellen hat noch ne falsche Lösung drin, sollte derjenige rausnehmen, der es reingeschrieben hat.

*5 -> 1
*11 -> 3
*9 -> 1 -> (1+9+2)%4=12%4=0
*14 -> 2

weiterhin hab ich die Bäume in der Klausureinsicht nachgeschaut, werde ich einbauen sobald ich zuhause bin. Hier Vorab-Versionen:

AVL:

8
4 12
2 10 14
15

Einzufügen war die 3, zu löschen war die 10, jeweils ausgehend vom obenstehenden baum, NICHT aufeinander aufbauend!

5
1 7
8

Einzufügen war die 9.

[[Benutzer:TomyLobo|TomyLobo]]

Diskussion:Informatik 3/Gedächtnisprotokoll Klausur SS07

2007-07-30T14:05:10Z

TomyLobo: Ergebnisse meiner Klausureinsicht

== Ergebnisse meiner Klausureinsicht ==

der Abschnitt mit den Hash-Tabellen hat noch ne falsche Lösung drin, sollte derjenige rausnehmen, der es reingeschrieben hat.

*5 -> 1
*11 -> 3
*9 -> 1 -> (1+9+2)%4=12%4=0
*14 -> 2

weiterhin hab ich die Bäume in der Klausureinsicht nachgeschaut, werde ich einbauen sobald ich zuhause bin. Hier Vorab-Versionen:

AVL:

8
4 12
2 10 14
15

Einzufügen war die 3, zu löschen war die 10.

5
1 7
8

Einzufügen war die 9.

[[Benutzer:TomyLobo|TomyLobo]]

Informatik 3/Gedächtnisprotokoll Klausur SS07

2007-07-30T13:53:40Z

TomyLobo: /* Aufgabe 2: HashTables (7 Punkte) */

== Aufgabe 1: Multiple Choice (7 Punkte) ==

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.
 

== Aufgabe 2: HashTables (7 Punkte) ==

Hashtabelle der Größe 4.
*Hashfunktion: h(k) = k mod 4
*Kollisonsauflösung"double hashing" a(k) = k+2

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) - Unsinn, bitte korrigieren [[Benutzer:TomyLobo|TomyLobo]]

D -> 2

0 blieb leer.

Andere Lösung:
A -> 1
B -> 3
C -> 1,0
D -> 2
 
Ist die Anzahl der Kollisionen bei double hashing abhängig von der Reihenfolge in der die Elemente eingefügt werden? Begründung, ggf. Beispiel.
 

== Aufgabe 3: Suchbäume (11 Punkte) ==
'''AVL-Bäume'''
*Einfügen in AVL-Baum
*Einfügen in AVL-Baum
*Löschen aus AVL-Baum
 

'''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; }
 

'''B-Baum'''
* Element in B-Baum einfügen.
[[Bild:Info3-ss2007-3-btree.png]]
 

== Aufgabe 4: Graphen (10 Punkte) ==
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 (4 Punkte) ==
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 (5 Punkte) ==

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


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

b) Kleinste worst-case-Laufzeitklasse angeben:

O( .... )

== Aufgabe 7: Geld wechseln (6 Punkte) ==
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).

== Siehe auch ==

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

Informatik 3/Gedächtnisprotokoll Klausur SS07

2007-07-30T13:51:25Z

TomyLobo: Punkte bei Klausureinsicht mitgeloggt, die stimmen jetzt so :)

== Aufgabe 1: Multiple Choice (7 Punkte) ==

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.
 

== Aufgabe 2: HashTables (7 Punkte) ==

Hashtabelle der Größe 4.
*Hashfunktion: h(k) = k mod 4
*Kollisonsauflösung"double hashing" a(k) = k+2
 
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.
 
Andere Lösung:
A -> 1
B -> 3
C -> 1,0
D -> 2
 
Ist die Anzahl der Kollisionen bei double hashing abhängig von der Reihenfolge in der die Elemente eingefügt werden? Begründung, ggf. Beispiel.
 

== Aufgabe 3: Suchbäume (11 Punkte) ==
'''AVL-Bäume'''
*Einfügen in AVL-Baum
*Einfügen in AVL-Baum
*Löschen aus AVL-Baum
 

'''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; }
 

'''B-Baum'''
* Element in B-Baum einfügen.
[[Bild:Info3-ss2007-3-btree.png]]
 

== Aufgabe 4: Graphen (10 Punkte) ==
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 (4 Punkte) ==
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 (5 Punkte) ==

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


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

b) Kleinste worst-case-Laufzeitklasse angeben:

O( .... )

== Aufgabe 7: Geld wechseln (6 Punkte) ==
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).

== Siehe auch ==

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

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

2007-07-30T13:48:29Z

TomyLobo: /* Aufgabe 2: Assembler (13 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.

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

*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).

Gib den Stack nach dem Aufruf der Subroutine und der Sicherung der Register an (2 Punkte)

== 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..

sei n die Anzahl der Elefanten und m die Anzahl der Mäuse.

wenn n Elefanten auf dem Schiff sind, dann muss beachtet werden:

*wenn n > 2m ist, dann muss eine Maus an Bord kommen
*wenn n < 2m ist, dann muss ein Elefant an Bord kommen
*wenn n = 2m ist, dann muss man schauen:
*um das Gleichgewicht zu erhalten können an Bord kommen:
:Elefant, Maus, Maus oder Maus, Elefant, Maus, damit keine Verletzung der ersten 2 Punkte zustandekommt.

die Aufgabe hat echt reingehauen

== Aufgabe 4: Monitore (13 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.

== Aufgabe 5: Betriebsmittelvergabe (5 Punkte) ==

Die Betriebsmittel werden in der Aufgabe nach preämptiver Planung nach Laufzeit
vergeben, gegeben sind folgende Prozesse:

[[Bild:Info4-ss2007-5.png]]

Geben Sie für die jewelige Zeit die Vergabereihenfolge für die Prozesse an:

<nowiki>
-----------------------------------
1 2 3 4 5 6 7 8 9 10
</nowiki>
Geben Sie zusätzlich die zeitlichen Verläufe der Inhalte der Warte-Queues an
und berechnen Sie die mittlere Wartezeit.

== Siehe auch ==

[[Informatik 3/Gedächtnisprotokoll Klausur SS07]]

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

2007-07-30T13:47:38Z

TomyLobo: /* 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.

== Aufgabe 2: Assembler (13 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).

== 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..

sei n die Anzahl der Elefanten und m die Anzahl der Mäuse.

wenn n Elefanten auf dem Schiff sind, dann muss beachtet werden:

*wenn n > 2m ist, dann muss eine Maus an Bord kommen
*wenn n < 2m ist, dann muss ein Elefant an Bord kommen
*wenn n = 2m ist, dann muss man schauen:
*um das Gleichgewicht zu erhalten können an Bord kommen:
:Elefant, Maus, Maus oder Maus, Elefant, Maus, damit keine Verletzung der ersten 2 Punkte zustandekommt.

die Aufgabe hat echt reingehauen

== Aufgabe 4: Monitore (13 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.

== Aufgabe 5: Betriebsmittelvergabe (5 Punkte) ==

Die Betriebsmittel werden in der Aufgabe nach preämptiver Planung nach Laufzeit
vergeben, gegeben sind folgende Prozesse:

[[Bild:Info4-ss2007-5.png]]

Geben Sie für die jewelige Zeit die Vergabereihenfolge für die Prozesse an:

<nowiki>
-----------------------------------
1 2 3 4 5 6 7 8 9 10
</nowiki>
Geben Sie zusätzlich die zeitlichen Verläufe der Inhalte der Warte-Queues an
und berechnen Sie die mittlere Wartezeit.

== Siehe auch ==

[[Informatik 3/Gedächtnisprotokoll Klausur SS07]]

Informatik 3/Gedächtnisprotokoll Klausur SS07

2007-07-29T15:00:29Z

TomyLobo: /* Aufgabe 7: Geld wechseln (>=3 (6?) Punkte) */

== Aufgabe 1: Multiple Choice (10(?) Punkte) ==

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.
 

== Aufgabe 2: HashTables (>=5 Punkte) ==

Hashtabelle der Größe 4.
*Hashfunktion: h(k) = k mod 4
*Kollisonsauflösung"double hashing" a(k) = k+2
 
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.
 
Andere Lösung:
A -> 1
B -> 3
C -> 1,0
D -> 2
 
Ist die Anzahl der Kollisionen bei double hashing abhängig von der Reihenfolge in der die Elemente eingefügt werden? Begründung, ggf. Beispiel.
 

== Aufgabe 3: Suchbäume (>=10 Punkte) ==
'''AVL-Bäume'''
*Einfügen in AVL-Baum
*Einfügen in AVL-Baum
*Löschen aus AVL-Baum
 

'''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; }
 

'''B-Baum'''
* Element in B-Baum einfügen.
[[Bild:Info3-ss2007-3-btree.png]]
 

== Aufgabe 4: Graphen (>=9 Punkte) ==
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 (>=8 Punkte) ==
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 (>=5 (6?) Punkte) ==

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


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

b) Kleinste worst-case-Laufzeitklasse angeben:

O( .... )

== Aufgabe 7: Geld wechseln (>=6 Punkte) ==
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).

== Siehe auch ==

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

Informatik 3/Gedächtnisprotokoll Klausur SS07

2007-07-29T15:00:26Z

TomyLobo: /* Aufgabe 5: Übungsorganisation (>=3 Punkte) */

== Aufgabe 1: Multiple Choice (10(?) Punkte) ==

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.
 

== Aufgabe 2: HashTables (>=5 Punkte) ==

Hashtabelle der Größe 4.
*Hashfunktion: h(k) = k mod 4
*Kollisonsauflösung"double hashing" a(k) = k+2
 
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.
 
Andere Lösung:
A -> 1
B -> 3
C -> 1,0
D -> 2
 
Ist die Anzahl der Kollisionen bei double hashing abhängig von der Reihenfolge in der die Elemente eingefügt werden? Begründung, ggf. Beispiel.
 

== Aufgabe 3: Suchbäume (>=10 Punkte) ==
'''AVL-Bäume'''
*Einfügen in AVL-Baum
*Einfügen in AVL-Baum
*Löschen aus AVL-Baum
 

'''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; }
 

'''B-Baum'''
* Element in B-Baum einfügen.
[[Bild:Info3-ss2007-3-btree.png]]
 

== Aufgabe 4: Graphen (>=9 Punkte) ==
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 (>=8 Punkte) ==
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 (>=5 (6?) Punkte) ==

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


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

b) Kleinste worst-case-Laufzeitklasse angeben:

O( .... )

== Aufgabe 7: Geld wechseln (>=3 (6?) Punkte) ==
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).

== Siehe auch ==

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

Informatik 3/Gedächtnisprotokoll Klausur SS07

2007-07-29T14:59:54Z

TomyLobo: /* Aufgabe 3: Suchbäume (>=8 Punkte) */

== Aufgabe 1: Multiple Choice (10(?) Punkte) ==

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.
 

== Aufgabe 2: HashTables (>=5 Punkte) ==

Hashtabelle der Größe 4.
*Hashfunktion: h(k) = k mod 4
*Kollisonsauflösung"double hashing" a(k) = k+2
 
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.
 
Andere Lösung:
A -> 1
B -> 3
C -> 1,0
D -> 2
 
Ist die Anzahl der Kollisionen bei double hashing abhängig von der Reihenfolge in der die Elemente eingefügt werden? Begründung, ggf. Beispiel.
 

== Aufgabe 3: Suchbäume (>=10 Punkte) ==
'''AVL-Bäume'''
*Einfügen in AVL-Baum
*Einfügen in AVL-Baum
*Löschen aus AVL-Baum
 

'''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; }
 

'''B-Baum'''
* Element in B-Baum einfügen.
[[Bild:Info3-ss2007-3-btree.png]]
 

== Aufgabe 4: Graphen (>=9 Punkte) ==
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 (>=3 Punkte) ==
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 (>=5 (6?) Punkte) ==

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


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

b) Kleinste worst-case-Laufzeitklasse angeben:

O( .... )

== Aufgabe 7: Geld wechseln (>=3 (6?) Punkte) ==
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).

== Siehe auch ==

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

Informatik 3/Gedächtnisprotokoll Klausur SS07

2007-07-29T14:59:48Z

TomyLobo: /* Aufgabe 2: HashTables (>=4 Punkte) */

== Aufgabe 1: Multiple Choice (10(?) Punkte) ==

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.
 

== Aufgabe 2: HashTables (>=5 Punkte) ==

Hashtabelle der Größe 4.
*Hashfunktion: h(k) = k mod 4
*Kollisonsauflösung"double hashing" a(k) = k+2
 
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.
 
Andere Lösung:
A -> 1
B -> 3
C -> 1,0
D -> 2
 
Ist die Anzahl der Kollisionen bei double hashing abhängig von der Reihenfolge in der die Elemente eingefügt werden? Begründung, ggf. Beispiel.
 

== Aufgabe 3: Suchbäume (>=8 Punkte) ==
'''AVL-Bäume'''
*Einfügen in AVL-Baum
*Einfügen in AVL-Baum
*Löschen aus AVL-Baum
 

'''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; }
 

'''B-Baum'''
* Element in B-Baum einfügen.
[[Bild:Info3-ss2007-3-btree.png]]
 

== Aufgabe 4: Graphen (>=9 Punkte) ==
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 (>=3 Punkte) ==
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 (>=5 (6?) Punkte) ==

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


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

b) Kleinste worst-case-Laufzeitklasse angeben:

O( .... )

== Aufgabe 7: Geld wechseln (>=3 (6?) Punkte) ==
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).

== Siehe auch ==

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

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

2007-07-28T16:57:24Z

TomyLobo: das mit den 50 punkten entfernt, wiki-syntax angewendet und Verweis auf den Informatik-3-Teil eingebaut

== 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.

== Aufgabe 2: Assembler (13 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).

== 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..

sei n die Anzahl der Elefanten und m die Anzahl der Mäuse.

wenn n Elefanten auf dem Schiff sind, dann muss beachtet werden:

*wenn n > 2m ist, dann muss eine Maus an Bord kommen
*wenn n < 2m ist, dann muss ein Elefant an Bord kommen
*wenn n = 2m ist, dann muss man schauen:
*um das Gleichgewicht zu erhalten können an Bord kommen:
:Elefant, Maus, Maus oder Maus, Elefant, Maus, damit keine Verletzung der ersten 2 Punkte zustandekommt.

die Aufgabe hat echt reingehauen

== 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.

== Aufgabe 5: Betriebsmittelvergabe (5 Punkte) ==

Die Betriebsmittel werden in der Aufgabe nach preämptiver Planung nach Laufzeit
vergeben, gegeben sind folgende Prozesse:

[[Bild:Info4-ss2007-5.png]]

Geben Sie für die jewelige Zeit die Vergabereihenfolge für die Prozesse an:

<nowiki>
-----------------------------------
1 2 3 4 5 6 7 8 9 10
</nowiki>
Geben Sie zusätzlich die zeitlichen Verläufe der Inhalte der Warte-Queues an
und berechnen Sie die mittlere Wartezeit.

== Siehe auch ==

[[Informatik 3/Gedächtnisprotokoll Klausur SS07]]

FreitagsrundenWiki:Bearbeitungshilfe

2007-07-28T16:55:33Z

TomyLobo:

[http://de.wikipedia.org/wiki/Hilfe:Bearbeitungshilfe Bearbeitungshilfe der deutschen Wikipedia]

[http://meta.wikimedia.org/wiki/Help:Contents#For_editors englische Bearbeitungshilfe bei metawiki]

Informatik 3/Gedächtnisprotokoll Klausur SS07

2007-07-28T16:45:16Z

TomyLobo: /* Aufgabe 7: Geld wechseln (>=6(?) Punkte) */

== Aufgabe 1: Multiple Choice (10(?) Punkte) ==

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.
 

== Aufgabe 2: HashTables (>=4 Punkte) ==

Hashtabelle der Größe 4.
*Hashfunktion: h(k) = k mod 4
*Kollisonsauflösung"double hashing" a(k) = k+2
 
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.
 
Andere Lösung:
A -> 1
B -> 3
C -> 1,0
D -> 2
 
Ist die Anzahl der Kollisionen bei double hashing abhängig von der Reihenfolge in der die Elemente eingefügt werden? Begründung, ggf. Beispiel.
 

== Aufgabe 3: Suchbäume (>=8 Punkte) ==
'''AVL-Bäume'''
*Einfügen in AVL-Baum
*Einfügen in AVL-Baum
*Löschen aus AVL-Baum
 

'''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; }
 

'''B-Baum'''
* Element in B-Baum einfügen.
[[Bild:Info3-ss2007-3-btree.png]]
 

== Aufgabe 4: Graphen (>=9 Punkte) ==
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 (>=3 Punkte) ==
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 (>=5 (6?) Punkte) ==

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


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

b) Kleinste worst-case-Laufzeitklasse angeben:

O( .... )

== Aufgabe 7: Geld wechseln (>=3 (6?) Punkte) ==
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).

== Siehe auch ==

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

Informatik 3/Gedächtnisprotokoll Klausur SS07

2007-07-28T16:45:02Z

TomyLobo: /* Aufgabe 6: Dynamisches Programmieren (>=6(?) Punkte) */

== Aufgabe 1: Multiple Choice (10(?) Punkte) ==

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.
 

== Aufgabe 2: HashTables (>=4 Punkte) ==

Hashtabelle der Größe 4.
*Hashfunktion: h(k) = k mod 4
*Kollisonsauflösung"double hashing" a(k) = k+2
 
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.
 
Andere Lösung:
A -> 1
B -> 3
C -> 1,0
D -> 2
 
Ist die Anzahl der Kollisionen bei double hashing abhängig von der Reihenfolge in der die Elemente eingefügt werden? Begründung, ggf. Beispiel.
 

== Aufgabe 3: Suchbäume (>=8 Punkte) ==
'''AVL-Bäume'''
*Einfügen in AVL-Baum
*Einfügen in AVL-Baum
*Löschen aus AVL-Baum
 

'''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; }
 

'''B-Baum'''
* Element in B-Baum einfügen.
[[Bild:Info3-ss2007-3-btree.png]]
 

== Aufgabe 4: Graphen (>=9 Punkte) ==
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 (>=3 Punkte) ==
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 (>=5 (6?) Punkte) ==

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


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

b) Kleinste worst-case-Laufzeitklasse angeben:

O( .... )

== Aufgabe 7: Geld wechseln (>=6(?) Punkte) ==
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).

== Siehe auch ==

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

Informatik 3/Gedächtnisprotokoll Klausur SS07

2007-07-28T16:44:46Z

TomyLobo: /* Aufgabe 6: Dynamisches Programmieren (>=6 Punkte) */

== Aufgabe 1: Multiple Choice (10(?) Punkte) ==

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.
 

== Aufgabe 2: HashTables (>=4 Punkte) ==

Hashtabelle der Größe 4.
*Hashfunktion: h(k) = k mod 4
*Kollisonsauflösung"double hashing" a(k) = k+2
 
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.
 
Andere Lösung:
A -> 1
B -> 3
C -> 1,0
D -> 2
 
Ist die Anzahl der Kollisionen bei double hashing abhängig von der Reihenfolge in der die Elemente eingefügt werden? Begründung, ggf. Beispiel.
 

== Aufgabe 3: Suchbäume (>=8 Punkte) ==
'''AVL-Bäume'''
*Einfügen in AVL-Baum
*Einfügen in AVL-Baum
*Löschen aus AVL-Baum
 

'''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; }
 

'''B-Baum'''
* Element in B-Baum einfügen.
[[Bild:Info3-ss2007-3-btree.png]]
 

== Aufgabe 4: Graphen (>=9 Punkte) ==
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 (>=3 Punkte) ==
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 (>=6(?) Punkte) ==

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


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

b) Kleinste worst-case-Laufzeitklasse angeben:

O( .... )

== Aufgabe 7: Geld wechseln (>=6(?) Punkte) ==
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).

== Siehe auch ==

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

Informatik 3/Gedächtnisprotokoll Klausur SS07

2007-07-28T16:44:35Z

TomyLobo: /* Aufgabe 7: Geld wechseln (>=3 Punkte) */

== Aufgabe 1: Multiple Choice (10(?) Punkte) ==

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.
 

== Aufgabe 2: HashTables (>=4 Punkte) ==

Hashtabelle der Größe 4.
*Hashfunktion: h(k) = k mod 4
*Kollisonsauflösung"double hashing" a(k) = k+2
 
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.
 
Andere Lösung:
A -> 1
B -> 3
C -> 1,0
D -> 2
 
Ist die Anzahl der Kollisionen bei double hashing abhängig von der Reihenfolge in der die Elemente eingefügt werden? Begründung, ggf. Beispiel.
 

== Aufgabe 3: Suchbäume (>=8 Punkte) ==
'''AVL-Bäume'''
*Einfügen in AVL-Baum
*Einfügen in AVL-Baum
*Löschen aus AVL-Baum
 

'''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; }
 

'''B-Baum'''
* Element in B-Baum einfügen.
[[Bild:Info3-ss2007-3-btree.png]]
 

== Aufgabe 4: Graphen (>=9 Punkte) ==
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 (>=3 Punkte) ==
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 (>=6 Punkte) ==

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


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

b) Kleinste worst-case-Laufzeitklasse angeben:

O( .... )

== Aufgabe 7: Geld wechseln (>=6(?) Punkte) ==
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).

== Siehe auch ==

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

Informatik 3/Gedächtnisprotokoll Klausur SS07

2007-07-28T16:44:22Z

TomyLobo: /* Aufgabe 6: Dynamisches Programmieren (>=5 Punkte) */

== Aufgabe 1: Multiple Choice (10(?) Punkte) ==

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.
 

== Aufgabe 2: HashTables (>=4 Punkte) ==

Hashtabelle der Größe 4.
*Hashfunktion: h(k) = k mod 4
*Kollisonsauflösung"double hashing" a(k) = k+2
 
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.
 
Andere Lösung:
A -> 1
B -> 3
C -> 1,0
D -> 2
 
Ist die Anzahl der Kollisionen bei double hashing abhängig von der Reihenfolge in der die Elemente eingefügt werden? Begründung, ggf. Beispiel.
 

== Aufgabe 3: Suchbäume (>=8 Punkte) ==
'''AVL-Bäume'''
*Einfügen in AVL-Baum
*Einfügen in AVL-Baum
*Löschen aus AVL-Baum
 

'''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; }
 

'''B-Baum'''
* Element in B-Baum einfügen.
[[Bild:Info3-ss2007-3-btree.png]]
 

== Aufgabe 4: Graphen (>=9 Punkte) ==
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 (>=3 Punkte) ==
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 (>=6 Punkte) ==

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


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

b) Kleinste worst-case-Laufzeitklasse angeben:

O( .... )

== Aufgabe 7: Geld wechseln (>=3 Punkte) ==
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).

== Siehe auch ==

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

Informatik 3/Gedächtnisprotokoll Klausur SS07

2007-07-28T16:43:11Z

TomyLobo: /* Siehe auch */

== Aufgabe 1: Multiple Choice (10(?) Punkte) ==

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.
 

== Aufgabe 2: HashTables (>=4 Punkte) ==

Hashtabelle der Größe 4.
*Hashfunktion: h(k) = k mod 4
*Kollisonsauflösung"double hashing" a(k) = k+2
 
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.
 
Andere Lösung:
A -> 1
B -> 3
C -> 1,0
D -> 2
 
Ist die Anzahl der Kollisionen bei double hashing abhängig von der Reihenfolge in der die Elemente eingefügt werden? Begründung, ggf. Beispiel.
 

== Aufgabe 3: Suchbäume (>=8 Punkte) ==
'''AVL-Bäume'''
*Einfügen in AVL-Baum
*Einfügen in AVL-Baum
*Löschen aus AVL-Baum
 

'''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; }
 

'''B-Baum'''
* Element in B-Baum einfügen.
[[Bild:Info3-ss2007-3-btree.png]]
 

== Aufgabe 4: Graphen (>=9 Punkte) ==
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 (>=3 Punkte) ==
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 (>=5 Punkte) ==

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


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

b) Kleinste worst-case-Laufzeitklasse angeben:

O( .... )

== Aufgabe 7: Geld wechseln (>=3 Punkte) ==
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).

== Siehe auch ==

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

Informatik 3/Gedächtnisprotokoll Klausur SS07

2007-07-28T16:40:11Z

TomyLobo:

== Aufgabe 1: Multiple Choice (10(?) Punkte) ==

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.
 

== Aufgabe 2: HashTables (>=4 Punkte) ==

Hashtabelle der Größe 4.
*Hashfunktion: h(k) = k mod 4
*Kollisonsauflösung"double hashing" a(k) = k+2
 
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.
 
Andere Lösung:
A -> 1
B -> 3
C -> 1,0
D -> 2
 
Ist die Anzahl der Kollisionen bei double hashing abhängig von der Reihenfolge in der die Elemente eingefügt werden? Begründung, ggf. Beispiel.
 

== Aufgabe 3: Suchbäume (>=8 Punkte) ==
'''AVL-Bäume'''
*Einfügen in AVL-Baum
*Einfügen in AVL-Baum
*Löschen aus AVL-Baum
 

'''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; }
 

'''B-Baum'''
* Element in B-Baum einfügen.
[[Bild:Info3-ss2007-3-btree.png]]
 

== Aufgabe 4: Graphen (>=9 Punkte) ==
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 (>=3 Punkte) ==
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 (>=5 Punkte) ==

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


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

b) Kleinste worst-case-Laufzeitklasse angeben:

O( .... )

== Aufgabe 7: Geld wechseln (>=3 Punkte) ==
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).

== Siehe auch ==

Informatik 3/Gedächtnisprotokoll Klausur SS07

2007-07-28T16:39:45Z

TomyLobo: /* Aufgabe 1: Multiple Choice (>=5 Punkte) */

== Aufgabe 1: Multiple Choice (10(?) Punkte) ==

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.
 

== Aufgabe 2: HashTables (>=4 Punkte) ==

Hashtabelle der Größe 4.
*Hashfunktion: h(k) = k mod 4
*Kollisonsauflösung"double hashing" a(k) = k+2
 
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.
 
Andere Lösung:
A -> 1
B -> 3
C -> 1,0
D -> 2
 
Ist die Anzahl der Kollisionen bei double hashing abhängig von der Reihenfolge in der die Elemente eingefügt werden? Begründung, ggf. Beispiel.
 

== Aufgabe 3: Suchbäume (>=8 Punkte) ==
'''AVL-Bäume'''
*Einfügen in AVL-Baum
*Einfügen in AVL-Baum
*Löschen aus AVL-Baum
 

'''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; }
 

'''B-Baum'''
* Element in B-Baum einfügen.
[[Bild:Info3-ss2007-3-btree.png]]
 

== Aufgabe 4: Graphen (>=9 Punkte) ==
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 (>=3 Punkte) ==
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 (>=5 Punkte) ==

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


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

b) Kleinste worst-case-Laufzeitklasse angeben:

O( .... )

== Aufgabe 7: Geld wechseln (>=3 Punkte) ==
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-28T16:36:12Z

TomyLobo:

== Aufgabe 1: Multiple Choice (>=5 Punkte) ==

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.
 

== Aufgabe 2: HashTables (>=4 Punkte) ==

Hashtabelle der Größe 4.
*Hashfunktion: h(k) = k mod 4
*Kollisonsauflösung"double hashing" a(k) = k+2
 
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.
 
Andere Lösung:
A -> 1
B -> 3
C -> 1,0
D -> 2
 
Ist die Anzahl der Kollisionen bei double hashing abhängig von der Reihenfolge in der die Elemente eingefügt werden? Begründung, ggf. Beispiel.
 

== Aufgabe 3: Suchbäume (>=8 Punkte) ==
'''AVL-Bäume'''
*Einfügen in AVL-Baum
*Einfügen in AVL-Baum
*Löschen aus AVL-Baum
 

'''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; }
 

'''B-Baum'''
* Element in B-Baum einfügen.
[[Bild:Info3-ss2007-3-btree.png]]
 

== Aufgabe 4: Graphen (>=9 Punkte) ==
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 (>=3 Punkte) ==
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 (>=5 Punkte) ==

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


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

b) Kleinste worst-case-Laufzeitklasse angeben:

O( .... )

== Aufgabe 7: Geld wechseln (>=3 Punkte) ==
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 4 (StuPO90)/Gedächtnisprotokoll Klausur SoSe 2007

2007-07-27T12:52:51Z

TomyLobo: /* Aufgabe 5: Betriebsmittelvergabe (5 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.

 

== 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).
 

== 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..
 

== 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.

== Aufgabe 5: Betriebsmittelvergabe (5 Punkte) ==

Die Betriebsmittel werden in der Aufgabe nach preämptiver Planung nach Laufzeit
vergeben, gegeben sind folgende Prozesse:

[[Bild:Info4-ss2007-5.png]]

Geben Sie für die jewelige Zeit die Vergabereihenfolge für die Prozesse an:

<nowiki>
-----------------------------------
1 2 3 4 5 6 7 8 9 10
</nowiki>
Geben Sie zusätzlich die zeitlichen Verläufe der Inhalte der Warte-Queues an
und berechnen Sie die mittlere Wartezeit.

 
Irgendwie komme ich nicht auf 50 Punkte :>

Datei:Info4-ss2007-5.png

2007-07-27T12:52:10Z

TomyLobo:

Informatik 3/Gedächtnisprotokoll Klausur SS07

2007-07-26T20:32:18Z

TomyLobo: /* Aufgabe 3: Suchbäume */

== 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.
 

== Aufgabe 2: HashTables ==

Hashtabelle der Größe 4.
*Hashfunktion: h(k) = k mod 4
*Kollisonsauflösung"double hashing" a(k) = k+2
 
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.
 
Ist die Anzahl der Kollisionen bei double hashing abhängig von der Reihenfolge in der die Elemente eingefügt werden? Begründung, ggf. Beispiel.
 

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

'''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; }
 

'''B-Baum'''
* Element in B-Baum einfügen.
[[Bild:Info3-ss2007-3-btree.png]]
 

== 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).

Datei:Info3-ss2007-3-btree.png

2007-07-26T20:31:34Z

TomyLobo:

Datei:Info3-ss2007-6.png

2007-07-26T20:05:49Z

TomyLobo:

Das Bild wurde gerendert mit freundlicher, allerdings unwissender, Unterstützung der deutschen Wikipedia.

Hier der TeX-Quellcode des obenstehenden Bildes:

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

Datei:Info3-ss2007-6.png

2007-07-26T18:49:44Z

TomyLobo:

Das Bild wurde gerendert mit freundlicher, allerdings unwissender, Unterstützung der deutschen Wikipedia.
Hier der TeX-Quellcode des obenstehenden Bildes:
<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>

Informatik 3/Gedächtnisprotokoll Klausur SS07

2007-07-26T18:46:21Z

TomyLobo: /* Aufgabe 6: Dynamisches Programmieren */

== 1. Aufgabe: 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.
 

== HashTables ==

Hashtabelle der Größe 4.
*Hashfunktion: h(k) = k mod 4
*Kollisonsauflösung"double hashing" a(k) = k+2
 
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.
 
Ist die Anzahl der Kollisionen bei double hashing abhängig von der Reihenfolge in der die Elemente eingefügt werden? Begründung, ggf. Beispiel.
 

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

== 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; }
 

== 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 ==

[[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).

Datei:Info3-ss2007-6.png

2007-07-26T18:44:57Z

TomyLobo:

Informatik 3/Gedächtnisprotokoll Klausur SS07

2007-07-26T18:39:24Z

TomyLobo: /* Rot/Schwarz-Bäume */

== 1. Aufgabe: 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.
 

== HashTables ==

Hashtabelle der Größe 4.
*Hashfunktion: h(k) = k mod 4
*Kollisonsauflösung"double hashing" a(k) = k+2
 
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.
 
Ist die Anzahl der Kollisionen bei double hashing abhängig von der Reihenfolge in der die Elemente eingefügt werden? Begründung, ggf. Beispiel.
 

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

== 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; }
 

== 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).

Referat Prüfungen

2007-07-26T16:59:02Z

TomyLobo:

Das '''Referat Prüfungen''' (I B), häufig auch Prüfungsamt genannt, ist ein wichtiger Anlaufpunkt in Eurem [[Studium]]. Hier muss man sich für einige [[Prüfungen]] anmelden, erhält sein (Vor-) [[Diplom]] u.ä.
Es befindet sich im [[Hauptgebäude]], im Raum H23 (Referat I B b 1, Tel.: 314-22559).

'''Achtung:''' Vom 25. September 2006 bis (voraussichtlich) Ende März 2007 sind die Mitarbeiter umgezogen ins Elektrotechnik-Gebäude am Einsteinufer, Raum 109 – 111, 1. Stock. Erreichbar über den nördlichen, aber nicht den südlichen Übergang vom Elektrotechnik-Neubau.

=== Links ===
* [http://www.tu-berlin.de/zuv/IB/ Internetseiten des Prüfungsamts]

[[Kategorie: Wichtige Orte]]
[[Kategorie: Uni-ABC]]
[[Kategorie: Fakultäts-ABC]]

Informatik 3/Gedächtnisprotokoll Klausur SS07

2007-07-26T15:53:36Z

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

== 1. Aufgabe: 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.
 

== HashTables ==

Hashtabelle der Größe 4.
*Hashfunktion: h(k) = k mod 4
*Kollisonsauflösung"double hashing" a(k) = k+2
 
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.
 
Ist die Anzahl der Kollisionen bei double hashing abhängig von der Reihenfolge in der die Elemente eingefügt werden? Begründung, ggf. Beispiel.
 

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

== Rot/Schwarz-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; }
 

== 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).

Informatik 3/Gedächtnisprotokoll Klausur SS07

2007-07-26T15:53:13Z

TomyLobo: /* Rot-Schwaz-Bäume */

== 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.
 

== HashTables ==

Hashtabelle der Größe 4.
*Hashfunktion: h(k) = k mod 4
*Kollisonsauflösung"double hashing" a(k) = k+2
 
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.
 
Ist die Anzahl der Kollisionen bei double hashing abhängig von der Reihenfolge in der die Elemente eingefügt werden? Begründung, ggf. Beispiel.
 

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

== Rot/Schwarz-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; }
 

== 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).

Informatik 3/Gedächtnisprotokoll Klausur SS07

2007-07-26T15:51:55Z

TomyLobo: /* Aufgabe 7: Geld wechseln */

== 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.
 

== HashTables ==

Hashtabelle der Größe 4.
*Hashfunktion: h(k) = k mod 4
*Kollisonsauflösung"double hashing" a(k) = k+2
 
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.
 
Ist die Anzahl der Kollisionen bei double hashing abhängig von der Reihenfolge in der die Elemente eingefügt werden? Begründung, ggf. Beispiel.
 

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

== 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; }
 

== 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).

Informatik 3/Gedächtnisprotokoll Klausur SS07

2007-07-26T15:47:55Z

TomyLobo: /* Aufgabe 6: Dynamisches Programmieren */

== 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.
 

== HashTables ==

Hashtabelle der Größe 4.
*Hashfunktion: h(k) = k mod 4
*Kollisonsauflösung"double hashing" a(k) = k+2
 
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.
 
Ist die Anzahl der Kollisionen bei double hashing abhängig von der Reihenfolge in der die Elemente eingefügt werden? Begründung, ggf. Beispiel.
 

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

== 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; }
 

== 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 ==
Hab ich, trag ich gleich ein [[Benutzer:TomyLobo|TomyLobo]]

Informatik 3/Gedächtnisprotokoll Klausur SS07

2007-07-26T15:32:13Z

TomyLobo: /* Aufgabe 5: Übungsorganisation */

== 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.
 

== HashTables ==

Hashtabelle der Größe 4.
*Hashfunktion: h(k) = k mod 4
*Kollisonsauflösung"double hashing" a(k) = k+2
 
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.
 
Ist die Anzahl der Kollisionen bei double hashing abhängig von der Reihenfolge in der die Elemente eingefügt werden? Begründung, ggf. Beispiel.
 

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

== 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; }
 

== 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 ==
Hab ich, trag ich gleich ein [[Benutzer:TomyLobo|TomyLobo]]

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

FreitagsrundenWiki:Bearbeitungshilfe

2007-07-26T15:26:04Z

TomyLobo:

[http://de.wikipedia.org/wiki/Hilfe:Bearbeitungshilfe Bearbeitungshilfe der deutschen Wikipedia]

FreitagsrundenWiki:Bearbeitungshilfe

2007-07-26T15:25:19Z

TomyLobo:

[[http://de.wikipedia.org/wiki/Hilfe:Bearbeitungshilfe]]

Datei:Info3-ss2007-4e.png

2007-07-26T15:21:34Z

TomyLobo:

Informatik 3/Gedächtnisprotokoll Klausur SS07

2007-07-26T15:15:34Z

TomyLobo: /* Aufgabe 4: Graphen */

Informatik 3/Gedächtnisprotokoll Klausur SS07

2007-07-26T15:14:38Z

TomyLobo: /* Aufgabe 4: Graphen */