Теория  
алгориТмов

в.и. игошин

Москва 
ИНФРА-М 
2012

Учебное пособие

Рекомендовано 
УМО по образованию в области подготовки 
педагогических кадров в качестве учебного пособия 
для студентов высших учебных заведений, 
обучающихся по специальности 050201.65 — математика

УДК 512.8; 161.2(075.8)
ББК 22.12; 87.4я73
 
И269

Игошин В.И. 
Теория алгоритмов: Учеб. пособие. — М.: ИНФРА-М, 2012. — 
318 с. — (Высшее образование).

ISBN 978-5-16-005205-2
Подробно изложены три формализации понятия алгоритма — ма-
шины Тьюринга, рекурсивные функции и нормальные алгоритмы 
Маркова, доказана их эквивалентность. Рассмотрены основные тео-
ремы общей теории алгоритмов, теория разрешимых и перечислимых 
множеств, алгоритмически неразрешимые массовые проблемы, тео-
рия сложности вычислений и массовых проблем, алгоритмические 
проблемы математической логики и других разделов математики. 
Охарактеризованы взаимосвязи теории алгоритмов с компьютерами 
и информатикой.
Для студентов университетов, технических и педагогических вузов, 
обучающихся по специальностям «Математика», «Прикладная мате-
матика», «Математик-педагог», «Учитель математики» на уровнях ба-
калавриата, магистратуры, а также специалитета.

УДК 512.8; 161.2(075.8)
ББК 22.12; 87.4я73

И269

© Игошин В.И., 2012
ISBN 978-5-16-005205-2

s m n

§

4

p q
s
p ≈ ,
q ≈ ,
s ≈ ,

,
≈

,
,
≈ ,

,

,
,
,

p
q
s ≈
,

7

§
§

m, n
m, n

m > n >

m
n

m
nb
r
n > r

r
m, n
n

r 
m, n
n, r

n
r

n
r · b
r
r > r

r
n, r
r

r 
n, r
r , r

r
r

r
r · b
r
r > r

r
r , r
r

r 
r , r
r , r

r
r

rk−
rk− · bk
rk
rk− > rk

rk−
rk · bk
rk
rk > rk

n > r
> r
> ... > rk−
> rk > rk
≥

rk

k ∈ N
n ∈ N

8

m, n
n, r
r , r
r , r

rk− , rk−
rk− , rk
rk

m·n

9

y

y

·

y

·

10