FB18 - Das Forum für Informatik

fb18.de / Bachelorstudieng / PM Praktische Informatik

AD Tutorium

AD Tutorium 2009-03-03 11:54
Anonymer User
Liebe Hörer der AD-Vorlesung,

auch zur zweiten AD-Klausur (am 26.03.) soll es ein Repetitorium/Tutorium zur
Vorbereitung auf die Klausur geben.

Das Repetitorium findet an vier Tagen

Montag, 09.03,
Dienstag, 10.03,
Mittwoch, 11.03 und
Freitag, 13.03

jeweils von 1000-1300 in C-221 statt.

Falls ihr spezielle Wünsche habt (z.B. Dinge, die ihr bei der ersten Klausur gar nicht konntet),
dann wäre es gut, wenn ihr mir das vorab kurz per Email an heitmann@inf… mitteilt.

Falls jemand an den Terminen gar keine Zeit hat, dann schreibt mir bitte auch eine Email.

Bis nächste Woche dann und entschuldigt bitte die etwas kurzfristige Ankündigung!

Fröhliche Grüße,
Frank

RE: AD Tutorium 2009-03-04 15:57
Anonymer User
wäre es möglich die erste klausur komplett zu besprechen?

RE: AD Tutorium 2009-03-04 22:04
Anonymer User
Hi…

so ähnliche Aufgaben können wir auf jeden Fall machen. - Wobei die zweite
Klausur natürlich schon irgendwie anders sein wird als die erste ;-)

Frank

RE: AD Tutorium 2009-03-05 10:34
Anonymer User
ja das war mir schon klar :-)
hatte nur einige aufgaben nochmal versucht zu lösen und wollte nur wissen, ob ich die auch richtig habe.

RE: AD Tutorium 2009-03-19 17:14
Anonymer User
Kann jemand posten, was in dem Tutorium besprochen wurde und was für Tips gegeben wurden ?
Ich hab das Tuturium irgendwie verschlafen.

RE: AD Tutorium 2009-03-19 23:16
Anonymer User
Hi…

Stofflich behandelt wurde im Prinzip alles. Schwerpunkte lagen auf
den Themen O-Notation, Rekurrenzgleichungen (inkl. Anwendung
des Mastertheorems) und Graphenalgorithmen (Dijkstra,
Bellman-Ford-Moore, Floyd-Warshall (alle fuer kuerzeste Wege),
Prim, Kruskal (beide fuer Spannbaeume), Topologisches Sortieren,
Strenge (heisst manchmal auch Starke) Zusammenhangskomponente
(basieren beide auf Tiefensuche) und Fluesse (Verfahren aehnlich
dem von Ford-Fulkerson, siehe die Uebungsaufgabe dazu).

Wie bei der ersten Klausur sind damit viele Punkte zu machen.

Des weiteren gibt es bestimmt wieder Fragen zu Suchbaeumen und
zu P, NP, NP-Vollstaendigkeit etc. und zu dem ein oder anderen
weiteren Thema (Fragen, die dann eher in die Breite prüfen und dafür
nicht so in die Tiefe).

Die "Probeklausur" im Netz ist weiterhin eine gute Moeglichkeit
zu testen, ob man mit dem Stoff (bzw. dem Stoff, der den Schwer-
punkt der Pruefung ausmacht) gut klar kommt.

Frank :)

RE: AD Tutorium 2009-03-21 11:05
Anonymer User
Müssen wir die Operationen der Suchbäume (insert, fixup, delete usw.) auswendig können ?

RE: AD Tutorium 2009-03-21 12:34
Anonymer User
Bei den grundlegenden Suchbäumen sollte man wissen, wie diese Operationen
funktionieren. Nebenbemerkung: Das hat wenig mit "auswendig können" zu tun.
Wenn du eine Vorstellung davon hast, was ein Suchbaum ist, dann ist die Einfüge-
Operation z.B. ziemlich offensichtlich. Das wichtige ist also, dass du die richtigen
Vorstellungen entwickelst.

Funktionieren heisst im übrigen nicht, dass man den Source-Code davon hinschreiben
können muss (oder noch schlimmer: Den Source-Code genau so wie er im Skript steht
- das wäre dann in der Tat "auswendig können" [25]), aber man muss die Operationen
z.B. an einem gegebenen Suchbaum ausführen können.

Bei Rot-Schwarz- und AVL-Bäumen (spezielle Suchbäume) muss man wissen wie die
definiert sind und warum man die überhaupt will. Die Operationen dort sind bisweilen
zu umständlich, um die sinnvoll in einer Klausur abfragen zu können, aber bspw. kam
ja in der letzten Klausur auch die Frage nach Rotationen bei AVL-Bäumen. Ähnliches ist
auch diesmal vorstellbar. Ferner gab es zu beiden die ein oder andere Übungsaufgabe.

Frank :)

RE: AD Tutorium 2009-03-23 10:55
Anonymer User
wenn ich auswenig einen left-rotate machen muss dann muss ich die operation auswendig lernen. Sie neu herzuleiten dauert meiner Meinung nach zu lange.

