AZ (algorytmika i złożoność obliczeniowa)JP (języki programowania i logika)
Opis przedmiotu:
Przedmiotem wykładu są te twierdzenia i metody logiki matematycznej i
informatyki teoretycznej, ktore mowią coś o naturze samej matematyki i
informatyki. Chodzi tu więc o twierdzenia takie jak twierdzenie Godla,
twierdzenie Chaitina, czy teza Turinga-Churcha na temat zasięgu metod
matematycznych, o dowodzenie nierozstrzygalności i niepodatności problemow
matematycznych, złożoność Kołmogorowa, o hipotezę P≠NP, czy może być ona
niezależna od aksjomatow teorii mnogości, i co to w praktyce znaczy?
Generalnie wykład poświęcony jest refleksji filozoficznej na temat matematyki
i informatyki na bazie twardych rezultatow matematycznych: co można rzec o
sensie tych dziedzin?
Wykład przeznaczony jest dla doktorantow, ambitnych studentow końcowych lat na
matematyce i informatyce, oraz bardzo ambitnych studentow lat początkowych. Z
jednej strony ma charakter przeglądowo-powtorzeniowy, bo powraca do tematow
znanych z innych wykładow -- jednak tematy te rozszerza i analizuje ich sens
na tle szerszej wiedzy. Z drugiej strony mniej obeznani z tą tematyką studenci
mogą potraktować wykład jako wprowadzający w dziedzinę najciekawszych
rezultatow matematyki o wydźwięku filozoficznym.
Do wykładu przewidziane są ćwiczenia, ktore w części będą sprawdzały biegłość
w rozwiązywaniu rutynowych zadań związanych z tematem (a więc pośrednio
rozumienie tematyki, a w części poświęcone będą technicznemu rozwinięciu
niektorych tematow.
Wkład obejmuje następujące tematy
1\. Maszyny Turinga -- rownoważność rożnych modeli
2\. Funkcje rekurencyjne, definiowanie klas problemow poprzez maszyny Turinga
i funkcje rekurencyjne
3\. Rożne definicje klasy NP
4\. Formalizacja matematyki, aksjomatyzacja, system ZFC, niezależność
twierdzeń od aksjomatow aksjomatow teorii mnogości
5\. Analiza dowodu twierdzenia Godla
6\. Czy hipoteza P≠NP da się udowodnić?
7\. Złożoność Kołmogorowa, Twierdzenia Chaitina.
8\. Teoria wnioskowania indukcyjnego Solomonoffa.
