Beweistechniken http://wwwagak.cs.uni-kl.de/home/lehre/beweistechniken/15-vorlesung Thu, 12 Oct 2017 16:33:22 +0200 Joomla! - Open Source Content Management en-gb wwwagak@informatik.uni-kl.de () Computational Biology I - SS 15 http://wwwagak.cs.uni-kl.de/home/lehre/bioinf1 http://wwwagak.cs.uni-kl.de/home/lehre/bioinf1 Computational Biology: Alignments and Sequencing (SS 15)

Biologists collect ever more data which we can only hope to evaluate using computers. In particular, there are huge databases of DNA and RNA resp. fragments thereof, which we model as strings. The sheer amount of data and size of individual records demands especially efficient algorithms if we want to obtain results in a timely fashion.

This course contains computer science methods for dealing with strings. This includes

  • computing similarities of strings,
    (suffix trees and their applications)
  • finding approximate matches and
    (pairwise and multiple alignments)
  • reconstructing texts from overlapping fragments.
    (partial digest and double digest methods, PQ-trees, shortest common superstrings)

We always bear in mind to keep complexities low.

It is a 4 ECTS entry-level master course with accompanying tutorials; find details in the official documents.

Registration

In order to participate in the exercise classes, you are required to register in the OLAT system.

Dates

Lectures and exercise sessions will be held throughout the reading period, that is from Apr 21st to Jul 21st. Individual sessions will take place weekly on

  • Lecture: Tuesdays, 10:00 - 11:30 in 48-654
  • Exercise Class (bi-weekly): Tuesdays, 13:45 - 15:15 in 48-654, starting on May 12th.

Note: There will be no lecture on June 9th and July 21st (new!). The exercise on July 21st has been moved to July 22nd, 15:30 in the usual room (new!).

Exercises

Exercises are organized by Robert.

There will be exercise sheets with problems relating to the current lecture material.

 {quickcat:43}

Lecture Notes

Here you can download the content of the electronic blackboard from class as pdf.

 {quickcat:44}

Exam

There will be oral exams at the end of the semester, please contact us in time to make an appointment. You need 40% of the achievable points in the exercises to be allowed to take the exam.

Suggested Reading

German lecture notes covering all course material are available in print; ask us for it!

Apart from the lecture notes, the following text books cover most of the course's content:

  • R. Durbin, S. Eddy, A. Krogh, G. Mitchison: Biological Sequence Analysis
    Cambridge University Press, 1998
  • D. Gusfield: Algorithms on Strings, Trees, and Sequences
    Cambridge University Press, 1997

Previous Iterations

Computational Biology I (WS 13/14)

]]>
r_muelle@cs.uni-kl.de (Robert Müller) Vorlesung Mon, 13 Apr 2015 09:28:05 +0200
Advanced Algorithmics (SS 15) http://wwwagak.cs.uni-kl.de/home/lehre/beweistechniken/15-vorlesung/111-advanced-algorithmics-15 http://wwwagak.cs.uni-kl.de/home/lehre/beweistechniken/15-vorlesung/111-advanced-algorithmics-15

Advanced Algorithmics (SS 15)

NP-hard problems are relevant in practical situations!

Complexity theory tells us that there are problems that seem to be inherently hard to solve. What can we do when faced which such a problem in practice? Over the decades, some useful techniques for tackling hard problems have emerged, for example

  • using heuristics to limit search spaces,
  • accepting wrong outputs with certain probability and
  • accepting suboptimal but still decent solutions.

We follow these approaches and develop theoretical foundations for solving hard problems sufficiently well and fast in practice.

This is an 8 ECTS advanced-level master course; find details in the official documents.

Dates

Lectures and exercise sessions will be held throughout the reading period, that is from April 20th to July 24th. Individual sessions will take place weekly on

  • Mondays, 10:00 - 11:30 in 48-654 (lecture),
  • Wednesdays, 10:00 - 11:30 in 48-654 (lecture) and
  • Fridays, 15:30 - 17:00 in 48-654 (exercises)

Note that we will not meet on public holidays, i.e. May 1st and May 25th. We will notify you about replacement dates and other exceptions on a case-by-case basis.

Exercises

There will be weekly exercise sheets with problems relating to the current lecture material. You can hand in your solutions for grading. We will discuss the exercise problems in weekly exercise sessions, provided sufficient participation. Your TA will be Raphael.

Participation is optional. Register via email to Raphael.

Material

WeekTranscripts*ExercisesHands-On
I L1, L2 Sheet 1 Sheet 1, Data
II L3, L4 Sheet 2 Sheet 2
III L5, L6, E1 Sheet 3
IV L7, L8, E2 Sheet 4+ Sheet 3
V L9, L10, E3 Sheet 5 Sheet 4
VI L11, E4 Sheet 6
VII L12, L13, E5 Sheet 7 Sheet 5
VIII L14, E6 Sheet 8
IX L15, L16, E7 Sheet 9
X L17, L18, E8 Sheet 10 Sheet 6
XI L19, L20, E9 Sheet 11
XII L21, L22, E10
XIII L23, E11
XIV E12, E13
* Login required; get credentials from Raphael.
+ Changed after first hand-out.

Find the Git repository used for collaboration on the hands-on sheets here. Please clone the repository and issue pull requests if you want to contribute.

Exams

There will be oral exams. Please contact Prof. Nebel towards the end of the lecture period to inquire about possible dates.

