https://wiki.mafiasi.de/api.php?action=feedcontributions&feedformat=atom&user=80.171.22.53 2026-10-17T09:23:20Z Benutzerbeiträge MediaWiki 1.46.2 https://wiki.mafiasi.de/index.php?title=Ged%C3%A4chtnisprotokoll_AD08-1&diff=5028 2008-02-18T19:00:57Z

<p>80.171.22.53: /* Bäume */</p> <hr /> <div>Die Klausur war zeitlich kaum zu schaffen. Die schwierigkeit der einzelnen Aufgaben wurde unterschiedlich zwischen angemessen und zu hoch bis viel zu hoch bewertet.<br /> <br /> Man konnte eine handbeschriebene Din-A4-Seite mit beliebigem Inhalt mitbringen.<br /> <br /> <br /> == Multiple-Choice Teil ==<br /> <br /> * Hashing<br /> * P/NP<br /> <br /> == asymptotische Laufzeiten ==<br /> Berechnen Sie mit dem Master-Theorem: (3 Rekurenzgleichungen folgen)<br /> <br /> Finden Sie die geschlossene Form für folgende Rekurenzgleichung: T(sqrt(N))+1 (oder so ähnlich)&lt;br&gt;<br /> Sie können annehmen dass n \in 2^{2^i} mit i \in \mathbb{N} ist.<br /> <br /> Stellen sie die Rekurenzgleichung für folgenden Algorithmus auf und geben Sie seine asymptotische Laufzeit an. (ein Algorithmus folgt)<br /> <br /> Zeigen Sie anhand der Definition des O-Kalküls: f(n) = O(g(n)). (Natürlich für konkrete f und g).<br /> <br /> == Suchen ==<br /> Gegeben: Ein Array von Zahlen, Mehrere andere Arrays mit denselben Zahlen, eine Liste mit dem bekannten Sortieralgorithmen Insertion-, Selection-, Bubble- und Quicksort.<br /> <br /> Zuordnen: Welcher Algorithmus hat welches Array als Zwischenergebnis produziert?<br /> <br /> Quicksort<br /> <br /> Annahme:Jedes Element steht maximal k Plätze von seinem richtigen entfernt<br /> * Zeigen Sie, dass eine Vertauschung von &lt;nowiki&gt;A[j] und A[j+1] mit A[j] &gt; A[j+1]&lt;/nowiki&gt; diese Eigenschaft nicht zerstört.<br /> * Passen Sie Bubble-Sort an die Zusatzbedingung an. (Bubble-Sort gegeben)<br /> <br /> == Hashing ==<br /> Gegeben: eine Zahl und ein teilweise gefülltes Array. Fügen sie die Zahl in das Array ein. Verwenden Sie die Hashfunktion h(k,i) = h_1(k) + i * h_2(k) mit h_1(k) = k mod m und k_2 = 1 + k mod (m-1). Geben Sie die Sondierungsfolge an.<br /> <br /> == Bäume ==<br /> Gegeben: 5 Bäume. Entscheiden Sie jeweils ob ein korrekter Rot-Schwarz-Baum vorliegt. Begründen Sie ihre Antwort.<br /> <br /> Geben Sie einen Algortithmus an, der ein Array mit n Zahlen in einem unbalancierten Binärbaum sortiert. Sie können dabei die aus der Vorlesung bekannten Operationen auf Binärbäumen verwenden. Geben Sie die asymptotischen Best- und Worst-Case-Laufzeiten an.<br /> <br /> Algoritmus implementieren der berechnet wieviele Knoten k mit a &lt;= k &lt;= b es gibt. (in O(log n))<br /> <br /> Gegeben: Ein Heap. Entfernen Sie das grösste Element (Heap-Extract-Max) und geben Sie den Heap nach der Operation an.<br /> <br /> == Graphen ==<br /> Dijkstras Algortitmus anwenden.<br /> <br /> Problemstellung: Aus einem Rohstoff wird über Zwischenzustände ein Endprodukt erstellt. Ein DAG ist gegeben. Die Kantengewichte sind prozentuale Angaben darüber wieviel von der vorherigen Masse noch da ist (alle &lt; 100%). Gesucht ist der Weg mit dem geringsten Verlust.<br /> * Warum kann der optimale Pfad keine Zyklen enthalten?<br /> * Welchem aus der Veranstaltung bekannten Problem ähnelt dieses?<br /> * Passen Sie den zu dem bekannten Problem gehörenden Algorithmus an dieses Problem an.<br /> <br /> Geben die folgenden Algortithmen einen MST (minimal-spanning-tree) zurück?<br /> * Alg 1<br /> ** initialisiere T mit der Leeren Menge<br /> ** für jede Kante x tue<br /> *** Wenn T vereinigt x Zyklenfrei<br /> **** T &lt;- T vereinigt x<br /> <br /> * Alg 2<br /> ** initialisiere T mit der Kantenmenge<br /> ** für jede Kante x sortiert von gross nach klein tue<br /> *** Wenn T ohne x verbunden<br /> **** T &lt;- T ohne x<br /> <br /> == Dynamische Programmierung ==<br /> Fragestellung: Verbindungen zwischen Städten mit der Bahn, minimaler Pfad mit max. k Mal umsteigen<br /> * Randbedingungen formulieren<br /> * Rekursionsgleichung formulieren<br /> * Algorithmus implementieren<br /> * Laufzeit?<br /> <br /> [[Kategorie:Gedaechtnisprotokoll]]</div>

