Folie 1

HEINZ NIXDORF INSTITUT Universitt Paderborn EIM Institut fr Informatik 1 Algorithm. Grundlagen des Internets 28. Juli 2003 Christian Schindelhauer Vorlesung Sommersemester 2003 Algorithmische Grundlagen des Internets XIII Christian Schindelhauer schindel@upb.de HEINZ NIXDORF INSTITUT Universitt Paderborn Fakultt fr Elektrotechnik, Informatik und Mathematik Institut fr Informatik AG Theoretische Informatik Algorithmen, Komplexittstheorie, Paralleles Rechnen

Folie 2

HEINZ NIXDORF INSTITUT Universitt Paderborn EIM Institut fr Informatik 2 Algorithm. Grundlagen des Internets 28. Juli 2003 Christian Schindelhauer ACHTUNG 1.Raum nderung: bung findet heute in Raum F1.310 zur gewohnten Zeit statt 2.Vorstellung Projektgruppen Parallel zur bung hier in Raum F0.530 statt. Wir empfehlen 1.Mobile Ad-Hoc Networks based on W-LAN, Bttcher, Rammig Schindelhauer 2.P2P-Netzwerke fr Dynamische Szenarien, Meyer auf der Heide 3.Studienarbeiten, Diplomarbeiten bitte bei Schindelhauer und Volbert anfragen oMobile Ad-Hoc Netzwerke oTCP-Bandweitenallokation oP2P-Netzwerke 4.Studentische Hilfskraft fr Buchprojekt Die Algorithmen des Internets gesucht 5.Veranstaltungen im Winter 2003/2003: oSeminar Advanced Topics of Computational Complexity oPG Mobile Ad-Hoc Networks based on W-LAN oVorbesprechung xx.10.2003, 18 Uhr F1.110 oVorlesung Average-Komplexittstheorie und Average-Case Algorithmen

Folie 3

HEINZ NIXDORF INSTITUT Universitt Paderborn EIM Institut fr Informatik 3 Algorithm. Grundlagen des Internets 28. Juli 2003 Christian Schindelhauer Lastanforderungen oEinige Web-Server haben immer hohe Lastanforderungen Z.B. Nachrichten-Sites, Suchmaschinen, Web- verzeichnisse Fr permanente Anforderungen mssen Server entsprechen ausgelegt werden oAndere leiden unter hohen Fluktuationen, z.B. Z.B. Web-Site des Tages, NASA, Turniere Server-Erweiterung nicht sinnvoll Bedienung der Anfragen aber erwnscht www.google.com www.viadukt- altenbeken.de MontagDienstag www.viadukt- altenbeken.de Mittwoch www.viadukt- altenbeken.de

Folie 4

HEINZ NIXDORF INSTITUT Universitt Paderborn EIM Institut fr Informatik 4 Algorithm. Grundlagen des Internets 28. Juli 2003 Christian Schindelhauer Web-Caching oLeighton, Lewin, et al. STOC 97 Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web Passen bestehende Verfahren fr dynamische Hash-Funktionen an WWW-Anforderungen an oLeighton und Lewin (MIT) grnden Akamai 97 oAkaimai 2003: 15.000 Server in 60 Lndern verbunden mit 1.100 lokalen Netzwerken Web-Cache www.altenbeken- viadukt.de

Folie 5

HEINZ NIXDORF INSTITUT Universitt Paderborn EIM Institut fr Informatik 5 Algorithm. Grundlagen des Internets 28. Juli 2003 Christian Schindelhauer Proxy Caching oJede Web-Seite wird auf einige (wenige) Web-Cache verteilt oNur Startanfrage erreicht Web-Server oLinks referenzieren auf Seiten im Web- Cache oDann surft der Web-Client nur noch auf den Web-Cache oVorteil: Kein Bottleneck oNachteil: Lastbalancierung nur implizit mglich Hohe Anforderung an Caching- Algorithmus Webseiten Web-Server Web-Clients Web-Cache Link

Folie 6

HEINZ NIXDORF INSTITUT Universitt Paderborn EIM Institut fr Informatik 6 Algorithm. Grundlagen des Internets 28. Juli 2003 Christian Schindelhauer Anforderungen an Caching-Algorithmus 1.Balance Gleichmige Verteilung der Seiten 2.Dynamik Effizientes Einfgen/Lschen von neuen Web-Cache-Servern 3.Views Web-Clients sehen unterschiedliche Menge von Web-Caches