Suggested Reading

  • D. Hochbaum: Approximation Algorithms for NP-Hard Problems
    ISBN: 978-0-534-94968-6, available in our library (key text)
  • J. Hromkovič: Algorithmics for Hard Problems
    ISBN: 978-3-642-07909-2, available in our library (key text)
  • V. Vazirani: Approximation Algorithms
    ISBN: 978-3-540-65367-7, available in our library (key text)
  • R. Motwani, P. Raghavan: Randomized Algorithms
    ISBN: 978-0-521-47465-8, available in our library
  • J. Balcazar, J. Diaz, J. Gabarro: Structural Complexity
    ISBN: 978-3-540-58384-4 and 978-3-540-52079-5, available in our library (key text)
  • R. Niedermeier: Invitation to Fixed Parameter Algorithms
    ISBN: 978-0-198-56607-6, available in our library

Prior Iterations

Advanced Algorithmics (SS 13) ]]>
r_reitzi@cs.uni-kl.de (Raphael Reitzig) Vorlesung Fri, 10 Apr 2015 15:27:30 +0200
Advanced Algorithmics (SS 17) http://wwwagak.cs.uni-kl.de/home/lehre/advanced-algorithmics http://wwwagak.cs.uni-kl.de/home/lehre/advanced-algorithmics Advanced Algorithmics (SS 17)
NP-hard problems are relevant in practical situations!

Complexity theory tells us that there are problems that seem to be inherently hard to solve. What can we do when faced which such a problem in practice? Over the decades, some useful techniques for tackling hard problems have emerged, for example

  • using heuristics to limit search spaces,
  • accepting wrong outputs with certain probability and
  • accepting suboptimal but still decent solutions.

We follow these approaches and develop theoretical foundations for solving hard problems sufficiently well and fast in practice.

This is an 8 ECTS advanced-level master course; find details in the official documents.

Solid knowledge of elementary algorithms and mathematical maturity are assumed; an introductory course on complexity classes P and NP is helpful, even though we recap the main results in class.

Please register in OLAT for the course to receive email notifications about news and short-term announcements.

Dates

Lectures and exercise sessions will be held throughout the reading period, that is from April 18th to July 22th. We will have two weekly sessions of lectures and one exercise class.

  • Lectures: every Monday and Thursday, 15:30 - 17:00 in room 11-201
  • Exercise Class:  every Friday, 13:45 - 15:15 in room 48-453

Exercises

There will be exercise sheets with problems relating to the current lecture material. We will discuss the exercise problems in weekly exercise sessions. Your tutor will be Marvin Petersen.

{quickcat:48}

Exams

There will be oral exams. The exams will have to be in July, so please arrange for some time to prepare directly after the reading period.

Oral exams can only be taken after successful participation in the course. This includes reaching at least a 1/e fraction of the total points on all exercise sheets.

Lecture Notes

Slides and notes from the lectures will be available here.

{quickcat:47}

Lecture Videos

Recorded lectures are on youtube.

Suggested Reading

The lecture is self-contained and lecture notes will be available.

Further reading (might be subject to change)

  • J. Hromkovič: Algorithmics for Hard Problems
    ISBN: 978-3-642-07909-2, available in our library
  • J. Flum, M. Grohe: Parametrized Complexity Theory
    ISBN: 978-3-540-29952-3, available as pdf by our library
  • R. Niedermeier: Invitation to Fixed Parameter Algorithms
    ISBN: 978-0-198-56607-6, available in our library
  • M. Mitzenmachen, E. Upfal: Probability and Computing - Randomized Algorithms and Probabilistic Analysis
    ISBN: 978-0-521-83540-4
  • S. Arora, B. Barak: Computation Complexity - A Modern Approach
    ISBN: 978-0-521-42426-4, available in our library
  • D. Hochbaum: Approximation Algorithms for NP-Hard Problems
    ISBN: 978-0-534-94968-6, available in our library
  • V. Vazirani: Approximation Algorithms
    ISBN: 978-3-540-65367-7, available in our library

Prior Iterations

Advanced Algorithmics (SS 15)
Advanced Algorithmics (SS 13)

]]>
r_reitzi@cs.uni-kl.de (Raphael Reitzig) Vorlesung Fri, 10 Apr 2015 15:27:30 +0200
Computational Biology II - SS 14 http://wwwagak.cs.uni-kl.de/home/lehre/bioinf2 http://wwwagak.cs.uni-kl.de/home/lehre/bioinf2 Computational Biology: Signals, Phylogenetics and Structure Prediction (SS 14)

Biologists collect ever more data which we can only hope to evaluate using computers. In particular, there are huge databases of DNA and RNA resp. fragments thereof, which we model as strings. The sheer amount of data and size of individual records demands especially efficient algorithms if we want to obtain results in a timely fashion.

This course contains computer science methods for advanced, biologically motivated analysis of string-based data, in particular

  • identifying signals, patterns in strings of statistical significance,
    (log-likelihood test, hidden markov models)
  • reconstructing phylogenetic trees and
    (hierarchical clustering, tree metrics, perfect phylogenetics, quartett puzzling)
  • predicting folding structure of RNA.
    (minimum free energy secondary structures, stochastic context-free grammars)

We always bear in mind to keep complexities low.

It is a 4 ECTS entry-level master course with accompanying tutorials; find details in the official documents.

Registration

In order to participate in the exercise classes, you are required to register in the OLAT system.

Dates