80.171.22.53 https://wiki.mafiasi.de/index.php?title=Ged%C3%A4chtnisprotokoll_AD08-1&diff=5027 2008-02-18T18:58:33Z

<p>80.171.22.53: /* Graphen */</p> <hr /> <div>Die Klausur war zeitlich kaum zu schaffen. Die schwierigkeit der einzelnen Aufgaben wurde unterschiedlich zwischen angemessen und zu hoch bis viel zu hoch bewertet.<br /> <br /> Man konnte eine handbeschriebene Din-A4-Seite mit beliebigem Inhalt mitbringen.<br /> <br /> <br /> == Multiple-Choice Teil ==<br /> <br /> * Hashing<br /> * P/NP<br /> <br /> == asymptotische Laufzeiten ==<br /> Berechnen Sie mit dem Master-Theorem: (3 Rekurenzgleichungen folgen)<br /> <br /> Finden Sie die geschlossene Form für folgende Rekurenzgleichung: T(sqrt(N))+1 (oder so ähnlich)&lt;br&gt;<br /> Sie können annehmen dass n \in 2^{2^i} mit i \in \mathbb{N} ist.<br /> <br /> Stellen sie die Rekurenzgleichung für folgenden Algorithmus auf und geben Sie seine asymptotische Laufzeit an. (ein Algorithmus folgt)<br /> <br /> Zeigen Sie anhand der Definition des O-Kalküls: f(n) = O(g(n)). (Natürlich für konkrete f und g).<br /> <br /> == Suchen ==<br /> Gegeben: Ein Array von Zahlen, Mehrere andere Arrays mit denselben Zahlen, eine Liste mit dem bekannten Sortieralgorithmen Insertion-, Selection-, Bubble- und Quicksort.<br /> <br /> Zuordnen: Welcher Algorithmus hat welches Array als Zwischenergebnis produziert?<br /> <br /> Quicksort<br /> <br /> Annahme:Jedes Element steht maximal k Plätze von seinem richtigen entfernt<br /> * Zeigen Sie, dass eine Vertauschung von &lt;nowiki&gt;A[j] und A[j+1] mit A[j] &gt; A[j+1]&lt;/nowiki&gt; diese Eigenschaft nicht zerstört.<br /> * Passen Sie Bubble-Sort an die Zusatzbedingung an. (Bubble-Sort gegeben)<br /> <br /> == Hashing ==<br /> Gegeben: eine Zahl und ein teilweise gefülltes Array. Fügen sie die Zahl in das Array ein. Verwenden Sie die Hashfunktion h(k,i) = h_1(k) + i * h_2(k) mit h_1(k) = k mod m und k_2 = 1 + k mod (m-1). Geben Sie die Sondierungsfolge an.<br /> <br /> == Bäume ==<br /> Gegeben: 5 Bäume. Entscheiden Sie jeweils ob ein korrekter Rot-Schwarz-Baum vorliegt. Begründen Sie ihre Antwort.<br /> <br /> Geben Sie einen Algortithmus an, der ein Array mit n Zahlen in einem unbalancierten Binärbaum sortiert. Sie können dabei die aus der Vorlesung bekannten Operationen auf Binärbäumen verwenden. Geben Sie die asymptotischen Best- und Worst-Case-Laufzeiten an.<br /> <br /> Algoritmus implementieren der berechnet wieviele Knoten k mit a &lt;= k &lt;= b es gibt. (in O(log n))<br /> <br /> == Graphen ==<br /> Dijkstras Algortitmus anwenden.<br /> <br /> Problemstellung: Aus einem Rohstoff wird über Zwischenzustände ein Endprodukt erstellt. Ein DAG ist gegeben. Die Kantengewichte sind prozentuale Angaben darüber wieviel von der vorherigen Masse noch da ist (alle &lt; 100%). Gesucht ist der Weg mit dem geringsten Verlust.<br /> * Warum kann der optimale Pfad keine Zyklen enthalten?<br /> * Welchem aus der Veranstaltung bekannten Problem ähnelt dieses?<br /> * Passen Sie den zu dem bekannten Problem gehörenden Algorithmus an dieses Problem an.<br /> <br /> Geben die folgenden Algortithmen einen MST (minimal-spanning-tree) zurück?<br /> * Alg 1<br /> ** initialisiere T mit der Leeren Menge<br /> ** für jede Kante x tue<br /> *** Wenn T vereinigt x Zyklenfrei<br /> **** T &lt;- T vereinigt x<br /> <br /> * Alg 2<br /> ** initialisiere T mit der Kantenmenge<br /> ** für jede Kante x sortiert von gross nach klein tue<br /> *** Wenn T ohne x verbunden<br /> **** T &lt;- T ohne x<br /> <br /> == Dynamische Programmierung ==<br /> Fragestellung: Verbindungen zwischen Städten mit der Bahn, minimaler Pfad mit max. k Mal umsteigen<br /> * Randbedingungen formulieren<br /> * Rekursionsgleichung formulieren<br /> * Algorithmus implementieren<br /> * Laufzeit?<br /> <br /> [[Kategorie:Gedaechtnisprotokoll]]</div>

