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

Министерство науки и высшего образования Российской Федерации  
Федеральное государственное бюджетное  
образовательное учреждение высшего образования 
«Казанский национальный исследовательский 
технологический университет» 
 
 
 
 
 
 
 
Л. Т. Ягьяева, М. Ю. Валеев 
 
 
ТЕОРИЯ АЛГОРИТМОВ  
И ПРОГРАММ 
 
Учебное пособие 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Казань 
Издательство КНИТУ 
2019 

УДК 004.021(075) 
ББК 22я7

Я31

 
Печатается по решению редакционно-издательского совета  
Казанского национального исследовательского технологического университета 
 
Рецензенты: 
генеральный директор НПП «ГКС»  И. А. Юманкин 
главный метролог НИЦ «Инкомсистем»  Р. Р. Замалетдинов 
 
 

 
Я31 

Ягьяева Л. Т. 
Теория алгоритмов и программ : учебное пособие / 
Л. Т. Ягьяева, М. Ю. Валеев; Минобрнауки России, Казан. 
нац. исслед. технол. ун-т. – Казань : Изд-во КНИТУ, 2019. – 
116 с. 
 
ISBN 978-5-7882-2737-5

 
Рассмотрены основные положения теории информации и теории 
алгоритмов и программ, а также основы кодирования символьной информации. 
Представлены задания по методам сортировки и поиска.  
Предназначено для студентов института управления, автоматизации 
и информационных технологий, изучающих дисциплину «Теория 
алгоритмов и программ» для направления подготовки 09.03.01 «Инфор-
матика и вычислительная техника».  
Подготовлено на кафедре автоматизированных систем сбора и об-
работки информации. 
 

 
 
 

ISBN 978-5-7882-2737-5
© Ягьяева Л. Т., Валеев М. Ю., 2019
© Казанский национальный исследовательский 

технологический университет, 2019

 
 

УДК 004.021(075) 
ББК 22я7

ВВЕДЕНИЕ 
 
Данное учебное пособие предназначено для студентов, изучаю-
щих курс «Теория алгоритмов и программ» по направлению подго-
товки «Информатика и вычислительная техника».  
Предлагаемое пособие состоит из трех глав.  
В первой главе рассматриваются основные положения теории ин-
формации, исходные понятия информатики, формы представления ин-
формации, а также понятие информации в теории Шеннона, понятие 
энтропии, связь информации и алфавита.  
Вторая глава посвящена основным понятиям алгоритма, прави-
лам их построения и разбиению программы, рассмотрено понятие алго-
ритма как абстрактной машины.  
В третьей главе приведены основные понятия первой теоремы 
Шеннона и способы построения двоичных кодов. 
Представлены также практические задания по основным методам 
сортировки и поиска. Каждая глава содержит задачи для самостоятель-
ного решения и завершается списком контрольных вопросов.  
В пособие также включен глоссарий по основным понятиям дан-
ной дисциплины. 
 
 
 

Глава 1. ТЕОРИЯ ИНФОРМАЦИИ 
 
1.1. Основные положения 
 
Теория информации как самостоятельная дисциплина возникла 
для решения задачи обеспечения надежной и эффективной передачи 
информации от источника к приемнику независимо от помех. Форму-
лировка этой задачи имеет ряд уточнений: 
– «надежная» означает, что в процессе передачи не должно про-
исходить потери информации, т. е. приемник полностью, без искаже-
ний должен получить информацию, отправленную источником, 
– «эффективная» означает, что передача должна осуществляться 
наиболее быстрым способом, (поскольку время эксплуатации линии 
связи – экономический фактор, который требуется минимизировать); 
– помехи присутствуют в любой реальной линии связи;  
Таким образом, поставленная выше задача имеет четкую прак-
тическую направленность. Решение этой задачи ведется по двум 
направлениям, которые условно можно назвать техническим и математическим. 