Lectures and exercise sessions will be held throughout the reading period. Individual sessions will take place weekly on

  • Lecture: Tuesdays, 10:00 - 11:30 in 48-654
  • Exercise Class (biweekly): Fridays, 13:45 - 15:15 in 48-654
    first exercise class on 09.05.2014

Exercises

Exercises are organized by Sebastian.

{quickcat:27}

Lecture Notes

Here you can download the content of the electronic blackboard from class as pdf.

{quickcat:30}

Exam

There will be oral exams at the end of the semester, please contact us in time to make an appointment. You need at least 40% of the achievable points in the exercises to be allowed to take the exam.

Suggested Reading

German lecture notes covering all course material are available in print; ask us for it!

Apart from the lecture notes, the following text books cover most of the course's content:

  • R. Durbin, S. Eddy, A. Krogh, G. Mitchison: Biological Sequence Analysis
    Cambridge University Press, 1998
  • D. Gusfield: Algorithms on Strings, Trees, and Sequences
    Cambridge University Press, 1997

Previous Iterations

WS 12/13

]]>
wild@cs.uni-kl.de (Sebastian Wild) Vorlesung Mon, 10 Mar 2014 09:57:23 +0100
Algorithm Engineering (SS 14) http://wwwagak.cs.uni-kl.de/home/lehre/ae http://wwwagak.cs.uni-kl.de/home/lehre/ae Algorithm Engineering (SS 14)

For many problems, there are several algorithms to choose from. But how to tell which is the best for your application? Rough complexity estimates can be misleading: If constants hidden by the O-class are large, an O(n) algorithm might be much slower than an O(n log n) algorithm for any reasonable size n.

In this course, we study state of the art techniques for the analysis of algorithms for computing precise asymptotics of costs, including constant factors. We will exercise their use on practical algorithms and data structures.
Moreover, we will take additional characteristics of modern computers into account that greatly influence actual running time:

  • Memory hierarchies and
  • instruction pipelines.

Finally, we use our new knowledge on the performance of an algorithm to suggest possible optimizations, whose effects we quantify again using analysis techniques. That way, you will learn to engineer the best possible algorithm for solving your real world problem at hand.

This is an 8 ECTS advanced-level master course with accompanying tutorials; find details in the official documents.

Registration

In order to participate in the exercise classes, you are required to register in the OLAT system.

Dates

Lectures and exercise sessions will be held throughout the reading period. Individual sessions will take place weekly on

  • Lecture: Mondays and Wednesdays, 10:00 - 11:30 in 48-654
  • Exercise Class: Wednesdays, 15:30 - 17:15 in 48-654
    first exercise class on 30.04.2014!

Exercises

Exercises are organized by Sebastian.
Sheet 7 can be handed in until Tuesday, 10.06., 12am. as the Monday is a holiday.

{quickcat:29}

Lecture Notes

{quickcat:31}

(Due to technical problems, the first lecture was only partially recorded. Therefore, we additionally provide the notes from the last iteration.)

Suggested Reading

Lecture notes covering all course material are available in print; ask us for it!

Apart from the lecture notes, the following text books cover parts of the course's content (and much more interesting stuff!):

  • R. Sedgewick, P. Flajolet: An Introduction to the Analysis of Algorithms
    Addison-Wesley Professional, 2nd edition, 2013
  • D. Knuth: The Art of Computer Programming: Fundamental Algorithms
    Addison-Wesley, 3rd edition, 1997
  • D. Knuth: The Art of Computer Programming: Searching and Sorting
    Addison-Wesley, 3rd edition, 1998
  • P. Flajolet, R. Sedgewick: Analytic Combinatorics
    Cambridge University Press, 2009

Previous Iterations

SS 12

]]>
wild@cs.uni-kl.de (Sebastian Wild) Vorlesung Thu, 05 Sep 2013 13:53:47 +0200
Übungen - Entwurf und Analyse von Algorithmen (WS 13/14) http://wwwagak.cs.uni-kl.de/home/lehre/beweistechniken/15-vorlesung/90-eaa1314-uebungen http://wwwagak.cs.uni-kl.de/home/lehre/beweistechniken/15-vorlesung/90-eaa1314-uebungen Übungen

Anmeldung
Prozedere
Übungstermine
Zusatzangebot
Übungsblätter
Zusatzmaterial

Anmeldung

Die Verwaltung der Übungsgruppen findet in OLAT statt.

Achtung: Eine Anmeldung (im richtigen Track) ist unbedingt nötig, wenn eine Zulassung erworben werden soll! Teilnehmer aus dem Track AI, die noch nicht die Beweistechniken bestanden haben, melden sich hierfür bitte zusätzlich an.

Hinweis: Melden Sie sich bitte auch an, wenn Sie nicht am Übungsbetrieb teilnehmen möchten, etwa weil Sie die Zulassung schon früher erworben haben; wir haben hierfür Pseudogruppen "Keine" vorgesehen. Dies erleichtert uns die Verwaltung eben dieser vorhandenen Zulassungen und Ihnen die Prüfung, um Missverständnisse und Fehler zu vermeiden.

Prozedere

Die Auswahl der Übungs- und Klausuraufgaben richtet sich nach dem belegten Modul. Hierfür teilen wir die Teilnehmerschaft in Track ε (Inf, Math) und Track AI (AI, WII) ein; Studenten aus anderen Studiengängen halten bitte mit uns Rücksprache. Bitte achten Sie unbedingt darauf, die richtigen Übungen zu besuchen!

