В учебном пособии изложены различные подходы к формализации понятия алгоритма. В нем рассматриваются: интуитивное понятие вычислимой арифметической функции, теория рекурсивных функций, рекурсивные предикаты, происходит уточнение понятия алгоритма через математическую машину Тьюринга и другие машины, рекурсивные и рекурсивно перечислимые множества, алгоритмические проблемы, некоторые оценки сложности алгоритмов. Помимо теоретических и практических материалов, учебное пособие содержит задания для самостоятельной работы. Содержание учебного пособия соответствует Федеральному государственному образовательному стандарту высшего образования третьего поколения и методическим требованиям, предъявляемым к учебным изданиям. Учебное пособие предназначено для студентов высших учебных заведений, обучающихся по направлению "Педагогическое образование" профилей "Физика и информатика", "Технология и информатика", "Математика и информатика", "Информатика и математика", "Прикладная информатика". Может быть полезно широкому кругу читателей, интересующихся основами теории вычислимости
V uchebnom posobii izlozheny razlichnye podkhody k formalizatsii ponjatija algoritma. V nem rassmatrivajutsja: intuitivnoe ponjatie vychislimoj arifmeticheskoj funktsii, teorija rekursivnykh funktsij, rekursivnye predikaty, proiskhodit utochnenie ponjatija algoritma cherez matematicheskuju mashinu Tjuringa i drugie mashiny, rekursivnye i rekursivno perechislimye mnozhestva, algoritmicheskie problemy, nekotorye otsenki slozhnosti algoritmov. Pomimo teoreticheskikh i prakticheskikh materialov, uchebnoe posobie soderzhit zadanija dlja samostojatelnoj raboty. Soderzhanie uchebnogo posobija sootvetstvuet Federalnomu gosudarstvennomu obrazovatelnomu standartu vysshego obrazovanija tretego pokolenija i metodicheskim trebovanijam, predjavljaemym k uchebnym izdanijam. Uchebnoe posobie prednaznacheno dlja studentov vysshikh uchebnykh zavedenij, obuchajuschikhsja po napravleniju "Pedagogicheskoe obrazovanie" profilej "Fizika i informatika", "Tekhnologija i informatika", "Matematika i informatika", "Informatika i matematika", "Prikladnaja informatika". Mozhet byt polezno shirokomu krugu chitatelej, interesujuschikhsja osnovami teorii vychislimosti
