Problemy decyzyjne w logice zima 2020/21
| Język wykładowy | Polski |
|---|---|
| Opiekun | Emanuel Kieroński |
| Liczba godzin | 30 (wyk.) 30 (ćw.) |
| Rodzaj | I2.T - teoria inf. |
| ECTS | 6 |
| Polecany dla I roku | Nie |
| Egzamin | Tak |
| Tagi | JP (języki programowania i logika) |
Opis przedmiotu:
Prace Churcha, Turing i Goedla z początków XX w. pokazały, że problem spełnialności (czy dana formuła ma model?) dla logiki pierwszego rzędu jest nierozstrzygalny. Wyniki te zapoczątkowały duży program badawczy, którego celem było ustalenie, które naturalne fragmenty logiki pierwszego rzędu są rozstrzygalne. Nieco później dodatkowym bodźcem dla tego programu stały się potencjalne zastosowania w informatyce (bazy danych, reprezentacja wiedzy, automatyczna weryfikacja programów i sprzętu, sztuczna inteligencja, itd.). Oczywiście, zwiększyły one też zainteresowanie badaczy dokładną złożonością obliczeniową problemu spełnialności w przypadku fragmentów rozstrzygalnych. Na wykładzie przedstawię szereg wyników dotyczących rozstrzygalności/nierozstrzygalności i złożoności obliczeniowej logik motywowanych teorią informatyki. W programie m.in.: logiki modalne, temporalne i deskrypcyjne, logiki z dwiema zmiennymi, fragmenty strzeżone, logika z unarną negacją. Wykład będzie oparty głównie na pracach opublikowanych w ciągu ostatnich dwudziestu kilku lat, choć opowiem oczywiście również o paru klasycznych wynikach, sięgając m.in. do prac Kurta Gödla. **Wymagania:** Logika dla informatyków, Zalecane: Języki formalne i złożoność obliczeniowa **W razie konieczności prowadzenia zajęć zdalnie**: wykłady i ćwiczenia będą odbywały się online przy użyciu wybranej platformy (np. Google Meets).Wykłady
Lista| Prowadzący | Termin zajęć | Limit | Zapisani | Kolejka |
|---|---|---|---|---|
|
Emanuel Kieroński
zdalna |
cz 12:00-14:00 (s. ) | 18 | 12 | 0 |
UWAGA! Wyższa liczba oznacza wyższy priorytet, po zapisaniu do grupy zostajemy usunięci z kolejek o niższym priorytecie.
Ćwiczenia
Lista| Prowadzący | Termin zajęć | Limit | Zapisani | Kolejka |
|---|---|---|---|---|
|
Emanuel Kieroński
zdalna |
cz 14:00-16:00 (s. ) | 18 | 12 | 0 |
UWAGA! Wyższa liczba oznacza wyższy priorytet, po zapisaniu do grupy zostajemy usunięci z kolejek o niższym priorytecie.
Konsultacje prowadzących:
| Imię i nazwisko | Pokój | Konsultacje |
|---|---|---|
| Emanuel Kieroński | 304 | środy 10-12 |