80.171.22.53 https://wiki.mafiasi.de/index.php?title=Ged%C3%A4chtnisprotokoll_AD08-1&diff=5026 2008-02-18T18:54:08Z

<p>80.171.22.53: /* Suchen */</p> <hr /> <div>Die Klausur war zeitlich kaum zu schaffen. Die schwierigkeit der einzelnen Aufgaben wurde unterschiedlich zwischen angemessen und zu hoch bis viel zu hoch bewertet.<br /> <br /> Man konnte eine handbeschriebene Din-A4-Seite mit beliebigem Inhalt mitbringen.<br /> <br /> <br /> == Multiple-Choice Teil ==<br /> <br /> * Hashing<br /> * P/NP<br /> <br /> == asymptotische Laufzeiten ==<br /> Berechnen Sie mit dem Master-Theorem: (3 Rekurenzgleichungen folgen)<br /> <br /> Finden Sie die geschlossene Form für folgende Rekurenzgleichung: T(sqrt(N))+1 (oder so ähnlich)&lt;br&gt;<br /> Sie können annehmen dass n \in 2^{2^i} mit i \in \mathbb{N} ist.<br /> <br /> Stellen sie die Rekurenzgleichung für folgenden Algorithmus auf und geben Sie seine asymptotische Laufzeit an. (ein Algorithmus folgt)<br /> <br /> Zeigen Sie anhand der Definition des O-Kalküls: f(n) = O(g(n)). (Natürlich für konkrete f und g).<br /> <br /> == Suchen ==<br /> Gegeben: Ein Array von Zahlen, Mehrere andere Arrays mit denselben Zahlen, eine Liste mit dem bekannten Sortieralgorithmen Insertion-, Selection-, Bubble- und Quicksort.<br /> <br /> Zuordnen: Welcher Algorithmus hat welches Array als Zwischenergebnis produziert?<br /> <br /> Quicksort<br /> <br /> Annahme:Jedes Element steht maximal k Plätze von seinem richtigen entfernt<br /> * Zeigen Sie, dass eine Vertauschung von &lt;nowiki&gt;A[j] und A[j+1] mit A[j] &gt; A[j+1]&lt;/nowiki&gt; diese Eigenschaft nicht zerstört.<br /> * Passen Sie Bubble-Sort an die Zusatzbedingung an. (Bubble-Sort gegeben)<br /> <br /> == Hashing ==<br /> Gegeben: eine Zahl und ein teilweise gefülltes Array. Fügen sie die Zahl in das Array ein. Verwenden Sie die Hashfunktion h(k,i) = h_1(k) + i * h_2(k) mit h_1(k) = k mod m und k_2 = 1 + k mod (m-1). Geben Sie die Sondierungsfolge an.<br /> <br /> == Bäume ==<br /> Gegeben: 5 Bäume. Entscheiden Sie jeweils ob ein korrekter Rot-Schwarz-Baum vorliegt. Begründen Sie ihre Antwort.<br /> <br /> Geben Sie einen Algortithmus an, der ein Array mit n Zahlen in einem unbalancierten Binärbaum sortiert. Sie können dabei die aus der Vorlesung bekannten Operationen auf Binärbäumen verwenden. Geben Sie die asymptotischen Best- und Worst-Case-Laufzeiten an.<br /> <br /> Algoritmus implementieren der berechnet wieviele Knoten k mit a &lt;= k &lt;= b es gibt. (in O(log n))<br /> <br /> == Graphen ==<br /> Dijkstras Algortitmus anwenden.<br /> <br /> Problemstellung: Aus einem Rohstoff wird über Zwischenzustände ein Endprodukt erstellt. Ein DAG ist gegeben. Die Kantengewichte sind prozentuale Angaben darüber wieviel von der vorherigen Masse noch da ist (alle &lt; 100%). Gesucht ist der Weg mit dem geringsten Verlust.<br /> * Warum kann der optimale Pfad keine Zyklen enthalten?<br /> * Welchem aus der Veranstaltung bekannten Problem ähnelt dieses?<br /> * Passen Sie den zu dem bekannten Problem gehörenden Algorithmus an dieses Problem an.<br /> <br /> == Dynamische Programmierung ==<br /> Fragestellung: Verbindungen zwischen Städten mit der Bahn, minimaler Pfad mit max. k Mal umsteigen<br /> * Randbedingungen formulieren<br /> * Rekursionsgleichung formulieren<br /> * Algorithmus implementieren<br /> * Laufzeit?<br /> <br /> [[Kategorie:Gedaechtnisprotokoll]]</div>

80.171.22.53 https://wiki.mafiasi.de/index.php?title=Ged%C3%A4chtnisprotokoll_AD08-1&diff=5025 2008-02-18T18:50:30Z

