Uniwersytet Warszawski - Centralny System Uwierzytelniania
Strona główna

Zaawansowane aspekty złożoności obliczeniowej

Informacje ogólne

Kod przedmiotu: 1000-2M24ZAZ
Kod Erasmus / ISCED: (brak danych) / (brak danych)
Nazwa przedmiotu: Zaawansowane aspekty złożoności obliczeniowej
Jednostka: Wydział Matematyki, Informatyki i Mechaniki
Grupy: Przedmioty obieralne dla informatyki
Punkty ECTS i inne: 6.00 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: (brak danych)
Założenia (lista przedmiotów):

Złożoność obliczeniowa 1000-218bZO

Skrócony opis:

Teoria złożoności klasyfikuje problemy obliczeniowe ze względu na ich trudność i tłumaczy, dlaczego niektóre problemy okazują się odporne na próby znalezienia dobrych algorytmów. Przedmiot ten jest kontynuacją przedmiotu „Złożoność obliczeniowa”. Poruszymy klasyczne tematy teorii złożoności, które nie zmieściły się na tamtym przedmiocie.

Pełny opis:

1) Hierarchia wielomianowa. Nie da się rozwiązać SAT w czasie liniowym i podliniowej pamięci.

2) Twierdzenia Karpa-Liptona i Meyera – hierarcha wielomianowa a niejednorodne obwody.

3) BPP a hierarchia wielomianowa.

4) Hierarchia wielomianowa a problemy zliczania. Twierdzenie Tody.

5) Dowody interaktywne – alternatywna definicja pamięci wielomianowej.

6) Bezpieczeństwo obliczeniowe, funkcje jednokierunkowe i generatory liczb pseudolosowych.

7) Podstawy obliczeń kwantowych.

8) Twierdzenie PCP i trudność aproksymacji.

9) Złożoność dowodowa.

10) Ekspandery i ich użycie w generatorach pseudolosowych.

11) Dowody naturalne.

12) Złożoność obliczeniowa a logika. Twierdzenia Fagina i Immermana-Vardiego.

Literatura:

• Ch. Papadimitriou, Złożoność obliczeniowa, WNT, Warszawa 2002.

• S. Arora, B. Barak, Computational Complexity: A Modern Approach, Cambridge University Press 2009 (dostępne on-line)

Efekty uczenia się:

Wiedza

Student pogłębia wiedzę o klasycznych zagadnieniach teorii złożoności. (K_W01)

Umiejętności

Student potrafi konstruować rozumowania matematyczne dotyczące klas złożoności obliczeniowej. (K_U01)

Student potrafi identyfikować przynależność i trudność wybranych problemów obliczeniowych w stosunku do ważnych klas złożoności, wykorzystując ich różne charakteryzacje. (K_U05)

Kompetencje

Student rozumie narzędzia matematyczne wypracowane we współczesnej teorii złożoności i potrafi z nich korzystać.

Metody i kryteria oceniania:

Egzamin ustny. Dodatkowo, możliwe podwyższenie oceny dzięki rozwiązaniu zadań gwiazdkowych. Każde zadanie warte jest 1 podzielone przez liczbę studentów, którzy prawidłowo je rozwiązali.

Dla doktorantów: obowiązkowe wzięcie udziału w rozwiązywaniu zadań gwiazdkowych, albo zapoznanie się z najnowszą literaturą.

Zajęcia w cyklu "Semestr letni 2024/25" (jeszcze nie rozpoczęty)

Okres: 2025-02-17 - 2025-06-08
Wybrany podział planu:
Przejdź do planu
Typ zajęć:
Ćwiczenia, 30 godzin więcej informacji
Wykład, 30 godzin więcej informacji
Koordynatorzy: Paweł Parys
Prowadzący grup: Paweł Parys
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Uniwersytet Warszawski.
Krakowskie Przedmieście 26/28
00-927 Warszawa
tel: +48 22 55 20 000 https://uw.edu.pl/
kontakt deklaracja dostępności USOSweb 7.0.3.0 (2024-03-22)