Unser Ziel ist, möglichst viel individuelles Feedback zum Fähigkeitsstand zu bieten. Im Idealfall würden also alle Teilnehmer Lösungen zu so vielen Aufgaben wie möglich selbst aufschreiben und eine detaillierte Korrektur nach Klausurmaßstäben zurückbekommen. Leider können wir das personell nicht stemmen und müssen daher Kompromisse eingehen.

Es gibt Basis- und Aufbauaufgaben. Erstere zielen in der Regel darauf ab, grundlegende technische Fertigkeiten zu üben, wohingegen Letztere über Anwendung und Transfer des Gelernten dem tieferen Verständnis dienen sollen. Die Basisaufgaben werden einzelnabgegeben, die Aufbauaufgaben in Vierergruppen. Wir formalisieren das wie folgt:

  • Jeder Teilnehmer gibt von jedem Übungsblatt (genau) eine Basisaufgabe ab.
  • Die Mitglieder einer jeden Abgabegruppe (je vier Teilnehmer) geben unterschiedliche Basisaufgaben ab. Doppelabgaben werden nicht gewertet.
  • Jede Abgabegruppe gibt von jedem Blatt beliebig viele Aufbauaufgaben ab.
  • Von den Punkten auf Basisaufgaben müssen insgesamt 50% der Grundgesamtheit erreicht werden; diese ergibt sich aus der Summe der mittleren Basispunktzahl über alle Blätter. Das Mittel pro Blatt wird stets bei drei Punkten liegen und wir rechnen mit 13 Blättern, womit voraussichtlich 19 Punkte erreicht werden müssen.
    Es wird in der Zwischenklausur die Möglichkeit geben, bis zu fünf Basispunkte zu erwerben.
  • Von den Punkten für Aufbauaufgaben müssen 20% aller Aufbaupunkte (des jeweiligen Tracks) erreicht werden. Erreichte Punkte zählen natürlich für jedes Abgabegruppenmitglied gleichermaßen.

Die genauen Zulassungsvoraussetzungen finden Sie hier.

Termine

Lösungen zu den Basisaufgaben werden in einer zentralen Saalübung präsentiert. Diese findet ab der zweitenVorlesungswoche immer

Dienstags, 15:30 Uhr in 52-207

statt; bitte beachten Sie die Ausnahmen am 12., 19. und 26. November wie im KIS angegeben.

Achtung: am Dienstag, den 11.02.2014 findet um 15:30 Uhr in 48-208 eine weitere Saalübung statt, in der Aufgabe 3 der Zwischenklausur besprochen wird.

Die Termine und Orte der Kleingruppenübungen entnehmen Sie bitte den untenstehenden Tabellen. In diesen Stunden werden die Aufbauaufgaben besprochen.

Nr.TagZeitTutorRaum
ε1 Dienstag 11:45 Jan Bormann 46-268
ε2 Mittwoch 13:45 Jan Bormann 46-280
ε3 Donnerstag 11:45 Jan Bormann 56-230
ε5 Mittwoch 15:30 Johannes Freiermuth 48-462
ε6 Donnerstag 10:00 Lars Hüttenberger 13-370
ε7 Donnerstag 11:45 Lars Hüttenberger 13-305
ε8 Dienstag 11:45 Lisa Jöckel 48-379
ε9 Mittwoch 15:30 Lisa Jöckel 48-379
ε10 Mittwoch 13:45 David Wahl 57-165
ε11 Mittwoch 15:30 David Wahl 56-232
Nr.TagZeitTutorRaum
AI1 Mittwoch 08:15 Olaf Diether 48-379
AI2 Mittwoch 10:00 Olaf Diether 48-654
AI3 Dienstag 15:30 Markus Löwenstein 56-232
AI4 Donnerstag 11:45 Markus Löwenstein 56-232
AI5 Donnerstag 15:30 Elisabeth Neumann 48-654
AI6 Donnerstag 10:00 David Wahl 48-654

Zusatzangebot

Unsere Übungsleiter bieten in der Vorlesungszeit zu mehreren Terminen eine Lern- bzw. Arbeitsbetreuung an. Wenn also im Zuge der Vor- und Nachbereitung der Vorlesung oder beim Bearbeiten der Übungen Fragen aufkommen, finden Sie zu den folgenden Zeiten im jeweils ausgezeichneten Terminalraum des SCI Unterstützung:

  • Montag, 15:30 - 17:00 Uhr (48-231),
  • Dienstag, 13:45 - 15:15 Uhr (48-231),
  • Mittwoch, 17:15 - 18:45 Uhr (48-231) und
  • Donnerstag, 15:30 - 17:00 Uhr (48-211).

Eine Anmeldung ist nicht nötig; wer kommt, der kommt.

Nach Ende der Vorlesungszeit haben wir bis zur Abschlussklausur täglich von 10:00 - 17:00 Uhr den Raum 48-462 reserviert. Dort können Sie sich gemeinsam in Laufnähe zum Getränke- und Snackangebot der Fachschaft auf die Klausur vorbereiten.

In den 2 Wochen vor der Klausur (10.–21.02.) ist Sebastian Wild jeweils Mo, Mi und Fr von 10 bis 12 Uhr im Lernraum 48-462 für Sie da. Neben allgemeinen Fragen und Hinweisen hat jeder Termin ein Schwerpunktthema. Anhand einer ausgewählten Altklausur-Aufgabe besprechen wir u.a. die Richtlinien für unsere Korrektur.