<p>80.171.22.53: /* Hashing */</p> <hr /> <div>Die Klausur war zeitlich kaum zu schaffen. Die schwierigkeit der einzelnen Aufgaben wurde unterschiedlich zwischen angemessen und zu hoch bis viel zu hoch bewertet.<br /> <br /> Man konnte eine handbeschriebene Din-A4-Seite mit beliebigem Inhalt mitbringen.<br /> <br /> <br /> == Multiple-Choice Teil ==<br /> <br /> * Hashing<br /> * P/NP<br /> <br /> == asymptotische Laufzeiten ==<br /> Berechnen Sie mit dem Master-Theorem: (3 Rekurenzgleichungen folgen)<br /> <br /> Finden Sie die geschlossene Form für folgende Rekurenzgleichung: T(sqrt(N))+1 (oder so ähnlich)&lt;br&gt;<br /> Sie können annehmen dass n \in 2^{2^i} mit i \in \mathbb{N} ist.<br /> <br /> Stellen sie die Rekurenzgleichung für folgenden Algorithmus auf und geben Sie seine asymptotische Laufzeit an. (ein Algorithmus folgt)<br /> <br /> Zeigen Sie anhand der Definition des O-Kalküls: f(n) = O(g(n)). (Natürlich für konkrete f und g).<br /> <br /> == Suchen ==<br /> Gegeben: Ein Array von Zahlen, Mehrere andere Arrays mit denselben Zahlen, eine Liste mit bekannten Sortieralgorithmen<br /> <br /> Zuordnen: Welcher Algorithmus hat welches Array als Zwischenergebnis produziert?<br /> <br /> Quicksort<br /> <br /> Bubble-Sort an Zusatzbedingung anpassen: Jedes Element steht maximal k Plätze von seinem richtigen entfernt. Quicksort war gegeben.<br /> <br /> == Hashing ==<br /> Gegeben: eine Zahl und ein teilweise gefülltes Array. Fügen sie die Zahl in das Array ein. Verwenden Sie die Hashfunktion h(k,i) = h_1(k) + i * h_2(k) mit h_1(k) = k mod m und k_2 = 1 + k mod (m-1). Geben Sie die Sondierungsfolge an.<br /> <br /> == Bäume ==<br /> Gegeben: 5 Bäume. Entscheiden Sie jeweils ob ein korrekter Rot-Schwarz-Baum vorliegt. Begründen Sie ihre Antwort.<br /> <br /> Geben Sie einen Algortithmus an, der ein Array mit n Zahlen in einem unbalancierten Binärbaum sortiert. Sie können dabei die aus der Vorlesung bekannten Operationen auf Binärbäumen verwenden. Geben Sie die asymptotischen Best- und Worst-Case-Laufzeiten an.<br /> <br /> Algoritmus implementieren der berechnet wieviele Knoten k mit a &lt;= k &lt;= b es gibt. (in O(log n))<br /> <br /> == Graphen ==<br /> Dijkstras Algortitmus anwenden.<br /> <br /> Problemstellung: Aus einem Rohstoff wird über Zwischenzustände ein Endprodukt erstellt. Ein DAG ist gegeben. Die Kantengewichte sind prozentuale Angaben darüber wieviel von der vorherigen Masse noch da ist (alle &lt; 100%). Gesucht ist der Weg mit dem geringsten Verlust.<br /> * Warum kann der optimale Pfad keine Zyklen enthalten?<br /> * Welchem aus der Veranstaltung bekannten Problem ähnelt dieses?<br /> * Passen Sie den zu dem bekannten Problem gehörenden Algorithmus an dieses Problem an.<br /> <br /> == Dynamische Programmierung ==<br /> Fragestellung: Verbindungen zwischen Städten mit der Bahn, minimaler Pfad mit max. k Mal umsteigen<br /> * Randbedingungen formulieren<br /> * Rekursionsgleichung formulieren<br /> * Algorithmus implementieren<br /> * Laufzeit?<br /> <br /> [[Kategorie:Gedaechtnisprotokoll]]</div>

80.171.22.53 https://wiki.mafiasi.de/index.php?title=Ged%C3%A4chtnisprotokoll_AD08-1&diff=5024 2008-02-18T18:47:14Z