Folie 7

HEINZ NIXDORF INSTITUT Universitt Paderborn EIM Institut fr Informatik 7 Algorithm. Grundlagen des Internets 28. Juli 2003 Christian Schindelhauer Ranged Hash-Funktionen oGegeben: Elemente (Items) I, Anzahl: I = | I | Caches (Buckets) B Views V 2 B oRanged Hash-Funktion: Voraussetzung:

Folie 8

HEINZ NIXDORF INSTITUT Universitt Paderborn EIM Institut fr Informatik 8 Algorithm. Grundlagen des Internets 28. Juli 2003 Christian Schindelhauer Anforderungen an Ranged Hash-Funktionen 1. Monotonie oSeiten, die im umfassenderen View einem Cache zugewiesen sind, werden nicht umorganisiert View 1: View 2: Seiten Cache

Folie 9

HEINZ NIXDORF INSTITUT Universitt Paderborn EIM Institut fr Informatik 9 Algorithm. Grundlagen des Internets 28. Juli 2003 Christian Schindelhauer Anforderungen an Ranged Hash-Funktionen 2. Balance Fr jeden View V ist die Hash-Funktion f V (i) balanciert View 1: View 2: Seiten Cache

Folie 10

HEINZ NIXDORF INSTITUT Universitt Paderborn EIM Institut fr Informatik 10 Algorithm. Grundlagen des Internets 28. Juli 2003 Christian Schindelhauer Anforderungen an Ranged Hash-Funktionen 3. Spread Die Verbreitung (i) (spread) einer Seite i ist die Gesamtanzahl aller notwendigen Kopien (ber alle Views) View 1: View 2: View 3:

Folie 11

HEINZ NIXDORF INSTITUT Universitt Paderborn EIM Institut fr Informatik 11 Algorithm. Grundlagen des Internets 28. Juli 2003 Christian Schindelhauer Anforderungen an Ranged Hash-Funktionen 4. Load View 1: View 2: View 3: Die Last (b) (load) eines Caches b ist die Gesamtanzahl aller notwendigen Kopien (ber alle Views)

Folie 12

HEINZ NIXDORF INSTITUT Universitt Paderborn EIM Institut fr Informatik 12 Algorithm. Grundlagen des Internets 28. Juli 2003 Christian Schindelhauer Blle und Krbe Lemma Werden m Blle zufllig in n Krbe geworfen. Dann gilt: 1.Die erwartete Zahl von Bllen pro Korb ist m/n. 2.Die Wkeit, dass k Blle auf einen bestimmten Korb fallen ist, Lemma Werden m=n Blle zufllig in n Krbe geworfen. Dann gilt: 1.Die Wkeit, dass ein (bestimmter) Korb leer bleibt, ist konstant (konvergiert gegen 1/e). Die erwartete Anzahl leerer Krbe konvergiert gegen n/e 2.Die Wkeit, dass mehr als k ln n/ln ln n Blle auf einen bestimmten Korb fallen, ist hchstens O(n -c ) fr konstante k und c.

Folie 13

HEINZ NIXDORF INSTITUT Universitt Paderborn EIM Institut fr Informatik 13 Algorithm. Grundlagen des Internets 28. Juli 2003 Christian Schindelhauer Blle und Krbe Lemma Werden m= k n log n Blle zufllig in n Krbe geworfen (fr geeignete Konstante k). Dann gilt: 1.Die Wkeit, dass mehr als c 1 log n Blle auf einen Korb fallen ist hchstens O(n -c ) 2.Die Wkeit, dass ein Korb leer bleibt ist hchstens O(n -c ) Beweis: bungsaufgabe!

Folie 14

HEINZ NIXDORF INSTITUT Universitt Paderborn EIM Institut fr Informatik 14 Algorithm. Grundlagen des Internets 28. Juli 2003 Christian Schindelhauer Familien von Hash-Funktionen oFr jede Hash-Funktion existiert eine Worst-Case-Eingabe Daher betrachtet man grundstzlich Familien von Hash- Funktionen Genauso definieren wir Familie von Ranged-Hash-Funktionen fr geg. Views und Caches oWir gehen im folgenden davon aus, dass die Hash-Funktion sich verhlt wie ein perfektes Zufallsereignis Gleichwahrscheinlich Unabhngig oWerden die Elemente wie Blle in Krbe verteilt.

Folie 15