Termin          Schwerpunktthema Musteraufgaben                                         
Mo 10.02. Asymptotiken Aufgabe 1, Aufgabe 2
Mi 12.02. Rekursionsgleichungen Aufgabe 1, Aufgabe 2
Fr 14.02. Beweisen oder Widerlegen? Aufgabe 1, Aufgabe 2
Mo 17.02. Komplexitätstheorie

Aufgabe 1, Aufgabe 2, Aufgabe 3

Mi 19.02. Algorithmenentwurf 1 Aufgabe 1, Aufgabe 2
Fr 21.02. Algorithmenentwurf 2 Aufgabe 1, Aufgabe 2

 

Übungsblätter

Die Übungsblätter werden in der Regel donnerstags in der Vorlesung herausgegeben – Reste liegen im SCI aus – und sind am jeweils übernächsten (Vorlesungszeit)Freitag fällig. Die genaue Abgabezeit entnehmen Sie bitte dem jeweiligen Übungsblatt.

Vorkenntnistest Track ε Track AI  
Blatt 1 Track ε Track AI  
Blatt 2 Track ε und AI *
Blatt 3 Track ε Track AI *
Blatt 4 Track ε Track AI *
Blatt 5 Track ε und AI *
Blatt 6 Track ε Track AI *
Blatt 7 Track ε Track AI  
Blatt 8 Track ε Track AI  
Blatt 9 Track ε und AI *
Blatt 10 Track ε Track AI
Blatt 11 Track ε Track AI
Blatt 12 Track ε und AI  
Blatt 13 Track ε Track AI

* Geändert seit Ausgabe in der Vorlesung.

Zusatzmaterial

  • Why Generating Functions Rule
    Ein kleiner Überblick darüber, wie und warum Erzeugendenfunktionen funktionieren. "Lücken" im formal-mathematischen Gefüge werden benannt und diese schließende Literatur angegeben.
  • Rechenregeln für Grenzwerte von Quotienten
    Zum asymptotischen Vergleich von Funktionen bestimmen wir gerne Grenzwerte von Quotienten von Funktionen. Hierfür gibt es einige "Rechenregeln", die zum Teil in unpräziser Form überliefert sind. Einige bieten wir hier in sauber bewiesener Form – soll heißen, bitte teilen Sie uns Fehler mit! – an.
  • Self-Deceit Sheet
    Dies ist eine in Anlehnung an das TCS Cheat Sheet benannte Sammlung von Fehlern, die frühere Teilnehmer in Klausuren gemacht haben. Sie soll nicht der humoristischen Erbauung auf Kosten Anderer dienen – unter Klausurbedingungen passieren die komischsten Dinge, das weiß jeder – sondern ein Werkzeug zur Klausurvorbereitung sein. Vielleicht ist doch der ein oder andere Eintrag zu finden, zu dem man sich auch hätte hinreißen lassen?
]]>
r_reitzi@cs.uni-kl.de (Raphael Reitzig) Vorlesung Mon, 26 Aug 2013 09:55:04 +0200
Übungen - Entwurf und Analyse von Algorithmen (WS 14/15) http://wwwagak.cs.uni-kl.de/home/lehre/eaa/eaa-uebungen http://wwwagak.cs.uni-kl.de/home/lehre/eaa/eaa-uebungen Übungen

Anmeldung
Prozedere
Übungstermine
Übungsblätter
Zusatzmaterial

Anmeldung

Flow Chart zur OLAT Anmeldung Flow Chart zur OLAT Anmeldung

Die Verwaltung der Übungsgruppen findet in OLAT statt.
Die Anmeldung ist von Mo 27.10., 16:30 Uhr bis Fr 31.10., 20:00 Uhr freigeschaltet.

Achtung: Eine Anmeldung (im richtigen Track) ist unbedingt nötig, wenn eine Zulassung erworben werden soll! Teilnehmer aus dem Track AI, die noch nicht die Beweistechniken bestanden haben, melden sich hierfür bitte zusätzlich an.

Hinweis: Melden Sie sich bitte auch an, wenn Sie nicht am Übungsbetrieb teilnehmen möchten, etwa weil Sie die Zulassung schon früher erworben haben; wir haben hierfür Pseudogruppen "Keine" vorgesehen. Dies erleichtert uns die Verwaltung eben dieser vorhandenen Zulassungen und Ihnen die Prüfung, um Missverständnisse und Fehler zu vermeiden.

Prozedere

Die Auswahl der Übungs- und Klausuraufgaben richtet sich nach dem belegten Modul. Hierfür teilen wir die Teilnehmerschaft in Track ε (Inf, Math) und Track AI (AI, WII) ein; Studenten aus anderen Studiengängen halten bitte mit uns Rücksprache. Bitte achten Sie unbedingt darauf, die richtigen Übungen zu besuchen!

Details zur Organisation von Übungen und den extraordinären Terminen in den ersten drei Wochen finden Sie in den Folien aus der ersten Vorlesung (für Ausnahmen und Zusatztermine siehe auch der Kalender im KIS (Vorlesung, Übung)).

Die genauen Zulassungsvoraussetzungen finden Sie hier.

Termine

Die Übungstermine sind: (Achtung: Die Termine im KIS sind nicht korrekt/aktuell.)

