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 studiów. Treści bardziej abstrakcyjne są coraz częściej pomijane,
studenci nie zapoznają się z wieloma własnościami obliczalności.
Informatycy bardzo często korzystają z osięgnięć matematyków. Samo pojęcie
obliczalności zostało po raz pierwszy zdefiniowane przy okazji rozwiązywania
problemów dotyczących tzw. podstaw matematyki. Idea Prologu tkwiła już chyba w
pierwszych wyobrażeniach Goedla o obliczalności, które miały zostać
sformalizowane przez Herbranda. Twórcy Prologu byc może korzystali także z
innych idei, zwiazanych również z nazwiskiem Herbranda. Idea programowania
funkcjonalnego powstała prawdopodobnie w wyniku bardzo nieudanej próby
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 badań prowadzonych przez matematyków.
Pierwsza część wykładu ma przypomniec pojęcie sformalizowanego systemu
logicznego i pojęcie prawdy. Będzie to podstawa reszty wykładu. Dalej zostanie
przedstawione kilka klasycznych definicji obliczalności i podstawowe wyniki
ich autorów. Będziemy rozważać róż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 kwantyfikatorów. Metoda ta jest uogólnieniem znanej
metody zero-jedynkowej. Wykład miałby też charakter historyczny. Chciałbym
uzupełnić go o fakty z historii podstaw matematyki i informatyki.
**Program:**
1. Rachunek kwantyfikatorów.
2. Goedel: funkcje rekurencyjne, twierdzenie o niezupełności arytmetyki.
3. Lambda rachunek Churcha, teza Churcha, twierdzenie o nierozstrzygalności arytmetyki i rachunku kwantyfikatorów.
4. Główna 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ów