Технический поиск связан с практической разработкой линий 
связи, в которых передача может идти с большой скоростью; с обеспечением 
защиты от помех или уменьшения их воздействия, созданием 
технических устройств, обеспечивающих быструю и надежную связь. 
В основе этих разработок лежат общие законы и принципы, которые 
применимы практически к любым видам связи. Эти законы и принципы 
определяют способы кодирования информации; условия надежной передачи 
информации, и вводятся величины, позволяющие количественно 
описывать информационные процессы. Именно эти методы  
и составляют содержательную основу теории информации. 
Теория информации тесно связана с математической теорией  
и основывается на теории случайных событий, для описания которых 
применяются понятия вероятность и энтропия. В рамках самой теории 
вводится понятие информация и устанавливается ее мера – бит.  
Теория информации используется в информатике, технике, психологии, 
биологии, физике, педагогике, лингвистике и т.д. Однако, как 
и любая иная математическая теория, теория информации применима 
для решения конкретных задач практики в той мере, в какой описывае-
мые материальные системы или процессы удовлетворяют исходным 
положениям теории.  

Математическое понятие информации связано с возможностью 
ее количественного измерения. При этом в теории информации исполь-
зуется энтропийный подход, когда количество информации в сообще-
нии определяется тем, насколько уменьшается неопределенность ис-
хода случайного события (например, появления конкретной буквы в не-
которой последовательности символов) после получения сообщения. 
Сообщение несет полную информацию о событии, если оно целиком 
снимает исходную неопределенность. В технических приложениях ис-
пользуется способ оценки количества информации, основанный на про-
стом подсчете числа знаков в сообщении – такой подход называется 
объемным. 
В общем случае эти две меры количества информации не совпа-
дают, в частности, в теории информации показывается, что энтропий-
ная мера не превышает числа двоичных символов (бит) в сообщении. 
Одинаковым же в обоих подходах оказывается то, что количественная 
мера информации не привязывается к ее семантической (т. е. смысло-
вой) основе. С бытовой точки зрения информация, лишенная смысла, 
лишена и какой-либо ценности для получателя. Однако устройство, 
предназначенное для передачи или хранения информации, оценить 
смысл передаваемого (или сохраняемого) не может (да и не должно) – 
в этом случае главной оказывается задача надежной передачи и хране-
ния информации независимо от ее семантической основы. 
Фазы обращения информации. Рассмотрим использование ин-
формации с целью принятия какого-либо решения или выработки 
управляющего воздействия. Можно выделить несколько фаз в цикле 
обращения информации. Пусть имеется какой-либо объект наблюде-
ния, который является также объектом управления (рис. 1.1), т. е. он 
является источником и потребителем информации. 
 

 

 
 
Рис. 1.1. Обращение информации в автоматической системе 

Можно выделить несколько фаз: 
1. Восприятие состоит в том, что формируется образ объекта, 
производится его опознание и оценка. При восприятии нужно отделить 
полезную информацию от шумов. В результате восприятия получается 
сигнал в форме, удобной для передачи или обработки. В фазу восприятия 
могут включаться операции подготовки информации, ее нормализации, 
квантования, кодирования, модуляции сигналов и построения 
моделей. 
2. Передача информации состоит в переносе ее на расстояние посредством 
каналов различной физической природы (механических, 
гидравлических, пневматических и т. п.). 
3. Обработка информации – это решение задач, связанных с преобразованием 
информации, независимо от их функционального назначения. 
ЭВМ обобщает и централизует функции обработки, имеющие 
отношение главным образом к моделям ситуаций и принятию решений 
при управлении. Из устройства обработки информация может выводиться 
или человеку, или непосредственно воздействовать на объект 
управления. Если есть человек, то необходима фаза представления информации. 

4. Представление информации заключается в демонстрации перед 
человеком условных изображений, содержащих качественные и количественные 
характеристики выходной информации с помощью соответствующих 
устройств, которые способны воздействовать на органы 
чувств человека: оптические, акустические и двигательные сигнализа-
торы (цифробуквенные, стрелочные и изобразительные индикаторы), 
цифровые и графические регистрирующие приборы с видимой записью, 
электроннолучевые трубки с экранами; табло и макеты с встроенными 
сигнальными и индикаторными элементами. После обработки 
информация воздействует на объект. 
5. Воздействие состоит в том, что сигналы, несущие информацию, 
производят регулирующие, управляющие или защитные действия, 
вызывают изменения в самом объекте. 
Информационные системы могут быть замкнутыми и разомкнутыми. 
Мы рассмотрели замкнутую систему. В разомкнутых системах 
информация передается только от источника к приемнику или потребителю 
без обратного воздействия.  
 
 

