Oferta dydaktyczna Instytutu Informatyki

Poniższa lista przedstawia przedmioty, które są uczone w Instytucie Informatyki, niektóre z nich co roku, niektóre z mniejszą częstotliwością Każdy student Instytutu Informatyki studiuje wg indywidualnego toku studiów, wybierając (zgodnie z pewnymi zasadami) z tej listy swoje przedmioty.

Jeżeli zastanawiasz się nad studiami u nas, jeżeli chcesz wiedzieć, czy na Uniwersytecie można zostać inżynierem, jeżeli interesuje Cię 1000 zł stypendium miesięcznie - zapraszamy na naszą stronę główną

Matematyczne podstawy informatyki

Nazwa angielska (title in English): Mathematical Foundations of Computer Science
Prowadzący (lecturer): Antoni Kościelski
Liczba punktów (ECTS): 9
Liczba punktów 2007 (ECTS since 2007): 6
Rodzaj (type): zaawansowany
Rodzaj od 2007 (type since 2007): informatyczny.I2
Liczba godzin (hours in semester):
wykład:30
ćwiczenia:30
Egzamin (exam): tak
Możliwe zajęcia w języku angielskim (can be taught in English): nie
Przedmiot zostal uaktualniony na biezacy rok (updated): tak
Semestr (semester): zimowy

Wymagania (prerequisites)

Opis (description)

Z upływem czasu informatyka staje się coraz bardziej praktyczna. Ma to wpływ na programy studiów i odbije się na wykształceniu ogólnym. 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 których 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ęć matematyków. Wiele algorytmów powstało prawdopodobnie dlatego, że ich twórcy mieli bardzo dobre przygotowanie matematyczne. 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. Wyobrażenia te zostały sformalizowane przez Herbranda. Jednak twórcy Prologu byc moze korzystali z innych idei, takze zwiazanych 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 wczesnych badań prowadzonych przez matematyków.

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 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 pewnego fragmentu matematyki i historii informatyki związane z jego treścią.

Program (program)

  1. Formalizacja rachunku 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.

Literatura (references)

Jeżeli jesteś zainteresowany studiowaniem w naszym instytucie, zapraszamy na stronę poświęconą tegorocznej rekrutacji.

Nazwa użytkownika (user name):
Hasło (password):