HEINZ NIXDORF INSTITUT Universitt Paderborn EIM Institut fr Informatik 15 Algorithm. Grundlagen des Internets 28. Juli 2003 Christian Schindelhauer Konsistentes Hashing C: Anzahl aller Caches B C/t: Mindestanzahl Caches pro View ist C/t V/C (Anzahl Views/Anzahl Caches)konstant I= C (Anzahl Seiten = Anzahl Caches) Theorem Es gibt eine Familie von ranged-Hash-Funktionen F mit den folgenden Eigenschaften 1.Jede Funktion f F ist monoton 2.Balance: Fr jeden View gilt 3.Spread: Fr jede Seite i ist 4.Load: Fr jeden Cache b ist

Folie 16

HEINZ NIXDORF INSTITUT Universitt Paderborn EIM Institut fr Informatik 16 Algorithm. Grundlagen des Internets 28. Juli 2003 Christian Schindelhauer Die Konstruktion o2 Hash-Funktionen auf das reelle Intervall [0,1] r B (b,j): fr Cache b und Zahl j {1,.., log C} log C Kopien des Caches b zufllig auf [0,1] ab r I (i): bildet Web-Seite i zufllig auf Intervall [0,1] ab of V (i) := Cache b V, der fr ein j den Abstand |r B (b,j)-r I (i)| minimiert. 0 1 Webseiten Caches View 2 View 1

Folie 17

HEINZ NIXDORF INSTITUT Universitt Paderborn EIM Institut fr Informatik 17 Algorithm. Grundlagen des Internets 28. Juli 2003 Christian Schindelhauer 1. Monotonie f V (i) := Cache b V, der fr ein j den Abstand |r B (b,j)-r I (i)| minimiert. Beobachtung: Blaues Intervall sowohl in V 2 als auch in V 1 leer! 0 1 Webseiten Caches View 2 View 1

Folie 18

HEINZ NIXDORF INSTITUT Universitt Paderborn EIM Institut fr Informatik 18 Algorithm. Grundlagen des Internets 28. Juli 2003 Christian Schindelhauer 2. Balance Balance: Fr jeden View gilt Whle festen View und eine Web-Seite i Wende nun die Hash-Funktionen r B (b,j) und r I (i) an. Unter der Annahme, dass diese sich wie zufllige Abbildungen verhalten, wird jeder Cache mit der gleichen Wahrscheinlichkeit ausgewhlt. 0 1 Webseiten View

Folie 19

HEINZ NIXDORF INSTITUT Universitt Paderborn EIM Institut fr Informatik 19 Algorithm. Grundlagen des Internets 28. Juli 2003 Christian Schindelhauer 3. Spread (I) Die Verbreitung (i) (spread) einer Seite i ist die Gesamtanzahl aller notwendigen Kopien (ber alle Views) C: Anzahl aller Caches B C/t: Mindestanzahl Caches pro View ist C/t V/C (Anzahl Views/Anzahl Caches)konstant I= C (Anzahl Seiten = Anzahl Caches) Spread: Fr jede Seite i ist Beweis Betrachte Intervalle der Lnge t/C 0 1 t/C 2t/C

Folie 20

HEINZ NIXDORF INSTITUT Universitt Paderborn EIM Institut fr Informatik 20 Algorithm. Grundlagen des Internets 28. Juli 2003 Christian Schindelhauer 3. Spread (II) C: Anzahl aller Caches B C/t: Mindestanzahl Caches pro View ist C/t V/C (Anzahl Views/Anzahl Caches)konstant I= C (Anzahl Seiten = Anzahl Caches) Beweis: Betrachte Intervalle der Lnge t/C Caches insgesamt: C log C zufllig verteilt ber C/t Intervalle O(n t log n) Bllen in n Krbe mit n = C/t Mit Wkeit 1-n -(1) sind hchstens O(t log C) Caches in jedem Intervall # Caches in benachbarten Intervallen von O(t log C) 0 1 t/C 2t/C Caches (alle Views)

Folie 21

HEINZ NIXDORF INSTITUT Universitt Paderborn EIM Institut fr Informatik 21 Algorithm. Grundlagen des Internets 28. Juli 2003 Christian Schindelhauer 3. Spread (III) C: Anzahl aller Caches B C/t: Mindestanzahl Caches pro View ist C/t V/C (Anzahl Views/Anzahl Caches)konstant I= C (Anzahl Seiten = Anzahl Caches) Beweis: Betrachte Intervalle der Lnge t/C Cache in einem View: C/t log C zufllig verteilt ber C/t Intervalle O(n log n) Bllen in n Krbe mit n = C/t Mit Wkeit 1-n -(1) ist mindestens ein Cache in einem Intervall In der Nhe von ist in jedem View ein Cache 0 1 t/C 2t/C View V