<p>80.171.22.53: /* Bäume */</p> <hr /> <div>Die Klausur war zeitlich kaum zu schaffen. Die schwierigkeit der einzelnen Aufgaben wurde unterschiedlich zwischen angemessen und zu hoch bis viel zu hoch bewertet.<br /> <br /> Man konnte eine handbeschriebene Din-A4-Seite mit beliebigem Inhalt mitbringen.<br /> <br /> <br /> == Multiple-Choice Teil ==<br /> <br /> * Hashing<br /> * P/NP<br /> <br /> == asymptotische Laufzeiten ==<br /> Berechnen Sie mit dem Master-Theorem: (3 Rekurenzgleichungen folgen)<br /> <br /> Finden Sie die geschlossene Form für folgende Rekurenzgleichung: T(sqrt(N))+1 (oder so ähnlich)&lt;br&gt;<br /> Sie können annehmen dass n \in 2^{2^i} mit i \in \mathbb{N} ist.<br /> <br /> Stellen sie die Rekurenzgleichung für folgenden Algorithmus auf und geben Sie seine asymptotische Laufzeit an. (ein Algorithmus folgt)<br /> <br /> Zeigen Sie anhand der Definition des O-Kalküls: f(n) = O(g(n)). (Natürlich für konkrete f und g).<br /> <br /> == Suchen ==<br /> Gegeben: Ein Array von Zahlen, Mehrere andere Arrays mit denselben Zahlen, eine Liste mit bekannten Sortieralgorithmen<br /> <br /> Zuordnen: Welcher Algorithmus hat welches Array als Zwischenergebnis produziert?<br /> <br /> Quicksort<br /> <br /> Bubble-Sort an Zusatzbedingung anpassen: Jedes Element steht maximal k Plätze von seinem richtigen entfernt. Quicksort war gegeben.<br /> <br /> == Bäume ==<br /> Gegeben: 5 Bäume. Entscheiden Sie jeweils ob ein korrekter Rot-Schwarz-Baum vorliegt. Begründen Sie ihre Antwort.<br /> <br /> Geben Sie einen Algortithmus an, der ein Array mit n Zahlen in einem unbalancierten Binärbaum sortiert. Sie können dabei die aus der Vorlesung bekannten Operationen auf Binärbäumen verwenden. Geben Sie die asymptotischen Best- und Worst-Case-Laufzeiten an.<br /> <br /> Algoritmus implementieren der berechnet wieviele Knoten k mit a &lt;= k &lt;= b es gibt. (in O(log n))<br /> <br /> == Graphen ==<br /> Dijkstras Algortitmus anwenden.<br /> <br /> Problemstellung: Aus einem Rohstoff wird über Zwischenzustände ein Endprodukt erstellt. Ein DAG ist gegeben. Die Kantengewichte sind prozentuale Angaben darüber wieviel von der vorherigen Masse noch da ist (alle &lt; 100%). Gesucht ist der Weg mit dem geringsten Verlust.<br /> * Warum kann der optimale Pfad keine Zyklen enthalten?<br /> * Welchem aus der Veranstaltung bekannten Problem ähnelt dieses?<br /> * Passen Sie den zu dem bekannten Problem gehörenden Algorithmus an dieses Problem an.<br /> <br /> == Dynamische Programmierung ==<br /> Fragestellung: Verbindungen zwischen Städten mit der Bahn, minimaler Pfad mit max. k Mal umsteigen<br /> * Randbedingungen formulieren<br /> * Rekursionsgleichung formulieren<br /> * Algorithmus implementieren<br /> * Laufzeit?<br /> <br /> [[Kategorie:Gedaechtnisprotokoll]]</div>

80.171.22.53 https://wiki.mafiasi.de/index.php?title=Ged%C3%A4chtnisprotokoll_AD08-1&diff=5023 2008-02-18T18:44:08Z

<p>80.171.22.53: /* asymptotische Laufzeit */</p> <hr /> <div>Die Klausur war zeitlich kaum zu schaffen. Die schwierigkeit der einzelnen Aufgaben wurde unterschiedlich zwischen angemessen und zu hoch bis viel zu hoch bewertet.<br /> <br /> Man konnte eine handbeschriebene Din-A4-Seite mit beliebigem Inhalt mitbringen.<br /> <br /> <br /> == Multiple-Choice Teil ==<br /> <br /> * Hashing<br /> * P/NP<br /> <br /> == asymptotische Laufzeiten ==<br /> Berechnen Sie mit dem Master-Theorem: (3 Rekurenzgleichungen folgen)<br /> <br /> Finden Sie die geschlossene Form für folgende Rekurenzgleichung: T(sqrt(N))+1 (oder so ähnlich)&lt;br&gt;<br /> Sie können annehmen dass n \in 2^{2^i} mit i \in \mathbb{N} ist.<br /> <br /> Stellen sie die Rekurenzgleichung für folgenden Algorithmus auf und geben Sie seine asymptotische Laufzeit an. (ein Algorithmus folgt)<br /> <br /> Zeigen Sie anhand der Definition des O-Kalküls: f(n) = O(g(n)). (Natürlich für konkrete f und g).<br /> <br /> == Suchen ==<br /> Gegeben: Ein Array von Zahlen, Mehrere andere Arrays mit denselben Zahlen, eine Liste mit bekannten Sortieralgorithmen<br /> <br /> Zuordnen: Welcher Algorithmus hat welches Array als Zwischenergebnis produziert?<br /> <br /> Quicksort<br /> <br /> Bubble-Sort an Zusatzbedingung anpassen: Jedes Element steht maximal k Plätze von seinem richtigen entfernt. Quicksort war gegeben.<br /> <br /> == Bäume ==<br /> Algoritmus implementieren der berechnet wieviele Knoten k mit a &lt;= k &lt;= b es gibt. (in O(log n))<br /> <br /> == Graphen ==<br /> Dijkstras Algortitmus anwenden.<br /> <br /> Problemstellung: Aus einem Rohstoff wird über Zwischenzustände ein Endprodukt erstellt. Ein DAG ist gegeben. Die Kantengewichte sind prozentuale Angaben darüber wieviel von der vorherigen Masse noch da ist (alle &lt; 100%). Gesucht ist der Weg mit dem geringsten Verlust.<br /> * Warum kann der optimale Pfad keine Zyklen enthalten?<br /> * Welchem aus der Veranstaltung bekannten Problem ähnelt dieses?<br /> * Passen Sie den zu dem bekannten Problem gehörenden Algorithmus an dieses Problem an.<br /> <br /> == Dynamische Programmierung ==<br /> Fragestellung: Verbindungen zwischen Städten mit der Bahn, minimaler Pfad mit max. k Mal umsteigen<br /> * Randbedingungen formulieren<br /> * Rekursionsgleichung formulieren<br /> * Algorithmus implementieren<br /> * Laufzeit?<br /> <br /> [[Kategorie:Gedaechtnisprotokoll]]</div>