Gruppe Tutor Tag Zeit Raum
ε1 Jan Bormann Dienstag 08:15 46-654
ε2 Jan Bormann Dienstag 11:45 46-268
ε3 David Deininger Mittwoch 10:00 48-462
ε4 Johannes Freiermuth Mittwoch 13:45 48-280
ε5 Jakob Wenzel Donnerstag 08:15 48-379
ε6 David Deininger Donnerstag 10:00 13-370
ε7 Jakob Wenzel Donnerstag 11:45 13-305
ε8 Johannes Freiermuth Donnerstag 11:45 56-230
ε9 Timo Ußner Donnerstag 15:30 48-654
AI1 Florian Pelz Dienstag 10:00 48-654
AI2 Florian Pelz Mittwoch 08:15 48-654
AI3 Markus Löwenstein Mittwoch 13:45 57-165
AI4 Markus Löwenstein Mittwoch 15:30 48-379
AI5 Nico Himpele Donnerstag 11:45 56-232

Die ersten Übungen starten in KW 45, also ab dem 04. November.

Die Saalübung, in der Lösungen für die Basisaufgaben präsentiert werden, findet dienstags, 15:30 Uhr in Raum 52-207 statt. Der erste Termin ist am 11. November.

Übungsblätter

Die Übungsblätter werden donnerstags in der Vorlesung ausgegeben – Reste liegen im SCI aus – und sind am jeweils übernächsten (Vorlesungszeit-) Freitag fällig. Die genaue Abgabezeit entnehmen Sie bitte dem jeweiligen Übungsblatt.

Die Übungsblätter finden Sie hier (die alten Links sind leider tot).

Blatt 1 Track ε Track AI  
Blatt 2 alle Tracks  
Blatt 3 Track ε Track AI  
Blatt 4 alle Tracks  
Blatt 5 alle Tracks  
Blatt 6 Track ε Track AI  
Blatt 7 alle Tracks  
Blatt 8 Track ε Track AI  
Blatt 9 Track ε Track AI  
Blatt 10 alle Tracks  
Blatt 11 alle Tracks  
Blatt 12 alle Tracks  

* Geändert seit Ausgabe in der Vorlesung.

Die Übungsblätter zu Beweistechniken finden Sie auf der entsprechenden Seite.

Zusatzmaterial

  • Why Generating Functions Rule
    Ein kleiner Überblick darüber, wie und warum Erzeugendenfunktionen funktionieren. "Lücken" im formal-mathematischen Gefüge werden benannt und Literatur angegeben, in der diese adressiert werden.
  • Rechenregeln für Grenzwerte von Quotienten
    Zum asymptotischen Vergleich von Funktionen bestimmen wir gerne Grenzwerte von Quotienten von Funktionen. Hierfür gibt es einige "Rechenregeln", die zum Teil in unpräziser Form überliefert sind. Einige bieten wir hier in sauber bewiesener Form an. (Bitte teilen Sie uns etwaige Unsauberkeiten mit!)
  • Self-Deceit Sheet
    Dies ist eine in Anlehnung an das TCS Cheat Sheet benannte Sammlung von Fehlern, die in Klausuren gemacht worden sind. (Sie soll nicht der humoristischen Erbauung auf Kosten Anderer dienen, sondern ein Werkzeug zur Klausurvorbereitung sein.)
]]>
r_reitzi@cs.uni-kl.de (Raphael Reitzig) Vorlesung Mon, 26 Aug 2013 09:55:04 +0200
Prüfungen - Entwurf und Analyse von Algorithmen (WS 13/14) http://wwwagak.cs.uni-kl.de/home/lehre/beweistechniken/15-vorlesung/89-eaa1314-pruefungen http://wwwagak.cs.uni-kl.de/home/lehre/beweistechniken/15-vorlesung/89-eaa1314-pruefungen Prüfungen

Zwischenklausur
2. Zwischenklausur
Abschlussklausur
Nachklausur

Es wird eine schriftliche Abschlußklausur geben, die über das Bestehen bzw. die Abschlußnote des Moduls entscheidet. Um an dieser teilnehmen zu dürfen, muss die passende Zulassungsvoraussetzung erreicht worden sein.

  • Für das Modul "Entwurf und Analyse von Algorithmen" (INF-00-06-V-2) müssen
    • mindestens 50% der Basispunkte und
    • mindestens 20% der Aufbaupunke erlangt sowie
    • die Zwischenklausur bestanden werden.
  • Für das Modul "Entwurf und Analyse von Algorithmen für Angewandte Informatiker" (INF-00-06AI-M-2) müssen
    • mindestens 50% der Basispunkte und
    • mindestens 20% der Aufbaupunke erlangt sowie
    • das Teilmodul Beweistechniken als auch
    • die Zwischenklausur bestanden werden.
  • Für das Modul "Informatik für Mathematiker" (MAT-INF-10-M-4) müssen
    • mindestens 50% der Basispunkte und
    • mindestens 20% der Aufbaupunke erlangt werden.
Bitte beachten Sie, dass in Vorjahren erworbene Zulassungen übernommen werden können. Hierbei sind Beweistechniken und die Kombination aus Übungen und Zwischenklausur allerdings getrennt zu betrachten, letztere werden auch nur zusammen anerkannt.
Details zur Be- und Anrechnung der Übungsprozente finden Sie auf der Seite zu den Übungen.

Zwischenklausur

Die Zwischenklausur fand am Montag, den 16.12.2013 ab 17:30 Uhr in der Mensa statt.