Folie 22

HEINZ NIXDORF INSTITUT Universitt Paderborn EIM Institut fr Informatik 22 Algorithm. Grundlagen des Internets 28. Juli 2003 Christian Schindelhauer 3. Spread (IV) Beweis: Betrachte Intervalle der Lnge t/C Mit Wkeit 1-n -(1) ist mindestens ein Cache in einem Intervall Also wird die Webseite i immer lokal gespeichert D.h. in ihrem Intervall oder im Nachbarintervall gespeichert Mit Wkeit 1-n -(1) sind hchstens O(t log C) Caches in jedem Intervall Obere Schranke fr Verbreitung: O(t log C) In der Nhe von ist in jedem View ein Cache 0 1 t/C 2t/C View 2 View 1

Folie 23

HEINZ NIXDORF INSTITUT Universitt Paderborn EIM Institut fr Informatik 23 Algorithm. Grundlagen des Internets 28. Juli 2003 Christian Schindelhauer 4. Load (I) oDie Last (b) (load) eines Caches b ist die Gesamtanzahl aller notwendigen Kopien (ber alle Views) C: Anzahl aller Caches B C/t: Mindestanzahl Caches pro View ist C/t V/C (Anzahl Views/Anzahl Caches)konstant I= C (Anzahl Seiten = Anzahl Caches) oLoad: Fr jeden Cache b ist oBeweis

Folie 24

HEINZ NIXDORF INSTITUT Universitt Paderborn EIM Institut fr Informatik 24 Algorithm. Grundlagen des Internets 28. Juli 2003 Christian Schindelhauer 4. Load (II) Beweis Betrachte Intervalle der Lnge t/C Mit Wkeit 1-n -(1) ist fr jeden View mindestens ein Cache in jedem Intervall V/C (Anzahl Views/Anzahl Caches)konstant I= C (Anzahl Seiten = Anzahl Caches) Web-Seiten insgesamt: C log C zufllig verteilt ber C/t Intervalle O(n t log n) Bllen in n Krbe mit n = C/t Mit pol. Wkeit sind hchstens O(t log C) Web-Seiten in jedem Intervall 0 1 t/C 2t/C View V 0 1 t/C 2t/C

Folie 25

HEINZ NIXDORF INSTITUT Universitt Paderborn EIM Institut fr Informatik 25 Algorithm. Grundlagen des Internets 28. Juli 2003 Christian Schindelhauer 4. Load (III) Beweis Mit Wkeit 1-n -(1) ist fr jeden View mindestens ein Cache in jedem Intervall Also wird die Webseite i immer lokal gespeichert -D.h. in ihrem Intervall oder im Nachbarintervall gespeichert Mit Wkeit 1-n -(1) sind hchstens O(t log C) Web-Seiten in jedem Intervall Jeder Cache hat hchstens O(t log C) Web-Seiten 0 1 t/C 2t/C View 2 View 1

Folie 26

HEINZ NIXDORF INSTITUT Universitt Paderborn EIM Institut fr Informatik 26 Algorithm. Grundlagen des Internets 28. Juli 2003 Christian Schindelhauer Peer-to-peer Netzwerke oPeer-to-peer Netzwerke sind verteilte Systeme ohne zentrale Kontrolle oder hierarchische Strukturen mit gleicher Software mit gro er D ynamik, d.h. Knoten erscheinen und verschwinden mit vielen Knoten mit geringer Netzwerkinform. oNetzwerkstruktur wie Internet vollst ndiger Graph nur Unicast (kein Broadcast) oHauptanwendung: Name-Lookup, d.h. verteiltes W rterbuch oLsung: konsistentes Hashing (mit nur einem View) Internet Knoten erscheint Knoten verschwindet

Folie 27

HEINZ NIXDORF INSTITUT Universitt Paderborn EIM Institut fr Informatik 27 Algorithm. Grundlagen des Internets 28. Juli 2003 Christian Schindelhauer Anwendungen Peer-to-peer Netzwerke oVerteiltes Caching z.B. Web-Caching ohne zentrale Kontrolle speichereffizientes Spiegeln im Internet oVerteiltes Plattenmanagement (Raid-Systeme) Statt einer Festplatte werden Daten auf verschiedene Festplatten verteilt Vorteil: Geschwindigkeit durch parallelen Zugriff oVerteilte Indizierung fr Napster/Gnutella File-Sharing Systeme Vorteil kein zentraler Server oDer Internet-Supercomputer Koordinierung einer Vielzahl (10 >5 ) per Internet verbundenen Rechnern Verteilung der Teilaufgaben durch konsistentes Hashing