80.171.22.53 https://wiki.mafiasi.de/index.php?title=Ged%C3%A4chtnisprotokoll_AD08-1&diff=5022 2008-02-18T18:38:36Z

<p>80.171.22.53: /* O-Kalkül */</p> <hr /> <div>Die Klausur war zeitlich kaum zu schaffen. Die schwierigkeit der einzelnen Aufgaben wurde unterschiedlich zwischen angemessen und zu hoch bis viel zu hoch bewertet.<br /> <br /> Man konnte eine handbeschriebene Din-A4-Seite mit beliebigem Inhalt mitbringen.<br /> <br /> <br /> == Multiple-Choice Teil ==<br /> <br /> * Hashing<br /> * P/NP<br /> <br /> == O-Kalkül ==<br /> Zeigen Sie anhand der Definition des O-Kalküls: f(n) = O(g(n)). (Natürlich für konkrete f und g).<br /> <br /> == Suchen ==<br /> Gegeben: Ein Array von Zahlen, Mehrere andere Arrays mit denselben Zahlen, eine Liste mit bekannten Sortieralgorithmen<br /> <br /> Zuordnen: Welcher Algorithmus hat welches Array als Zwischenergebnis produziert?<br /> <br /> Quicksort<br /> <br /> Bubble-Sort an Zusatzbedingung anpassen: Jedes Element steht maximal k Plätze von seinem richtigen entfernt. Quicksort war gegeben.<br /> <br /> == Bäume ==<br /> Algoritmus implementieren der berechnet wieviele Knoten k mit a &lt;= k &lt;= b es gibt. (in O(log n))<br /> <br /> == Graphen ==<br /> Dijkstras Algortitmus anwenden.<br /> <br /> Problemstellung: Aus einem Rohstoff wird über Zwischenzustände ein Endprodukt erstellt. Ein DAG ist gegeben. Die Kantengewichte sind prozentuale Angaben darüber wieviel von der vorherigen Masse noch da ist (alle &lt; 100%). Gesucht ist der Weg mit dem geringsten Verlust.<br /> * Warum kann der optimale Pfad keine Zyklen enthalten?<br /> * Welchem aus der Veranstaltung bekannten Problem ähnelt dieses?<br /> * Passen Sie den zu dem bekannten Problem gehörenden Algorithmus an dieses Problem an.<br /> <br /> == Dynamische Programmierung ==<br /> Fragestellung: Verbindungen zwischen Städten mit der Bahn, minimaler Pfad mit max. k Mal umsteigen<br /> * Randbedingungen formulieren<br /> * Rekursionsgleichung formulieren<br /> * Algorithmus implementieren<br /> * Laufzeit?<br /> <br /> [[Kategorie:Gedaechtnisprotokoll]]</div>

80.171.22.53 https://wiki.mafiasi.de/index.php?title=Ged%C3%A4chtnisprotokoll_AD08-1&diff=5021 2008-02-18T18:35:08Z

<p>80.171.22.53: /* Graphen */ +%-DAG</p> <hr /> <div>Die Klausur war zeitlich kaum zu schaffen. Die schwierigkeit der einzelnen Aufgaben wurde unterschiedlich zwischen angemessen und zu hoch bis viel zu hoch bewertet.<br /> <br /> Man konnte eine handbeschriebene Din-A4-Seite mit beliebigem Inhalt mitbringen.<br /> <br /> <br /> == Multiple-Choice Teil ==<br /> <br /> * Hashing<br /> * P/NP<br /> <br /> == Suchen ==<br /> Gegeben: Ein Array von Zahlen, Mehrere andere Arrays mit denselben Zahlen, eine Liste mit bekannten Sortieralgorithmen<br /> <br /> Zuordnen: Welcher Algorithmus hat welches Array als Zwischenergebnis produziert?<br /> <br /> Quicksort<br /> <br /> Bubble-Sort an Zusatzbedingung anpassen: Jedes Element steht maximal k Plätze von seinem richtigen entfernt. Quicksort war gegeben.<br /> <br /> == Bäume ==<br /> Algoritmus implementieren der berechnet wieviele Knoten k mit a &lt;= k &lt;= b es gibt. (in O(log n))<br /> <br /> == Graphen ==<br /> Dijkstras Algortitmus anwenden.<br /> <br /> Problemstellung: Aus einem Rohstoff wird über Zwischenzustände ein Endprodukt erstellt. Ein DAG ist gegeben. Die Kantengewichte sind prozentuale Angaben darüber wieviel von der vorherigen Masse noch da ist (alle &lt; 100%). Gesucht ist der Weg mit dem geringsten Verlust.<br /> * Warum kann der optimale Pfad keine Zyklen enthalten?<br /> * Welchem aus der Veranstaltung bekannten Problem ähnelt dieses?<br /> * Passen Sie den zu dem bekannten Problem gehörenden Algorithmus an dieses Problem an.<br /> <br /> == Dynamische Programmierung ==<br /> Fragestellung: Verbindungen zwischen Städten mit der Bahn, minimaler Pfad mit max. k Mal umsteigen<br /> * Randbedingungen formulieren<br /> * Rekursionsgleichung formulieren<br /> * Algorithmus implementieren<br /> * Laufzeit?<br /> <br /> [[Kategorie:Gedaechtnisprotokoll]]</div>