Ergebnisse

Die Ergebnisse werden aus gegebenem Anlass nicht mehr gebündelt zur Verfügung gestellt. Sie sind in der Einsichtnahme bzw. zu gegebener Zeit im OLAT individuell einsehbar.

Einsichtnahme

Die Einsichtnahme fand am Montag, den 06.01.2014 von 16:00 bis 18:00 Uhr in 48-680 statt.

2. Zwischenklausur

Für Teilnehmer, die die Zwischenklausur noch für ihre Zulassung brauchten, boten wir eine zweite Zwischenklausur am Montag, den 24.02.2014 ab 13:30 Uhr in der Sporthalle an. Sie deckte den gleichen Stoff wie die erste Zwischenklausur ab.

Die Ergebnisse werden in OLAT (an gleicher Stelle wie die erste Zwischenklausur) eingetragen.

Abschlussklausur

Die Abschlussklausur fand am Montag, den 24.02.2014 ab 13:30 Uhr in der Sporthalle statt.

Dies sind die Ergebnisse nach der Einsichtnahme vom 06.03.2014:

Die Dateien sind nur aus dem Uninetz zugreifbar.

Abschlussklausur, die Zweite

Die zweite Abschlussklausur fand am 30.09.2014 ab 08:30 Uhr in 42-115 statt.

Ergebnisse

Dies sind die Ergebnisse vor der Einsichtnahme:

Die Dateien sind nur aus dem Uninetz zugreifbar.

Einsichtnahme

Die Einsichtnahme wird am Montag, den 10.11.2014 ab 17:00 Uhr in 48-654 (Einlass bis 18:00 Uhr) stattfinden.

]]>
r_reitzi@cs.uni-kl.de (Raphael Reitzig) Vorlesung Mon, 26 Aug 2013 09:52:07 +0200
Prüfungen - Entwurf und Analyse von Algorithmen (WS 14/15) http://wwwagak.cs.uni-kl.de/home/lehre/eaa/eaa-pruefungen http://wwwagak.cs.uni-kl.de/home/lehre/eaa/eaa-pruefungen Prüfungen

Zwischenklausur
Abschlussklausur
Nachklausur

Es wird eine schriftliche Abschlussklausur geben, die über das Bestehen bzw. die Abschlussnote des Moduls entscheidet. Um an dieser teilnehmen zu dürfen, muss die passende Zulassungsvoraussetzung erreicht worden sein.

Bitte beachten Sie, dass in Vorjahren erworbene Zulassungen übernommen werden können. Dabei gilt Beweistechniken als eigenständiger Teil, muss also nicht erneut belegt werden, auch wenn nur die EAA-Übungszulassung noch nicht erworben wurde.

Wer im Track ε die Zulassung erworben hat, muss die EAA-Übungen nach einem Studiengangwechsel in den Track AI nicht erneut belegen. Sollten aber die Mathematikveranstaltungen im alten Studiengang nicht vollständig abgeschlossen gewesen sein, muss die Beweistechnikzulassung nachgeholt werden.

Zwischenklausur

Die Zwischenklausur findet diesmal als "Grundlagentest" schon zu Beginn des Semesters am Montag 03.11.2014 um 19:00 Uhr in der Mensa statt (Dauer etwa 1h). Die Teilnahme am Vorkenntnistest ist verpflichtender Teil der Zulassungsvoraussetzungen zur Modulklausur, aber es wird keine Mindestpunktzahl für das Bestehen der Zwischenklausur geben.

Bitte melden sie sich bis 31.10.2014 im OLAT für die Zwischenklausur an.

Ziel des Vorkenntnistests ist es, frühzeitig einen Überblick über die Heterogenität der Hörerschaft zu bekommen, damit wir bei fehlenden Voraussetzungen reagieren können.

Zur Zwischenklausur sind keine Hilfsmittel zugelassen.

Die aggregierten Ergebnisse des Grundlagentests sind hier verfügbar (nur aus dem Uninetz erreichbar).

Zulassungsvoraussetzungen zur Abschlussklausur

  • Track ε:
    (Bachelor Informatik, Bachelor Mathematik)
    • mind. 17 Punkte aus Basisaufgaben (von 18 gesenkt),
    • mind. 20% aus Aufbauaufgaben,
    • Teilnahme an der Zwischenklausur (Grundlagentest).
      (nicht zwingend für Bachelor Mathematik)
  • Track AI:
    (Bachelor Informatik in den Anwendungen, Bachelor Wirtschaftsingenieurwesen: Fachrichtung Informatik)
    • mind. 17 Punkte aus Basisaufgaben (von 18 gesenkt),
    • mind. 20% aus Aufbauaufgaben,
    • Teilnahme an der Zwischenklausur (Grundlagentest),
    • erfolgreiche Teilnahme an Beweistechniken.

Abschlussklausur

Die schriftliche Abschlussklausur findet am Montag, den 02.03.2015 ab 13:30 Uhr in der Sporthalle statt.

Beachten Sie die oben aufgeführten Zulassungvoraussetzungen; ohne vollständige Zulassung können Sie an der Klausur nicht teilnehmen. Bitte überprüfen Sie rechtzeitig vor der Prüfung, ob Ihre Zulassung im OLAT korrekt erfasst ist (insbesondere, wenn Sie die Zulassung in einer früheren Iteration erworben haben).

