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

Министерство науки и высшего образования Российской Федерации  
Федеральное государственное бюджетное  
образовательное учреждение высшего образования 
«Казанский национальный исследовательский 
технологический университет» 
 
 
 
 
 
 
 
Л. Т. Ягьяева, М. Ю. Валеев 
 
 
ТЕОРИЯ АЛГОРИТМОВ  
И ПРОГРАММ 
 
Учебное пособие 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Казань 
Издательство КНИТУ 
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) изменение сообщения, сопровождающееся преобразованием 
информации.  
К процессам первого типа относятся передача информации без 
потерь и обратимая перекодировка; к процессам второго типа – создание-уничтожение, необратимая перекодировка, передача с потерями, 
обработка с появлением новой информации. 
Хранение информации. Хранение связывается с фиксацией параметра материального носителя, который далее с течением времени не 
меняется. Следовательно, запись информации на носитель (непосредственно момент фиксации параметра) и ее последующее считывание 
подпадают под определение информационного процесса, но само хранение – нет.  
С передачей информации связана еще одна пара сопряженных 
понятий – источник и приемник информации. 
Источник информации – это субъект или объект, порождающий 
информацию и представляющий ее в виде сообщения. 
Приемник информации – это субъект или объект, принимающий 
сообщение и способный правильно его интерпретировать. 
В этих определениях сочетание «субъект или объект» означает, 
что источники и приемники информации могут быть одушевленными 
(человек, животные) или неодушевленными (технические устройства, 
природные явления). Для того чтобы объект (или субъект) считался источником информации, он должен не только ее породить, но и иметь 
возможность создать какой-то нестационарный процесс и связать информацию с его параметрами, т. е. создать сообщение. Например, если 
человек что-то придумал, но держит это в своем мозге, он не является 
источником информации; однако он им становится, как только свою 
идею изложит на бумаге (в виде текста, рисунка, схемы и пр.) или выскажет словами. 
В определении приемника информации важным представляется 
то, что факт приема сообщения еще не означает получение информации; информация может считаться полученной только в том случае, 
если приемнику известно правило интерпретации сообщения. Другими 
словами, понятия «приемник сообщения» и «приемник информации»