МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ
РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное государственное бюджетное образовательное учреждение
высшего образования «Пермский государственный национальный
исследовательский университет»
Соликамский государственный педагогический институт (филиал)
федерального государственного бюджетного образовательного учреждения
высшего образования «Пермский государственный национальный
исследовательский университет»
Т. В. Рихтер
Теоретические основы
информатики
Учебно-методическое пособие
Соликамск
2019
1
Стр.1
УДК 004(075.2)
ББК 32.81я7
Р 23
Рецензенты:
Т. С. Шумейко, кандидат педагогических наук, декан естественноматематического
факультета, ассоциированный профессор кафедры информатики,
робототехники и компьютерных технологий Костанайского государственного
педагогического университета им. У. Султангазина;
И. В. Абрамова, кандидат педагогических наук, доцент кафедры математических
и естественнонаучных дисциплин СГПИ филиал ФГБОУ ВО «Пермский
государственный национальный исследовательский университет».
Р 23 Рихтер Т. В.
Теоретические основы информатики [Текст] : учебнометодическое
пособие. – Соликамск: РТО СГПИ филиал ПГНИУ;
ООО «Типограф», 2019. – 111 с. – ISBN 978-5-91252-112-6
Пособие представляет результаты исследования по проблеме изучения дисциплины
«Теоретические основы информатики» бакалаврами направления подготовки
«Прикладная математика и информатика». В издании рассмотрены предмет, структура,
место информатики в системе наук, различные подходы к определению информации,
вопросы теории информации Шеннона, теории кодирования, криптографии,
элементы теории алгоритмов и теории конечных автоматов, а также общие
вопросы моделирования и описания систем. Учебное пособие содержит краткий
теоретический материал, примеры решения задач, вопросы и задания для самоконтроля,
тестовый материал, а также практические работы (по вариантам).
Материалы издания будут интересны педагогическим работникам, студентам
и другим категориям читателей, интересующихся рассматриваемой
тематикой.
УДК 004(075.2)
ББК 32.81я7
Рекомендовано к изданию РИСо СГПИ (филиал) ПГНИУ.
Протокол № 117 от 9.10.2019
ISBN 978-5-91252-112-6
© Т. В. Рихтер, 2019
© Пермский государственный национальный
исследовательский университет, 2019
© Соликамский государственный педагогический
институт (филиал) ПГНИУ, 2019
2
Стр.2
Содержание
Введение.…………………………………………...…..………...……...…..4
Содержание дисциплины..……………………………………………..…5
Методические рекомендации по овладению дисциплиной...….….9
Глава 1.
Информатика: предмет, структура, место в системе наук...….…15
Глава 2.
Информация в теории Шеннона.
Энтропия, статистическое определение информации.
Вероятностный и объемный подходы
к измерению информации, формулы Шеннона и Хартли...…..…25
Глава 3.
Кодирование различных видов информации.
Понятие кода. Методы сжатия……...……..……….…...…………37
Глава 4.
Передача информации ……………..…….…..………………….....57
Глава 5.
Понятие алгоритма. Нестрогое определение алгоритма.
Уточнение понятия алгоритма. Машина Тьюринга.……………..67
Практические задания по курсу
«Теоретические основы информатики»…..….……………………80
Итоговый тест по дисциплине
«Теоретические основы информатики»…..………………………84
Итоговая работа по курсу
«Теоретические основы информатики».…..…..………………….95
Список литературы…..….…..…..….….…..….….……….….….…97
Приложения….…….…….….……………..………..…….….……..98
3
Стр.3
Введение
Учебное пособие представляет результаты исследования
по проблеме изучения дисциплины «Теоретические основы
информатики» бакалаврами направления подготовки «Прикладная
математика и информатика», что указывает на его актуальность.
В
пособии рассмотрены предмет, структура, место информатики
в системе наук, различные подходы к определению
информации, вопросы теории информации Шеннона, теории
кодирования, криптографии, элементы теории алгоритмов и
теории конечных автоматов, а также общие вопросы моделирования
и описания систем. Отбор материала произведен в
соответствии с программой подготовки обучающихся по направлению
«Прикладная математика и информатика» студентов
высших учебных заведений.
Учебное пособие содержит краткий теоретический материал,
примеры решения задач, вопросы и задания для самоконтроля,
тестовый материал, а также практические работы
(по вариантам).
Материалы учебного пособия имеют достаточную значимость
для практического применения, они могут быть использованы
в учебном процессе высших, профессиональных и
общеобразовательных учебных заведений, при организации
курсов повышения квалификации педагогических работников,
проведении мастер-классов, проблемных групп и семинаров.
Курс вводит студентов в современные проблемы теоретической
информатики, формирует информационную культуру,
способствует овладению методами точного анализа, которые
позволяют ответить на вопросы, возникающие при получении,
хранении, обработке, передаче и использовании информации.
4
Стр.4
Содержание дисциплины
Цель дисциплины: освоить теоретический фундамент и
математические методы при построении и изучении моделей
по представлению, обработке, передаче и использованию информации.
Задачи
дисциплины:
– формирование основных понятий теоретической информатики;
–
получение знаний об основных видах информационных
моделей и научных подходах, изучающих их свойства;
– освоение математических методов, которые при этом
используются.
Изучение данного курса будет полезно при знакомстве с
дисциплиной «Интеллектуальные системы», оно позволит
расширить подготовку к профессиональной деятельности.
Курс предназначен для студентов, обучающихся по направлению
«Прикладная математика и информатика».
Компетенции обучающихся, формируемые в результате
освоения дисциплины:
– способность использовать базовые знания естественных
наук, математики и информатики, основные факты, концепции,
принципы теорий, связанных с прикладной математикой
и информатикой;
– способность приобретать новые научные и профессиональные
знания, используя современные образовательные и
информационные технологии;
– способность критически переосмысливать накопленный
опыт, изменять при необходимости вид и характер своей
профессиональной деятельности.
В результате изучения дисциплины студент должен
знать:
– место информатики в системе наук;
– понятие информации, виды информации, методы ко5
Стр.5