1.2. Исходные понятия информатики 
 
Начальные определения. Любая наука начинается со строгих 
определений. Определить какое-либо понятие – значит выразить его через 
другие понятия, уже определенные ранее.  
Рассмотрим сам термин «информация»: на бытовом уровне и во 
многих научных дисциплинах он ассоциируется с понятиями сведения, 
знания, данные, известие, сообщение, управление и др. Общим во всех 
перечисленных примерах является то, в них существенным и значимым 
для использования является содержательная сторона информации. Од-
нако оценка смысла и ценности одной и той же информации различ-
ными людьми будет различной; объективная количественная мера 
смысловой стороны информации отсутствует. Семантическая основа 
информации роли не играет, точнее, она принимается в виде атрибута 
(свойства, качества) информации, который не должен изменяться, а для 
этого следует обеспечить неизменность материального представления 
информации.  
Отделив информацию от ее семантической основы, получаем 
возможность построить определение информации и параллельно вве-
сти ее объективную количественную меру. Будет использован способ 
определения, который называется операционным и который состоит  
в описании метода измерения или нахождения значения определяемой 
величины. 
Информация – категория нематериальная. Следовательно, для 
существования и распространения в материальном мире она должна 
быть обязательно связана с какой-либо материальной основой – без нее 
информация не может проявиться, передаваться и сохраняться, напри-
мер, восприниматься и запоминаться нами. Введем определение: мате-
риальный объект или среда, которые служат для представления или 
передачи информации, называются материальным носителем. 
Материальным носителем информации может быть бумага, воз-
дух, лазерный диск, электромагнитное поле и пр. Хранение информа-
ции связано с некоторой характеристикой носителя, которая не меня-
ется с течением времени, например, намагниченные области поверхно-
сти диска или буква на бумаге. А передача информации – наоборот, свя-
зана с характеристикой, которая изменяется с течением времени, напри-
мер, 
амплитуда 
колебаний 
звуковой 
волны 
или 
напряжение  
в проводах. Другими словами, хранение информации связано с фикса-
цией состояния носителя, а распространение – с процессом, который 

протекает в носителе. Состояния и процессы могут иметь физическую, 
химическую, биологическую или иную основу – главное, что они ма-
териальны. 
Однако не с любым процессом можно связать информацию,  
в частности, стационарный процесс информацию не переносит (т. е. 
процесс с неизменными в течение времени характеристиками). Приме-
ром может служить постоянный электрический ток, ровное горение 
лампы, или равномерный гул – они содержат лишь ту информацию, что 
процесс идет, т. е. что-то функционирует. Иное дело, если будем лампу 
включать и выключать, т. е. изменять ее яркость, – чередованием вспы-
шек и пауз можно представить и передать информацию (например, по-
средством азбуки Морзе). Таким образом, для передачи необходим не-
стационарный процесс, т. е. процесс, характеристики которого могут 
изменяться, при этом информация связывается не с существованием 
процесса, а именно с изменением какой-либо его характеристики. 
Изменение характеристики носителя, которое используется для 
представления информации, называется сигналом, а значение этой ха-
рактеристики, отнесенное к некоторой шкале измерений, называется 
параметром сигнала. 
В табл. 1.1 приведены примеры процессов, используемых для пе-
редачи информации, и связанных с ними сигналов. 
Таблица 1.1 
Примеры процессов 

Способ передачи
Процесс
Параметры сигнала

Звук 
Звуковые волны 
Высота и громкость звука 

Радио, телевидение 
Радиоволны 
Частота, амплитуда или 
фаза радиоволны 

Изображение 
Световые волны 
Частота и амплитуда свето-
вых волн 

Телефон, компьютерная 
сеть 

Электрический ток 
Частота и амплитуда элек-
трических колебаний в ли-
нии связи

 
Однако одиночный сигнал не может содержать много информа-
ции. Поэтому для передачи информации используется ряд следующих 
друг за другом сигналов. Последовательность сигналов называется со-
общением. 