Zugelassene Hilfsmittel sind

  • Das Buch (sowie Ausdrucke und Kopien davon),
  • eine Formelsammlung wie z.B. das TCS Cheat Sheet,
  • Ausdrucke des Zusatzdokuments zu Lemma Auspacken, sowie
  • selbstgeschriebenes, handschriftliches Material.
  • Die einzigen Druck- oder Kopiererzeugnisse, die außerdem zugelassen sind, sind Ausdrucke der Übungsblätter (aus diesem Semester) sowie Kopien der eigenen Übungsabgaben (aus diesem Semester).

Stellen Sie bitte sicher, dass Sie mit hinreichend zulässigem Schreibmaterial ausgerüstet sind. Korrigiert wird nur, was mit einem dokumentenechten Stift geschrieben ist. Das schließt zum Beispiel Kugelschreiber und Füllfederhalter mit nicht löschbarer Tinte ein; nicht dokumentenecht sind unter anderem Bleistifte und Füllfederhalter mit löschbarer Tinte. Sie müssen außerdem in blau oder schwarz schreiben; alle anderen Farben sind den Korrektoren vorbehalten. Weiterhin sind Korrekturmittel wie Tipp-Ex oder ähnliche unzulässig; darauf Geschriebenes wird behandelt, als sei es mit einem nicht dokumentenechten Stift geschrieben.

Bearbeitungsbögen stellen wir. Sie können sich weiteres Schmierpapier mitbringen, solange es unbedruckt ist.

Lernraum

In den zwei Wochen vor der Klausur (16.02. - 02.03.) sind die Seminarräume 48-462 und 48-438 ganztägig als Lernraum zur gemeinsamen Klausurvorbereitung für Sie reserviert.

Von den Übungsleitern wird in dieser Zeit jeweils Mo, Mi und Fr von 10:00 - 12:00 Uhr, sowie Do von 10:00 - 14:00 Uhr jemand anwesend sein, um auftretende Fragen zu beantworten.

Ergebnisse

Die anonymen Ergebnisse (mittels Klausurnummern) sind in OLAT (Ordner Klausurergebnisse auf der Startseite zum Kurs) und durch Aushang veröffentlicht.

Die Einsichtnahme in die Klausurkorrektur findet am Mittwoch, 25.03.2015 in Raum 48-680 statt. Start ist um

  • 14:00 Uhr für Informatiker,
  • 15:00 Uhr für angewandte Informatiker und
  • 15:30 Uhr für Mathematiker.

Bringen Sie bitte Ihren Studierendenausweis mit. Die Einsichtnahme zählt als Teil der Klausur, insbesondere gelten die gleichen Regeln für zugelassene Hilfsmittel.

Nachklausur

Die zweite Abschlussklausur findet am 29.09.2015 in 42-115 (Audimax) ab 08:30 Uhr statt. Die Regularien entsprechen denen der ersten Abschlussklausur. Stellen Sie bitte insbesondere sicher, dass Ihre Zulassung korrekt in OLAT erfasst ist.

]]>
r_reitzi@cs.uni-kl.de (Raphael Reitzig) Vorlesung Mon, 26 Aug 2013 09:52:07 +0200
Entwurf und Analyse von Algorithmen - Beweistechniken WS 13/14 http://wwwagak.cs.uni-kl.de/home/lehre/beweistechniken/15-vorlesung/87-beweistechniken1314 http://wwwagak.cs.uni-kl.de/home/lehre/beweistechniken/15-vorlesung/87-beweistechniken1314 Beweistechniken (WS 13/14)

Die Veranstaltung Beweistechniken ist ein Bestandteil des Moduls Entwurf und Analyse von Algorithmen für Angewandte Informatiker, die helfen soll, unterschiedliche Vorkenntnisse verschiedener Hörergruppen im Bereich der Mathematik, insbesondere dem Beweisen, anzugleichen.

Beweistechniken wird dieses Semester von Sebastian Wild betreut.

Übungsanmeldung

Teilnahme und Punkte werden in OLAT verwaltet. Falls Sie noch nicht angemeldet sind (auch mit alter Zulassung!), melden Sie sich bitte bei uns.

Termine

Es gibt zwei Vorlesungtermine, beide in der ersten Vorlesungswoche, in der die Inhalte vorgestellt werden.

  • Dienstag, 22.10.2012 08:15 - 09:45 Uhr in Raum 13-222
  • Freitag, 25.10.2012 08:15 - 09:45 Uhr in Raum 42-110

Die Inhalte finden Sie ebenfalls im Skript zur Vorlesung (Download unten).

Zur Besprechung der Übungsaufgaben gibt es ab dem 01.11.2012 eine wöchentliche Saalübung

  • freitags, 08:15 - 09:45 Uhr in Raum 42-110.
    ! Ersatztermin für 1.11. (Allerheiligen): Montag, 04.11. um 08:15 Uhr in 11-207.

Übungsblätter

Es wird voraussichtlich 6 Übungsblätter geben. Auf jedem dieser Blätter müssen 50% der Pflichtpunkte (dieses Blattes) erreicht werden, wobei aber nur die sinnvolle Bearbeitung der Aufgaben bepunktet wird. Durch die Bearbeitung freiwilliger Aufgaben können Sie zusätzliche Punkte bekommen.

{quickcat:20}

Frühere Iterationen

WS 12/13

]]>
wild@cs.uni-kl.de (Sebastian Wild) Vorlesung Tue, 20 Aug 2013 11:45:08 +0200