Funkcje obliczalne
Informacje ogólne
Kod przedmiotu: | 0600-FS1-3FO |
Kod Erasmus / ISCED: |
11.1
|
Nazwa przedmiotu: | Funkcje obliczalne |
Jednostka: | Instytut Matematyki. |
Grupy: | |
Punkty ECTS i inne: |
(brak)
|
Język prowadzenia: | polski |
Rodzaj przedmiotu: | fakultatywne |
Skrócony opis: |
Maszyny Turinga - specyficzne realizacje, klasy złożoności obliczeniowej, wybrane algorytmy, modelowanie Monte Carlo. |
Pełny opis: |
Maszyny Turinga. Uniwersalna maszyna Turinga. Problem zatrzymania się, funkcje nieobliczalne. Goedla twierdzenie o niezupełności. Ezoteryczny język programowania fractran. Uniwersalne zbiory bramek. Klasy złożoności. Język wxmaxima. Badanie funkcji ciągłych metodą dziel i rządź. Rekurencja, optymalizacja ogonowa, iteracja. Algorytmy arytmetyki w formie rekurencyjnej. Imaginowany bilard jako przykład maszyny liczącej. Liczby pseudolosowe, symulacje modeli. Kompresja informacji. Funkcje jednokierunkowe. Konstruujemy uniwersalną maszynę Turinga. Algorytmy zwane pracowitymi bobrami. |
Literatura: |
Z. Hannan, wxMaxima for Calculus I, II, internet. C. H. Papadimitriou, Złożoność obliczeniowa, Helion, 2012. R. P. Feynman, Wykłady o obliczeniach, Prószyński i S-ka, 2007. D. Harel, Komputery — spółka z o.o., Wyd. N.-T., 2002. J. L. Casti, W. DePauli, Goedel. Życie i logika, CiS, 2003. |
Efekty uczenia się: |
Student ma rozeznanie w zagadnieniach obliczalności. |
Metody i kryteria oceniania: |
Egzamin w formie testu; domowe prace rachunkowe/problemowe; prezentacje rozwiązań zadań na zajęciach; obserwacja ciągła aktywności studenta. |
Właścicielem praw autorskich jest Uniwersytet w Białymstoku.