AZ (algorytmika i złożoność obliczeniowa)JP (języki programowania i logika)
Grupy efektów kształcenia
Podstawy informatyki i programowania
Opis przedmiotu:
Z upływem czasu informatyka staje się coraz bardziej praktyczna. Ma to wpływ
na programy studiow i odbije się na wykształceniu ogolnym. Treści bardziej
abstrakcyjne są coraz częściej pomijane. Studenci nie zapoznają się już z
wieloma, znanymi własnościami obliczalności. Być może nie wiedzą, że są
zadania, dla ktorych nie ma algorytmu optymalnego, a dowolny algorytm
rozwiązujący takie zadanie można ulepszyć, i to w zadanym stopniu. Fakt ten
nie ma chyba żadnego znaczenia praktycznego. Pozwala jednak lepiej rozumieć
obliczalność.
Informatycy bardzo często korzystają z osięgnięć matematykow. Wiele algorytmow
powstało prawdopodobnie dlatego, że ich tworcy mieli bardzo dobre
przygotowanie matematyczne. Samo pojęcie obliczalności zostało po raz pierwszy
zdefiniowane przy okazji rozwiązywania problemow dotyczących tzw. podstaw
matematyki. Idea Prologu tkwiła już chyba w pierwszych wyobrażeniach Goedla o
obliczalności. Wyobrażenia te zostały sformalizowane przez Herbranda. Jednak
tworcy Prologu byc moze korzystali z innych idei, takze zwiazanych z
nazwiskiem Herbranda. Idea programowania funkcjonalnego powstała
prawdopodobnie w wyniku bardzo nieudanej proby stworzenia podstawowej dla
matematyki teorii, konkurencyjnej w stosunku do teorii mnogości.
Celem wykładu jest przedstawienie klasycznej wiedzy o podstawowych pojęciach
informatycznych znanej z wczesnych badań prowadzonych przez matematykow.
Pierwsza część wykładu jest poświęcona przedstawieniu sformalizowanego systemu
logicznego i pojęciu prawdy. Będzie to podstawa reszty wykładu. Dalej zostanie
przedstawione kilka klasycznych definicji obliczalności i prace ich autorow.
Będziemy rozważać rożne problemy (zadania) odgrywające rolę w początkach
informatyki, zajmować się ich rozstrzygalnością i ewentualnie złożonością.
Twierdzenie Herbranda podaje metodę badania, czy dana formuła jest tautologią
rachunku kwantyfikatorow. Metoda ta jest uogolnieniem znanej metody zero-
jedynkowej. Wykład miałby też charakter historyczny. Chciałbym uzupełnić go o
fakty z historii pewnego fragmentu matematyki i historii informatyki związane
z jego treścią.
**Program:**
1. Formalizacja rachunku kwantyfikatorow.
2. Goedel: funkcje rekurencyjne, twierdzenie o niezupełności arytmetyki.
3. Lambda rachunek Churcha, teza Churcha, twierdzenie o nierozstrzygalności arytmetyki i rachunku kwantyfikatorow.
4. Głowna praca Turinga i maszyna Turinga.
5. Funkcje rekurencyjne według Herbranda i Goedla.
6. Twierdzenie Herbranda.
7. Ewentualnie: zastosowania funkcji rekurencyjnych: abstrakcyjna złożoność obliczeniowa
8. i rozstrzygalność teorii dodawania (arytmetyki Presburgera), a może i teorii mnożenia.
**Wymagania:** Logika dla informatyk ow
sem. letni 2023/24: piątki, godz. 12.30-13.30, pokój 311, a także konsultacje zdalne za pośrednictwem MSTeams, w piątki, godz. 19.15 - 19.30 i dłużej, jeżeli będą zainteresowani.
Zapraszam też na konsultacje zdalne lub w Instytucie w terminach uzgodnionych ze stosownym wyprzedzeniem np. pocztą elektroniczną.
