Nagroda Gödla

Informacje ogólne

Kod przedmiotu:	1000-2M14NG
Kod Erasmus / ISCED:	11.3 Kod klasyfikacyjny przedmiotu składa się z trzech do pięciu cyfr, przy czym trzy pierwsze oznaczają klasyfikację dziedziny wg. Listy kodów dziedzin obowiązującej w programie Socrates/Erasmus, czwarta (dotąd na ogół 0) – ewentualne uszczegółowienie informacji o dyscyplinie, piąta – stopień zaawansowania przedmiotu ustalony na podstawie roku studiów, dla którego przedmiot jest przeznaczony. / (0612) Database and network design and administration Kod ISCED - Międzynarodowa Standardowa Klasyfikacja Kształcenia (International Standard Classification of Education) została opracowana przez UNESCO.
Nazwa przedmiotu:	Nagroda Gödla
Jednostka:	Wydział Matematyki, Informatyki i Mechaniki
Grupy:	Przedmioty obieralne dla informatyki Przedmioty obieralne na studiach drugiego stopnia na kierunku bioinformatyka
Punkty ECTS i inne:	(brak) Podstawowe informacje o zasadach przyporządkowania punktów ECTS: roczny wymiar godzinowy nakładu pracy studenta konieczny do osiągnięcia zakładanych efektów uczenia się dla danego etapu studiów wynosi 1500-1800 h, co odpowiada 60 ECTS; tygodniowy wymiar godzinowy nakładu pracy studenta wynosi 45 h; 1 punkt ECTS odpowiada 25-30 godzinom pracy studenta potrzebnej do osiągnięcia zakładanych efektów uczenia się; tygodniowy nakład pracy studenta konieczny do osiągnięcia zakładanych efektów uczenia się pozwala uzyskać 1,5 ECTS; nakład pracy potrzebny do zaliczenia przedmiotu, któremu przypisano 3 ECTS, stanowi 10% semestralnego obciążenia studenta. 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 uczenia się:	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.