Folie 28

HEINZ NIXDORF INSTITUT Universitt Paderborn EIM Institut fr Informatik 28 Algorithm. Grundlagen des Internets 28. Juli 2003 Christian Schindelhauer Konsistentes Hashing n: Anzahl der Knoten im P2P-Netzwerk k: Anzahl der Schl ssel Theorem Es gibt ein konsistentes Hashing f r ein Peer-to-peer-Netzwerk mit den folgenden Eigenschaften 1.Balance&Load: Mit pol. Wkeit (1-n -c ) werden in jedem Knoten h chstens O((k/n) log n) Schl ssel gespeichert 2.Spread: Jeder Schl ssel wird auf genau einem Knoten gespeichert. 3.Dynamik: Tritt ein neuer Knoten bei oder verl sst ein Knoten das Netzwerk mssen m it pol. Wkeit h chstens O((k/n) log n) Schlssel bewegt werden. Beweis Verwende konsistentes Web-Caching mit nur einem View und nur einer Cache-Kopie

Folie 29

HEINZ NIXDORF INSTITUT Universitt Paderborn EIM Institut fr Informatik 29 Algorithm. Grundlagen des Internets 28. Juli 2003 Christian Schindelhauer Verteiltes Konsistentes Hashing oProblem: Ranged-Hash-Funktion ben tigt zentrale Instanz, um Schlssel zu verteilen Gesucht: verteilte Datenstruktur ohne zentrale Instanz Es reicht, nur einen Knoten des Netzwerks zu kenne. oLsungen: DNS,Freenet, Ohaha, Globe system oLsungen mit konsistenten Hashing: Ocean store PAST,Pastry, Tapestry CAN Chord: A Scalable Peer-to peer Lookup Service for Internet Applications, Stoica, Morris, Karger Kaashoek, Balakrishnan, SIGCOMM01 wird hier besprochen

Folie 30

HEINZ NIXDORF INSTITUT Universitt Paderborn EIM Institut fr Informatik 30 Algorithm. Grundlagen des Internets 28. Juli 2003 Christian Schindelhauer Der Aufbau von Chord on: Knotenanzahl, Knotenmenge V ok: Anzahl Schl ssel, Schlsselmenge K om: Hashwertlnge: m >> log max{K,N} o2 Hash-Funktionen bilden auf {0,..,2 m -1} ab r V (b): bildet Knoten/Cache b zuf llig auf {0,..,2 m -1} ab r K (i): bildet Schl ssel i zufllig auf {0,..,2 m -1} ab of V (i) := arg min b V (r B (b)-r I (i)) mod 2 m Schlssel r K (i) = 3i-2 mod 8 0 1 23 4 5 6 7 r V (b) = b+1 mod 8 2 3 5 2 0 6

Folie 31

HEINZ NIXDORF INSTITUT Universitt Paderborn EIM Institut fr Informatik 31 Algorithm. Grundlagen des Internets 28. Juli 2003 Christian Schindelhauer Die Datenstruktur von Chord oF r jeden Knoten b: successor: Nachfolger predecessor: Vorg nger Fr i {0,..m-1} Finger[i] := Der Knoten der dem Wert r V (b+2 i ) folgt oFr kleine i werden die Finger- Eintrge immer gleich Nur unterschiedliche Fingereintrge werden gespeichert Lemma Die Anzahl unterschiedlicher Finger- Eintrge fr Knoten b ist mit pol. Wkeit O(log n) 0 1 23 4 5 6 7 5 2 0 successor predecessor finger[0] finger[1] finger[2]

Folie 32

HEINZ NIXDORF INSTITUT Universitt Paderborn EIM Institut fr Informatik 32 Algorithm. Grundlagen des Internets 28. Juli 2003 Christian Schindelhauer Eigenschaften der Datenstruktur Lemma Der Abstand |r V (b.succ) - r V (b)| ist 1.Im Erwartungswert 2 m /n 2.Mit pol. Wahrscheinlichkeit hchstens O((2 m /n) log n) und 3.In einem Interall der Lnge w/n 2 m sind mit pol. Wkeit a)hchstens O(w) Knoten, falls w=(log n) b)hchstens O(w log n) Knoten, falls w=O(log n) Lemma Die Anzahl der Knoten, die einen Fingerzeiger auf Knoten b besitzen ist 1.im Erwartungswert O(log n) 2.mit pol. Wahrscheinlichkeit hchstens O(log 2 n)

