392245 Komplexitätstheorie (S) (SoSe 2014)
Contents, comment
-
Im Seminar geht es um einige Klassiker bzw. neuere Ergebnisse zu den Fragen P, NP, und was es sonst noch gibt. Zentral is dabei das Buch von Arora/Barak (siehe http://www.cs.princeton.edu/theory/complexity/), aus dem exemplarisch einige Themen bearbeitet werden sollen. Moegliche Themen sind etwa:
- Ladner's Theorem: es gibt Sprachen zwischen P und NP vollstaendig
- Satz von Savitch: was bewirkt Nichtdeterminismus bezogen auf die Platzkomplexitaet?
- Was ist die ploynomielle Hierarchie von Sprachen?
- Wieso ist es zwar schwer, ein Programm fuer Graphn Isomorphism zu schreiben, aber leicht, zu testen, ob es richtig ist?
- Algorithmus von Shor: Wie kann man mit Quantumcomputing effizient faktorisieren?
- Was sind die Implikationen des berühmten PCP-Theorems für NP-harte Probleme und deren Approximierbarkeit?
- Komplexität von EntscheidungsbäumenDie Themenvergabe findet in der ersten Vorlesungswoche statt, der Termin wird noch bekannt gegeben.
ACHTUNG: Auf Wunsch von Interessenten findet dieses Seminar nicht im WS13 statt, sondern wird erst im SS14 angeboten!
Requirements for participation, required level
-
Grundlagen der Theoretischen Informatik bzw. eine Kenntnis von folgenden Themen: was ist eine Tuirngmaschine, was ist P und NP, was heisst NP-vollstaendig
Bibliography
-
Siehe http://www.cs.princeton.edu/theory/complexity/ inklusive einer online Version von Drafts der Kapitel.
Teaching staff
Dates ( Calendar view )
| Frequency | Weekday | Time | Format / Place | Period | |
|---|---|---|---|---|---|
| weekly | Fr | 14-16 | X-E0-214 | 13.06.2014 |
Subject assignments
| Module | Course | Requirements | |
|---|---|---|---|
| 23-MeWi-HM5 Praxis-Umgang mit Medien | Lehrveranstaltung I | Graded examination
|
Student information |
| Lehrveranstaltung II | Study requirement
|
Student information | |
| Lehrveranstaltung III | Study requirement
|
Student information | |
| Lehrveranstaltung IV | Study requirement
|
Student information | |
| 39-Inf-MIKE Modularisierter individueller Kompetenz-Erwerb (MiKE) | - | Ungraded examination | Student information |
| 39-M-Inf-MIKE Modularisierter individueller Kompetenz-Erwerb (MiKE) | - | Ungraded examination | Student information |
The binding module descriptions contain further information, including specifications on the "types of assignments" students need to complete. In cases where a module description mentions more than one kind of assignment, the respective member of the teaching staff will decide which task(s) they assign the students.
| Degree programme/academic programme | Validity | Variant | Subdivision | Status | Semester | LP | |
|---|---|---|---|---|---|---|---|
| Bioinformatik und Genomforschung / Bachelor | (Enrollment until SoSe 2011) | Individueller Ergänzungsber | Wahl | 4. 6. | 3 | unbenotet | |
| Bioinformatik und Genomforschung / Master | (Enrollment until SoSe 2012) | Individueller Ergänzungsb | Wahl | 2. | 3 | unbenotet | |
| Intelligente Systeme / Master | (Enrollment until SoSe 2012) | Individuelle Ergänzung | Wahl | 2. | 3 | unbenotet | |
| Kognitive Informatik / Bachelor | (Enrollment until SoSe 2011) | Individueller Ergänzungsb | Wahl | 4. 6. | 3 | unbenotet | |
| Medieninformatik und Gestaltung / Bachelor | (Enrollment until SoSe 2011) | Individueller Ergänzungs | Wahl | 4. 6. | 3 | unbenotet | |
| Medienwissenschaft, interdisziplinäre / Master | (Enrollment until SoSe 2014) | Hauptmodul 6 | Wahlpflicht | 3 | unbenotet | ||
| Naturwissenschaftliche Informatik / Bachelor | (Enrollment until SoSe 2011) | Individueller Ergänzungsbereic | Wahl | 4. 6. | 3 | unbenotet | |
| Naturwissenschaftliche Informatik / Master | (Enrollment until SoSe 2012) | Individuelle Ergänzung | Wahl | 2. | 3 | unbenotet |
Teilnahme am Seminar, Vortrag aufgrund eines Originalartikels und gute Folien/Ausarbeitung.
- Address:
- SS2014_392245@ekvv.uni-bielefeld.de
- This address can be used by teaching staff, their secretary's offices as well as the individuals in charge of course data maintenance to send emails to the course participants. IMPORTANT: All sent emails must be activated. Wait for the activation email and follow the instructions given there.
- If the reference number is used for several courses in the course of the semester, use the following alternative address to reach the participants of exactly this: VST_45073320@ekvv.uni-bielefeld.de
- Notes:
- Additional notes on the electronic mailing lists
- Last update basic details/teaching staff:
- Friday, December 11, 2015
- Last update times:
- Thursday, June 12, 2014
- Last update rooms:
- Thursday, June 12, 2014
- Type(s) / SWS (hours per week per semester)
- seminar (S) / 2
- Department
- Faculty of Technology
- Questions or corrections?
- Questions or correction requests for this course?
- Planning support
- Clashing dates for this course
- Links to this course
- If you want to set links to this course page, please use one of the following links. Do not use the link shown in your browser!
- The following link includes the course ID and is always unique:
- https://ekvv.uni-bielefeld.de/kvv_publ/publ/vd?id=45073320
- Send page to mobile
-
Click to open QR code
Scan QR code:
- ID
- 45073320