Информация от источника к приемнику передается в виде сооб-
щений. Можно сказать, что сообщение выступает в качестве материаль-
ной оболочки для представления информации при передаче. Следова-
тельно, сообщение служит переносчиком информации, а информация 
является содержанием сообщения. 
Соответствие между сообщением и содержащейся в нем инфор-
мацией называется правилом интерпретации сообщения. Это соответ-
ствие может быть однозначным и неоднозначным. Если соответствие 
однозначное, то сообщение имеет лишь одно правило интерпретации. 
Например, по последовательности точек, тире и пауз в азбуке Морзе 
однозначно восстанавливается переданная буква.  
Неоднозначность соответствия между сообщением и информа-
цией возможна в двух вариантах: 
– одна и та же информация может передаваться различными со-
общениями (например, прогноз погоды может быть получен из СМИ, 
по телефону и пр.); 
– одно и то же сообщение может содержать различную информа-
цию для разных приемников (примером может служить передача  
в 1936 г. по радио фразы «Над всей Испанией безоблачное небо», кото-
рая для непосвященных людей означала лишь прогноз погоды, а для 
знакомых с правилом интерпретации – сигнал к началу военных дей-
ствий).  
Рассмотрим такое понятие, как информационный процесс. Тер-
мин «процесс» применяется в тех случаях, когда некоторое качество, 
характеризующее систему или объект, меняется с течением времени  
в результате внешних воздействий или каких-то внутренних причин. 
Какие атрибуты могут изменяться с течением времени у нематериаль-
ной информации? Очевидно, только ее содержание и материальная обо-
лочка, посредством которого информация представлена, т. е. сообще-
ние. В связи с этим примем следующее определение: Информационный 
процесс – это изменение с течением времени содержания информации 
или представляющего его сообщения. 
Существуют различные виды информационных процессов: 
- порождение (создание) новой информации; 
- преобразование информации (т. е. порождение новой информа-
ции в результате обработки имеющейся); 
- передача информации (распространение в пространстве); 
- уничтожение информации. 

Все перечисленные события происходят не непосредственно  
с самой информацией, а с сообщением, т. е. ее материальной оболочкой. 
Поэтому возможны лишь два типа процессов:  
1) изменение сообщения с сохранением содержащейся в нем ин-
формации; 
2) изменение сообщения, сопровождающееся преобразованием 
информации.  
К процессам первого типа относятся передача информации без 
потерь и обратимая перекодировка; к процессам второго типа – созда-
ние-уничтожение, необратимая перекодировка, передача с потерями, 
обработка с появлением новой информации. 
Хранение информации. Хранение связывается с фиксацией пара-
метра материального носителя, который далее с течением времени не 
меняется. Следовательно, запись информации на носитель (непосред-
ственно момент фиксации параметра) и ее последующее считывание 
подпадают под определение информационного процесса, но само хра-
нение – нет.  
С передачей информации связана еще одна пара сопряженных 
понятий – источник и приемник информации. 
Источник информации – это субъект или объект, порождающий 
информацию и представляющий ее в виде сообщения. 
Приемник информации – это субъект или объект, принимающий 
сообщение и способный правильно его интерпретировать. 
В этих определениях сочетание «субъект или объект» означает, 
что источники и приемники информации могут быть одушевленными 
(человек, животные) или неодушевленными (технические устройства, 
природные явления). Для того чтобы объект (или субъект) считался ис-
точником информации, он должен не только ее породить, но и иметь 
возможность создать какой-то нестационарный процесс и связать ин-
формацию с его параметрами, т. е. создать сообщение. Например, если 
человек что-то придумал, но держит это в своем мозге, он не является 
источником информации; однако он им становится, как только свою 
идею изложит на бумаге (в виде текста, рисунка, схемы и пр.) или вы-
скажет словами. 
В определении приемника информации важным представляется 
то, что факт приема сообщения еще не означает получение информации; 
информация может считаться полученной только в том случае, 
если приемнику известно правило интерпретации сообщения. Другими 
словами, понятия «приемник сообщения» и «приемник информации»