RE: AD Tutorium 2009-03-23 13:46
Anonymer User
Ok, ich meinte das ein wenig anders. Sehr oft sagen Studenten vor einer
Theorieprüfung, dass das so viel Stoff *zum auswendig lernen sei*. Damit
sind dann oft Definitionen gemeint. Z.B. gibt es in FGI1 so viele Automaten-
modelle, deren Definition man "auswendig lernen muss".

Nun kann man sich natürlich auf den Stand stellen und so etwas wie
M = (Z, \Sigma, …)
auswendig lernen.

Wenn man aber im Kopf eine Vorstellung (ein Modell) davon hat, was so
ein Automat ist, wozu der da ist und was man damit machen kann (bzw.
können will), dann ist M = (…) einfach nur eine (sehr) kompakte (mathe-
matische) Weise das auszudrücken.

Z.B. will man bei so einem Automat den Begriff des Zustandes haben. Davon
aber nur endlich viele (warum eigentlich? - wenn man die Frage beantworten
kann, erschliesst sich einem meist sehr viel mehr des Stoffes als beim "aus-
wendig lernen) und schon landet man bei der Menge Z. Wobei man sich viel-
leicht fragt, ob man nicht lieber ein Tupel (z_1, z_2, …) nimmt, dann aber zu
dem Ergebnis kommt, dass das doch unpraktisch ist etc.

So hat das dann nicht mehr viel mit auswendig lernen zu tun, sondern eben
mit Verstehen.

Bei den meisten Algorithmischen Verfahren ist das ähnlich. Natürlich muss man
sich das ein oder andere an Wissen aneignen - und in gewisser Weise ist es dann
bestimmt auswendig gelernt - wobei der Unterschied zu "verinnerlichen", "ver-
stehen" usw. hier sehr schwierig ist, find ich -, damit man überhaupt erstmal
anfangen kann. Lernt man z.B. die Fragestellung: "Kürzeste Wege ermitteln" aus-
wendig? Oder ergibt sich das natürlich, dass man sich dafür interessiert?

Das Verfahren von Dijkstra dann aber z.B. lernt man nicht zwingend auswendig.
Man versteht und verinnerlicht die Kernidee.

Nur ein paar Gedanken… ich wollte das jetzt nicht philosophisch ausdiskuttieren ;)

Fröhliche Grüße
und noch viel Spass beim Lernen!
Frank :)

RE: AD Tutorium 2009-03-25 15:43
Anonymer User
Hallo ! Ich lerne gerade für AD und da ist bei mir eine Frage aufgekommen zu P-NP
Sind folgende Aussagen richtig:
P ist keine Teilmenge von NP-Vollständigen aber
P ist eine Teilmenge von NP

Wo liegt dann NP-Schwer ?

RE: AD Tutorium 2009-03-25 15:58
Anonymer User
jedes Sprache aus NP lässt sich in polynomineller Zeit auf eine Sprache des NP schwere Problems reduzieren.

RE: AD Tutorium 2009-03-25 16:00
payne
Ein Problem ist NP-Schwer, wenn sich alle anderen Probleme aus NP in polynomieller Zeit auf dieses reduzieren Lassen. Das Problem muss allerdings selber nicht in NP liegen und das ist der Unterschied zu NP-Vollständig. Damit ist NP-Vollständig eine Teilmenge von NP-Schwer.
Wenn du dir das als Zeichnung vorstellst, liegt ein Teil von NP-Schwer außerhalb von NP und der andere innerhalb. Der Teil, der innerhalb liegt, wird dann NP-Vollständig genannt.

RE: AD Tutorium 2009-03-25 16:01
rothose86
Hallo ! Ich lerne gerade für AD und da ist bei mir eine Frage aufgekommen zu P-NP
Sind folgende Aussagen richtig:
P ist keine Teilmenge von NP-Vollständigen aber
P ist eine Teilmenge von NP

Wo liegt dann NP-Schwer ?

NP-schwer liegt ausserhalb und innerhalb von NP.

RE: AD Tutorium 2009-03-25 16:11
Anonymer User
okay… das habe ich kapiert.
Sind die anderen Aussagen richtig ?
Das Bedeutet, dass wenn ein NP-Schweres Problem in P liegt, dann liegt jedes NP-Problem in P.

RE: AD Tutorium 2009-03-25 16:25
georg
okay… das habe ich kapiert.
Sind die anderen Aussagen richtig ?

Ja, die sind richtig. P ist keine Teilmenge der NP-vollständigen Probleme, weil
die leere Menge nicht NP-vollständig ist. Und P ist eine Teilmenge von NP, das
sieht man direkt an der Definition von deterministischen vs. nichtdeterministischen
Turing-Maschinen.

Das Bedeutet, dass wenn ein NP-Schweres Problem in P liegt, dann liegt jedes NP-Problem in P.

Richtig.

RE: AD Tutorium 2009-03-26 16:14
Anonymer User
wie fandet ihr die klausur ?

RE: AD Tutorium 2009-03-26 17:56
Anonymer User
gemein :(

die erste war viiiiieeelll leichter, zu viel von diesem P, NP, etc.
und die punkte pro aufgabe waren ziemlich wenig

naja mal sehen, vllt hats ja nochmal geklappt