Co umie policzyć komputer?

Opis

Komputerów używamy na co dzień, niemal się z nimi nie rozstajemy, a szacowana moc obliczeniowa 500 najszybszych superkomputerów na świecie w 2020 roku wyniosła ponad 10^18 FLOPS - to dużo obliczeń na sekundę.
Wydawałoby się, że przy tak ogromnej mocy obliczeniowej możemy policzyć co tylko chcemy i to w mgnieniu oka, ale czy faktycznie tak jest?

Większości osób pewnie obiły się o uszy takie wyrażenia jak "problem P vs NP" czy "problem stopu" - na tych warsztatach nie tylko wyjaśnimy sobie dokładniej skąd one się biorą i na czym polegają, ale zajrzymy w głąb króliczej nory i poznamy świat zarówno tego co się da jak i tego czego się nie da policzyć.

Plan Warsztatów

• formalne wprowadzenie Maszyny Turinga (w wersji deterministycznej i niedeterministycznej)
• problemy decyzyjne
• klasy złożoności, redukcje, i przykładowe problemy w P, NP, coNP, tw. Cooka-Levina
• rozstrzygalność problemów decyzyjnych - klasy R i RE, problem stopu i pokrewne, tw. Rice'a
• problemy obliczeniowe
• rachunek lambda i wpływ typów na obliczane funkcje

Wymagania

• podstawowe zrozumienie złożoności obliczeniowej, notacja dużego O
• podstawowa wiedza o językach formalnych i automatach
• umiejętność przeprowadzania i zrozumienia dowodów matematycznych

Kontakt

michalhorodecki2002+www@gmail.com

Uwaga: Rozwiązania należy wysyłać przez stronę warsztatów.