Folie 33

HEINZ NIXDORF INSTITUT Universitt Paderborn EIM Institut fr Informatik 33 Algorithm. Grundlagen des Internets 28. Juli 2003 Christian Schindelhauer Suchen in Chord Theorem Die Schlsselsuche kann mit O(log n) Anfragen mit pol. Wkeit erfolgen, d.h. O(log n) Nachrichten fr Schlsseleinfgen/lschen oSuchalgorithmus fr Schlssel s: Abbruch(b,s): Knoten b,b=b.succ gefunden, mit r K (s) [r V (b),r V (b)| Hauptroutine: Starte mit irgendeinem Knoten b while not Abbruch(b,s) do for i=m downto 0 do if r K (s) [r V (b.finger[i]),r V (finger[i+1])] then b b.finger[i] fi od b s b.finger[m] b.finger[m-1] c xy

Folie 34

HEINZ NIXDORF INSTITUT Universitt Paderborn EIM Institut fr Informatik 34 Algorithm. Grundlagen des Internets 28. Juli 2003 Christian Schindelhauer Knotendynamik in Chord Theorem O(log 2 n) Nachrichten gengen mit pol. Wkeit, um Knoten aufzunehmen/zu entfernen Beweisidee (fr aufnehmen) Im Erwartungswert mssen hchstens O(log n) (Finger-)Zeiger aktualisiert werden. Diese zu suchen kostet jeweils O(log n) Der einzutragende Wert ist bekannt (also keine Suche notwendig) Fhrt zur Schranke Ist das Intervall |r V (b.succ) - r V (b)|, in das ein neuer Knoten eingefgt wird, gro, also z.B. (2 m /n) log n Dann gibt es O(log 2 n) Zeiger, Aber diese sind jeweils in Gruppen von O(log n) benachbart. Damit fallen nur O(log n) Suchen a Kosten O(log n) an Die Aktualisierung hat jeweils konstante Kosten

Folie 35

HEINZ NIXDORF INSTITUT Universitt Paderborn EIM Institut fr Informatik 35 Algorithm. Grundlagen des Internets 28. Juli 2003 Christian Schindelhauer Abschlu veranstaltung/Prfungen 1.ffentliche Prfung oam 07.08.2003, 14 Uhr in Raum F2.211 oZuhrer erwnscht 2.Abschlubesprechung oGrillplatz am Querweg sdlich B64 oGetrnke werden gestellt (Wnsche?-Teilnehmerzahl?) oEssen, Grill, Kohle, etc. bitte selbst organisieren 3.Prfungstermine oDo, 07.08.03, 14 Uhr - (nur mit Zuhrer) oMo, 11.08.03 (opt. Di 12.08.) oMo, 18.08.03 (opt. Di. 19.08.) oMo, 29.09.03 (opt. Di. 30.09) oMo, 06.10.03 (opt. Di. 06.10) oweitere Termine auf Anfrage

Folie 36

HEINZ NIXDORF INSTITUT Universitt Paderborn EIM Institut fr Informatik 36 Algorithm. Grundlagen des Internets 28. Juli 2003 Christian Schindelhauer Wie bereite ich mich auf die Pr fung vor? 1.Mglichst nicht alleine 2.bungsaufgaben durchrechnen (sind Prfungsstoff) 3.Skript durcharbeiten, mit eigenen Aufzeichnungen 4.Bei Fragen fragen: oKurze Verstndnisfrage, Tippfehler im Skript: oEMAIL an schindel oder kvolbert oGreren Problemen: oTermin vereinbaren fr Sprechstunde per EMail 5.Letzter Tipp: oPrfung selber mit Mitstudenten durchspielen oMinivortrge vorbereiten o(Ein Q ist ein X als auch ein U, wenn man... Dagegen ist ein P wie das W im R... Darberhinaus haben wir auch das Y kennengelernt..) 6.Allerletzter Tipp: oWeb-Seite mitverfolgen wegen Aktualisierungen des Skripts/Fragenkatalog 7.Viel Erfolg!