80.171.22.53 https://wiki.mafiasi.de/index.php?title=Hauptseite&diff=5020 2008-02-18T18:28:03Z

<p>80.171.22.53: +kat:gedprok-link</p> <hr /> <div>[[Bild:Hochschulsport.gif|right]]<br /> [[Bild:Hetzner-partner.jpg|right|111px]]<br /> [[Bild:Boykott20.gif|right|111px]]<br /> http://www.informatik.uni-hamburg.de/Fachschaft/pics/fslogo.gif<br /> <br /> Willkommen auf den Webseiten der [[Fachschaft]] Informatik.<br /> Wir versuchen hier, alle wichtigen Informationen über das Informatik-Studium an der Universität Hamburg zusammenzustellen.<br /> Falls etwas fehlt, ergänze es bitte direkt auf der Seite, wo es fehlt.<br /> Dazu klickst Du einfach auf den Link ''bearbeiten'' am oberen Rand der Seite.<br /> Du darfst hier wirklich alles ändern, was Dir nicht gefällt. Also keine falsche Scheu.<br /> <br /> == Aktionen ==<br /> * [https://jabber.mafiasi.de/ Freie Kommunikation für alle!] Unser neuer Jabber-Server ist online.<br /> * [http://www.izshamburg.de/ Studiengebuehrenboykott 2.0] Freie Bildung fuer alle! Von der Kita bis zur Hochschule.<br /> * [https://winter.gotdns.org/~teythoon/befreiung.html Befreiungsantraege für alle!] Der Studiengebuehrenbefreiungsantragsgenerator.<br /> <br /> == Informationen für Studienbeginner ==<br /> <br /> * Für Studieninteressierte gibt es viele nützliche [http://www.informatik.uni-hamburg.de/Info/Studium/intr.shtml Infos].<br /> * Wenn du im Oktober hier anfängst zu studieren, solltest du die [[Orientierungseinheit]] besuchen!<br /> * Die erste Anlaufstelle für alle Fragen zum Studium ist das [https://www.fb18.de/ Forum].<br /> * Eine [[Wegbeschreibung]] für alle, die uns besuchen wollen, gibt es auch.<br /> * Wenn du interessiert bist solltest du der [[MafiA]] beitreten.<br /> <br /> == Infos zum Studium ==<br /> <br /> * [[STiNE]]<br /> * [[Lehrtableau]] und [http://www.informatik.uni-hamburg.de/cgi-bin/kvv/ausgabe/index_start.pl Kommentiertes Vorlesungsverzeichnis] ? Alle Veranstaltungen im Überblick.<br /> * [[Diplomstudiengang]] (1998-2004)<br /> * [[Bachelor|Bachelorstudiengang]] (seit 2005)<br /> * [[Master]]studiengang (seit 2007)<br /> * [http://www.informatik.uni-hamburg.de/Fachschaft/gprot/ Gedächtnisprotokolle] ? Protokolle von Prüfungen. [[:Kategorie:Gedaechtnisprotokoll|Selber schreiben]] nicht vergessen!<br /> * Das [[Informatikum]] und ähnliche Örtlichkeiten<br /> * Studentische Arbeitsräume in [[Arbeitsräume_Stellingen|Stellingen]] und am [[Arbeitsräume_Hauptcampus|Hauptcampus]]<br /> <br /> == Interessenvertretung und Gremien ==<br /> <br /> * [[Gremien]] sind offiziell vom Department, von der [[Fakultät]] oder von der Universität eingesetzt, um ein bestimmtes Thema zu besprechen. Wer euer direkter Ansprechpartner ist, findet ihr in der [[GremienMitgliederListe]].<br /> * [[VVProtokolle|Protokolle]] von den [[VV|Vollversammlungen]]<br /> * [[Gremieninfos]] ? eine Sammlung von Infos, die für Gremienvertreter interessant sein könnten.<br /> * [[MafiA]] ? die '''M'''enge '''a'''ller '''f'''achschafts'''i'''nteressierten '''A'''ktivisten unterhält eine Mailinglistliste, über die wichtige Informationen zum aktuellen Geschehen verschickt werden.<br /> * Bei uns am Informatikum:<br /> ** [[Fachschaftsrat|Fachschaftsrat (FSR)]] ? Eure Interessenvertretung und Ansprechpartner für Probleme jeglicher Art.<br /> ** [[Arbeitsgemeinschaften]] sind Gruppen von Studierenden, die gemeinsam versuchen, etwas für andere Studierende zu tun.<br /> ** [http://www.informatik.uni-hamburg.de/cgi-bin/informatik/gremien-wiki.pl Gremien-Wiki] ? ein Fachbereichsöffentliches Wiki für interne Informationen. Nur von den Netzen der Uni aus zugreifbar.<br /> <br /> == Unterhaltsames ==<br /> <br /> * [http://www.nomaden.org/ Nomaden] ? Die Nomaden, der Informatiker-Stammtisch, jede Woche in einer anderen Kneipe<br /> * [[BitBilder]] samt [[BitBilderFAQ]] ? Welches [[Bit]] wozu verwenden?<br /> * [[Professorensprüche]] ? Merk-würdige Sprüche von Professoren und anderen Menschen<br /> * der [[FachBereichsSong]] - The Buggles mal anders<br /> <br /> == Weiteres Wissenswertes ==<br /> <br /> * [[GuteVeranstaltung]] ? was würdest du dir von einer guten Veranstaltung wünschen? (Liebe Professoren, lesen!)<br /> * [[Linkliste]] ? sonstige wichtige Seiten<br /> * Ein [[BuntesSeminar]] hat leider schon lange nicht mehr stattgefunden.<br /> * Die Fachschaft vermietet [http://www.informatik.uni-hamburg.de/Fachschaft/fsr/button.html Buttonmaschinen].<br /> * Eine [[Wegbeschreibung]] für alle, die uns besuchen wollen.<br /> * [[Hobbys]] der Informatikstudierenden.<br /> * Wichtige Informationen über das [[Rechenzentrum]] und was man da machen kann.<br /> * [[Verbindungen]] - was dein(e) Rechner zuhause können könnte(n), damit zu vernünftig arbeiten kannst.<br /> * [[Essen|Essensmöglichkeiten]] im, um und um das [[Informatikum]] herum.<br /> * [[CiscoVPN|VPN-Verbindung]] unter Linux mit Networmanager<br /> <br /> == Über dieses Wiki ==<br /> Dies ist das neue Wiki des FSR. Wenn du das alte suchst (vielleicht weil einige Inhalte nicht richtig konvertiert wurden), findest du dies unter http://www.informatik.uni-hamburg.de/cgi-bin/fsr-wiki.pl/oldwiki.<br /> <br /> === WikiWikiWeb ===<br /> * [http://de.wikipedia.org/wiki/Wiki Was ist ein Wiki?]<br /> * Diese Seiten benutzen das [http://www.mediawiki.org/ Mediawiki]<br /> * [http://www.mediawiki.org/wiki/Help:Formatting Wie formatiere ich Text?]<br /> * [http://www.mediawiki.org/wiki/Help:Editing_pages Wie kann ich Wiki-Seiten bearbeiten?]<br /> * [[SpielWiese]] zum ausprobieren vom Wiki-Syntax<br /> <br /> === Sonstiges ===<br /> * Übersicht über die [[Spezial:Benutzer|Bewohner]] dieses Wikis ([[Bewohner|alte Übersicht]])<br /> * [[WikiNode]] ? Wir und unsere Nachbarn im Wiki Web</div>

