392245 Komplexitätstheorie (S) (SoSe 2014)
Inhalt, Kommentar
-
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!
Teilnahmevoraussetzungen, notwendige Vorkenntnisse
-
Grundlagen der Theoretischen Informatik bzw. eine Kenntnis von folgenden Themen: was ist eine Tuirngmaschine, was ist P und NP, was heisst NP-vollstaendig
Literaturangaben
-
Siehe http://www.cs.princeton.edu/theory/complexity/ inklusive einer online Version von Drafts der Kapitel.
Lehrende
Termine ( Kalendersicht )
| Rhythmus | Tag | Uhrzeit | Format / Ort | Zeitraum |
|---|
Fachzuordnungen
| Modul | Veranstaltung | Leistungen | |
|---|---|---|---|
| 23-MeWi-HM5 Praxis-Umgang mit Medien | Lehrveranstaltung I | benotete Prüfungsleistung
|
Studieninformation |
| Lehrveranstaltung II | Studienleistung
|
Studieninformation | |
| Lehrveranstaltung III | Studienleistung
|
Studieninformation | |
| Lehrveranstaltung IV | Studienleistung
|
Studieninformation | |
| 39-Inf-MIKE Modularisierter individueller Kompetenz-Erwerb (MiKE) | - | unbenotete Prüfungsleistung | Studieninformation |
| 39-M-Inf-MIKE Modularisierter individueller Kompetenz-Erwerb (MiKE) | - | unbenotete Prüfungsleistung | Studieninformation |
Die verbindlichen Modulbeschreibungen enthalten weitere Informationen, auch zu den "Leistungen" und ihren Anforderungen. Sind mehrere "Leistungsformen" möglich, entscheiden die jeweiligen Lehrenden darüber.
| Studiengang/-angebot | Gültigkeit | Variante | Untergliederung | Status | Sem. | LP | |
|---|---|---|---|---|---|---|---|
| Bioinformatik und Genomforschung / Bachelor | (Einschreibung bis SoSe 2011) | Individueller Ergänzungsber | Wahl | 4. 6. | 3 | unbenotet | |
| Bioinformatik und Genomforschung / Master | (Einschreibung bis SoSe 2012) | Individueller Ergänzungsb | Wahl | 2. | 3 | unbenotet | |
| Intelligente Systeme / Master | (Einschreibung bis SoSe 2012) | Individuelle Ergänzung | Wahl | 2. | 3 | unbenotet | |
| Kognitive Informatik / Bachelor | (Einschreibung bis SoSe 2011) | Individueller Ergänzungsb | Wahl | 4. 6. | 3 | unbenotet | |
| Medieninformatik und Gestaltung / Bachelor | (Einschreibung bis SoSe 2011) | Individueller Ergänzungs | Wahl | 4. 6. | 3 | unbenotet | |
| Medienwissenschaft, interdisziplinäre / Master | (Einschreibung bis SoSe 2014) | Hauptmodul 6 | Wahlpflicht | 3 | unbenotet | ||
| Naturwissenschaftliche Informatik / Bachelor | (Einschreibung bis SoSe 2011) | Individueller Ergänzungsbereic | Wahl | 4. 6. | 3 | unbenotet | |
| Naturwissenschaftliche Informatik / Master | (Einschreibung bis SoSe 2012) | Individuelle Ergänzung | Wahl | 2. | 3 | unbenotet |
Teilnahme am Seminar, Vortrag aufgrund eines Originalartikels und gute Folien/Ausarbeitung.
- registrierte Anzahl: 7
- Dies ist die Anzahl der Studierenden, die die Veranstaltung im Stundenplan gespeichert haben. In Klammern die Anzahl der über Gastaccounts angemeldeten Benutzer*innen.
- Adresse:
- SS2014_392245@ekvv.uni-bielefeld.de
- Lehrende, ihre Sekretariate sowie für die Pflege der Veranstaltungsdaten zuständige Personen können über diese Adresse E-Mails an die Veranstaltungsteilnehmer*innen verschicken. WICHTIG: Sie müssen verschickte E-Mails jeweils freischalten. Warten Sie die Freischaltungs-E-Mail ab und folgen Sie den darin enthaltenen Hinweisen.
- Falls die Belegnummer mehrfach im Semester verwendet wird können Sie die folgende alternative Verteileradresse nutzen, um die Teilnehmer*innen genau dieser Veranstaltung zu erreichen: VST_45073320@ekvv.uni-bielefeld.de
- Reichweite:
- 3 Studierende direkt per E-Mail erreichbar
- Hinweise:
- Weitere Hinweise zu den E-Mailverteilern
- Letzte Änderung Grunddaten/Lehrende:
- Freitag, 11. Dezember 2015
- Letzte Änderung Zeiten:
- Donnerstag, 12. Juni 2014
- Letzte Änderung Räume:
- Donnerstag, 12. Juni 2014
- Art(en) / SWS
- S / 2
- Einrichtung
- Technische Fakultät
- Fragen oder Korrekturen?
- Fragen oder Korrekturwünsche zu dieser Veranstaltung?
- Planungshilfen
- Terminüberschneidungen für diese Veranstaltung
- Link auf diese Veranstaltung
- Wenn Sie diese Veranstaltungsseite verlinken wollen, so können Sie einen der folgenden Links verwenden. Verwenden Sie nicht den Link, der Ihnen in Ihrem Webbrowser angezeigt wird!
- Der folgende Link verwendet die Veranstaltungs-ID und ist immer eindeutig:
- https://ekvv.uni-bielefeld.de/kvv_publ/publ/vd?id=45073320
- Seite zum Handy schicken
-
Klicken Sie hier, um den QR Code zu zeigen
Scannen Sie den QR-Code:
- ID
- 45073320
Zum Seitenanfang