Uniwersytet w Białymstoku - Centralny System UwierzytelnianiaNie jesteś zalogowany | zaloguj się
katalog przedmiotów - pomoc

Przedmiot z dyscypliny dodatkowej

Informacje ogólne

Kod przedmiotu: 390-FS3-4PDD Kod Erasmus / ISCED: (brak danych) / (brak danych)
Nazwa przedmiotu: Przedmiot z dyscypliny dodatkowej
Jednostka: Wydział Fizyki
Grupy: studia doktoranckie 4 rok sem. zimowy 2021/2022
Punkty ECTS i inne: 2.00
zobacz reguły punktacji
Język prowadzenia: polski
Rodzaj przedmiotu:

obowiązkowe

Założenia (opisowo):

Przedstawienie granic możliwości obliczeniowych uniwersalnej maszyny Turinga.

Tryb prowadzenia przedmiotu:

w sali

Skrócony opis:

Maszyny Turinga - specyficzne realizacje, klasy złożoności obliczeniowej, wybrane algorytmy, modelowanie Monte Carlo, maszynowe wspomaganie konstrukcji hipotez. Techniczne aspekty prezentowane są w środowisku CAS (computer algebra system; z uwagi na swoją wyjątkową swobodną dostępność użyte zostanie środowisko wxMaxima).

Pełny opis:

Maszyny Turinga. Uniwersalna maszyna Turinga. Problem zatrzymania się, funkcje nieobliczalne. Goedla twierdzenie o niezupełności. Uniwersalne zbiory bramek. Język maxima. Badanie zadań formalnych i przestrzeni znaczeń (interpretacji) metodą dziel i rządź (np. kodowanie Huffmana i odgadywanie przez 20 pytań). Rekurencja a iteracja. Algorytmy arytmetyki w formie rekurencyjnej. Złożoność obliczeniowa problemów i jej konsekwencje. Imaginowany bilard jako przykład maszyny liczącej. Liczby pseudolosowe, symulacje modeli. Kompresja informacji i funkcje jednokierunkowe. Symulacja uniwersalnej maszyny Turinga i algorytmy zwane pracowitymi bobrami. Ezoteryczny język programowania fractran.

Literatura:

Z. Hannan, wxMaxima for Calculus I, II, internet.

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, Gödel. Życie i logika, CiS, 2003.

J.H. Conway, FRACTRAN - A Simple Universal Programming Language for Arithmetic, Open Problems Commun. Comput., str. 4–26. 1986.

Efekty uczenia się:

Student ma rozeznanie w praktycznych ograniczeniach maszynowych obliczeń niekwantowych i w zróżnicowanych sposobach realizacji zautomatyzowanego rachunku.

Metody i kryteria oceniania:

Egzamin w formie testu; obserwacja ciągła aktywności studenta na wykładzie.

Zajęcia w cyklu "Rok akademicki 2020/21" (zakończony)

Okres: 2020-10-01 - 2021-06-30
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Wykład, 30 godzin więcej informacji
Koordynatorzy: Edward Piotrowski
Prowadzący grup: Edward Piotrowski
Lista studentów: (nie masz dostępu)
Zaliczenie: Przedmiot - Egzamin
Wykład - Egzamin

Zajęcia w cyklu "Rok akademicki 2021/22" (w trakcie)

Okres: 2021-10-01 - 2022-06-30
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Wykład, 30 godzin więcej informacji
Koordynatorzy: Marek Kisielewski
Prowadzący grup: Marek Kisielewski
Lista studentów: (nie masz dostępu)
Zaliczenie: Przedmiot - Egzamin
Wykład - Egzamin
Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Uniwersytet w Białymstoku.