Serwisy internetowe Uniwersytetu Warszawskiego | USOSownia - uniwersyteckie forum USOSoweNie jesteś zalogowany | zaloguj się
katalog przedmiotów - pomoc

Nagroda Gödla

Informacje ogólne

Kod przedmiotu: 1000-2M14NG Kod Erasmus / ISCED: 11.3 / (0612) Database and network design and administration
Nazwa przedmiotu: Nagroda Gödla
Jednostka: Wydział Matematyki, Informatyki i Mechaniki
Grupy: Przedmioty monograficzne dla III - V roku informatyki
Przedmioty obieralne dla informatyki
Punkty ECTS i inne: (brak)
zobacz reguły punktacji
Język prowadzenia: angielski
Rodzaj przedmiotu:

monograficzne

Skrócony opis:

Nagroda Gödla jest przyznawana od 1993-go, raz do roku, za wybitne osiągnięcia w dziedzinie informatyki teoretycznej. Celem wykładu jest prezentacja rezultatów, za które została ona przyznana. Dokładniej przedstawione będzie około dziesięciu najciekawszych pomysłów. Głównym celem jest zrozumienie idei wyników, jednak szczegóły techniczne często też będą omawiane.

Pełny opis:

1. Wstęp, krótkie omówienie wszystkich wyników (1-2 wykłady)

2. Algorytmy wielomianowe w teorii liczb

a. wielomianowy algorytm AKS rozstrzygania pierwszości (1 wykład)

b. kwantowy algorytm faktoryzacji Shora (2 wykłady)

3. Teoria złożoności i okolice

a. dowody naturalne (2 wykłady)

b. produkt zygzakowy i równość SL = L (1 wykłady)

c. twierdzenie PCP (1 wykład)

d. optymalne ograniczenia dolne dla aproksymacji (1 wykład)

4. Algorytmika i bardziej praktyczne okolice

a. algorytm aproksymacyjny dla problemu komiwojażera na płaszczyźnie (1 wykład)

b. analiza smoothed (1 wykład)

c. algorytm AdaBoost w uczeniu maszynowym (1 wykład)

d. algorytmy strumieniowe (1 wykład)

e. algorytmiczna teoria gier (1 wykład)

Literatura:

Sanjeev Arora, Boaz Barak „Computational Complexity: A Modern Approach”: http://theory.cs.princeton.edu/complexity/

http://www.eatcs.org/index.php/goedel-prize

http://sigact.org/Prizes/Godel/

http://en.wikipedia.org/wiki/G%C3%B6del_Prize

Efekty kształcenia:

Zna aktualne dziedziny badań w informatyce teoretycznej. Umie określić główne pomysły prowadzące do przełomowych odkryć w tej dziedzinie.

Metody i kryteria oceniania:

Ocena końcowa na podstawie egzaminu ustnego

Przedmiot nie jest oferowany w żadnym z aktualnych cykli dydaktycznych.
Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Uniwersytet Warszawski.