University of Bialystok - Central Authentication System
Strona główna

(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) Basic information on ECTS credits allocation principles:
  • the annual hourly workload of the student’s work required to achieve the expected learning outcomes for a given stage is 1500-1800h, corresponding to 60 ECTS;
  • the student’s weekly hourly workload is 45 h;
  • 1 ECTS point corresponds to 25-30 hours of student work needed to achieve the assumed learning outcomes;
  • weekly student workload necessary to achieve the assumed learning outcomes allows to obtain 1.5 ECTS;
  • work required to pass the course, which has been assigned 3 ECTS, constitutes 10% of the semester student load.

view allocation of credits
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.

This course is not currently offered.
Course descriptions are protected by copyright.
Copyright by University of Bialystok.
ul. Świerkowa 20B, 15-328 Białystok tel: +48 85 745 70 00 (Centrala) https://uwb.edu.pl contact accessibility statement site map USOSweb 7.1.2.0-8 (2025-07-09)