(in Polish) Przedmiot z dyscypliny dodatkowej
General data
Course ID: | 390-FS3-4PDD |
Erasmus code / ISCED: | (unknown) / (unknown) |
Course title: | (unknown) |
Name in Polish: | Przedmiot z dyscypliny dodatkowej |
Organizational unit: | Faculty of Physics |
Course groups: | |
ECTS credit allocation (and other scores): |
(not available)
|
Language: | Polish |
Type of course: | obligatory courses |
Prerequisites (description): | Presentation of the calculation limits for the Turing universal machine. |
Mode: | (in Polish) w sali |
Short description: |
Turing's machines - specific realizations, complexity classes, selected algorithms, Monte Carlo modelling, machine support for hypothesis constructions. Technical aspects are presented in the computer algebra system's environment (due to its unique free availability the wxMaxima environment will be used). |
Full description: |
Turing machines. Turing's universal machine. Halting problem, incalculable functions. Goedel incompleteness theorem. Universal sets of gates. Maxima language. Examination of formal tasks and spaces of meanings (interpretations) by divide-and-conquer method (e.g. Huffman coding vs. guessing by 20 questions). Recursion and iteration. Arithmetic algorithms in recursive form. Computational complexity of problems and its consequences. Imaginary billiards as an example of a computing machine. Pseudo-random numbers, model simulations. Information compression and one-way functions. Turing's universal machine simulation and algorithms called busy beavers. Esoteric fractran programming language. |
Bibliography: |
Z. Hannan, wxMaxima for Calculus I, II, internet. R. P. Feynman, Feynman Lectures on Computation, Westview Press, 2000. D. Harel, Computers Ltd., Oxford University Press, 2000. J. L. Casti, W. DePauli, Gödel: A Life of Logic, Westview, 2001. J.H. Conway, FRACTRAN - A Simple Universal Programming Language for Arithmetic, Open Problems Commun. Comput., str. 4–26. 1986. |
Learning outcomes: |
The student has an understanding of the practical limitations of non-quantum computations and of the different ways of implementing automated calculations. |
Assessment methods and assessment criteria: |
Examination in the form of a test; continuous observation of the student's activity during the lecture. |
Copyright by University of Bialystok.