80.171.22.53 https://wiki.mafiasi.de/index.php?title=Ged%C3%A4chtnisprotokoll_AD08-1&diff=5016 2008-02-18T16:58:36Z

<p>80.171.22.53: pling!</p> <hr /> <div>Die Klausur war zeitlich kaum zu schaffen. Die schwierigkeit der einzelnen Aufgaben wurde unterschiedlich zwischen angemessen und zu hoch bis viel zu hoch bewertet.<br /> <br /> Man konnte eine handbeschriebene Din-A4-Seite mit beliebigem Inhalt mitbringen.<br /> <br /> <br /> == Multiple-Choice Teil ==<br /> <br /> * Hashing<br /> * P/NP<br /> <br /> == Suchen ==<br /> Gegeben: Ein Array von Zahlen, Mehrere andere Arrays mit denselben Zahlen, eine Liste mit bekannten Sortieralgorithmen<br /> <br /> Zuordnen: Welcher Algorithmus hat welches Array als Zwischenergebnis produziert?<br /> <br /> Quicksort<br /> <br /> Bubble-Sort an Zusatzbedingung anpassen: Jedes Element steht maximal k Plätze von seinem richtigen entfernt. Quicksort war gegeben.<br /> <br /> == Bäume ==<br /> Algoritmus implementieren der berechnet wieviele Knoten k mit a &lt;= k &lt;= b es gibt. (in O(log n))<br /> <br /> == Graphen ==<br /> Dijkstras Algortitmus anwenden.<br /> <br /> Einen Algoritmus scheiben + Laufzeit?<br /> <br /> == Dynamische Programmierung ==<br /> Fragestellung: Verbindungen zwischen Städten mit der Bahn, minimaler Pfad mit max. k Mal umsteigen<br /> * Randbedingungen formulieren<br /> * Rekursionsgleichung formulieren<br /> * Algorithmus implementieren<br /> * Laufzeit?<br /> <br /> [[Kategorie:Gedaechtnisprotokoll]]</div>

80.171.22.53