ОСНОВЫ
ИНФОРМАТИКИ
Улан-Удэ
2026
Стр.1
МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ
РОССИЙСКОЙ ФЕДЕРАЦИИ
ФГБОУ ВО «БУРЯТСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
ИМЕНИ ДОРЖИ БАНЗАРОВА»
ОСНОВЫ ИНФОРМАТИКИ
Рекомендовано Экспертным советом университета
в качестве практикума для обучающихся по направлению
подготовки 09.03.02 Информационные системы и технологии
Улан-Удэ
Издательство Бурятского госуниверситета
имени Доржи Банзарова
2026
Стр.2
УДК 004 (075.8)
ББК 32.8я73
О 75
Утверждено
Экспертным советом университета.
Протокол № 4 от 12.12.2025 г.
Р е ц е н з е нты
И. С. Евдокимова, кандидат технических наук, доцент
кафедры «Программная инженерия и ИИ»,
Восточно-Сибирский государственный университет
технологий и управления
Т. Ж. Базаржапова, кандидат педагогических наук, доцент
кафедры «Вычислительная техника и информатика»,
Бурятский государственный университет им. Д. Банзарова
О 75
Основы информатики: практикум / составители Т. В. Немчинова,
Д. А. Габеева, Т. С. Цыбикова. — Улан-Удэ: Издательство Бурятского
госуниверситета им. Д. Банзарова, 2026. — 84 с.
ISBN 978-5-9793-2091-5
Лабораторный практикум дисциплины «Теоретические основы информатики»
разработан в соответствии с требованиями ФГОС по направлению
подготовки 09.03.02 Информационные системы и технологии. Содержит
разбор заданий к лабораторным работам курса «Теоретические основы информатики»,
а также описание различных методов и подходов к способам
решения. Предлагаются контрольные вопросы и задания для самостоятельного
выполнения.
Предназначено для студентов высших учебных заведений.
УДК 004 (075.8)
ББК 32.8я73
© Т. В. Немчинова, Д. А. Габеева,
Т. С. Цыбикова, составление, 2026
© Бурятский госуниверситет
ISBN 978-5-9793-2091-5
2
им. Д. Банзарова, 2026
Стр.3
ПРЕДИСЛОВИЕ
Настоящее учебное издание представляет собой практикум для
дисциплины «Теоретические основы информатики» в рамках реализации
образовательной программы высшего образования по направлению
подготовки 09.03.02 Информационные системы и технологии
по очной форме обучения и подготовлено в соответствии с требованиями
Федерального государственного образовательного стандарта
высшего образования.
Дисциплина «Теоретические основы информатики» относится к
дисциплинам профессионального модуля Блока 1, части, формируемой
участниками образовательных отношений.
Изучение дисциплины направлено на формирование универсальной
компетенции:
УК-2.1 — Определяет круг задач в рамках поставленной цели,
определяет связи между ними
В результате освоения дисциплины обучающийся должен:
знать:
основные понятия и модели теории информации: количество
информации (подходы Хартли и Шеннона), энтропия, избыточность
информации;
фундаментальные принципы построения и функционирования
логических элементов компьютера: базовые логические функции (И,
ИЛИ, НЕ, исключающее ИЛИ) и их таблицы истинности;
основные понятия теории алгоритмов: определение алгоритма,
свойства алгоритмов, способы задания алгоритмов;
основные модели вычислений: машина Тьюринга, машина Поста;
уметь:
проводить расчет количества информации для различных вероятностных
моделей;
строить таблицы истинности для логических выражений и
комбинационных схем;
составлять логические схемы по заданной функции и минимизировать
их; анализировать работу базовых узлов ЭВМ на уровне логических
элементов;
формализовывать неформально поставленные задачи; составлять
алгоритмы решения типовых задач и представлять их в виде
блок-схем или на учебном алгоритмическом языке;
3
Стр.4
анализировать алгоритмы с точки зрения их корректности и
сложности;
владеть:
терминологией в области теоретических основ информатики;
навыками применения аппарата теории информации и математической
логики для анализа информационных процессов;
методами синтеза и анализа логических схем;
навыками алгоритмического мышления и методами проектирования
алгоритмов;
навыками решения учебных задач, требующих интеграции знаний
из разных разделов теоретической информатики (например, анализ
информационной эффективности алгоритма).
Структура и содержание пособия отражают логику изучения дисциплины
и включают три ключевых модуля: «Теория информации»,
«Логические основы ЭВМ» и «Теория алгоритмов». Каждый модуль
содержит теоретический материал, иллюстрированный примерами,
практические задания для аудиторной и самостоятельной работы, а
также контрольные вопросы и задания для самопроверки.
Практикум апробирован в учебном процессе и предназначен для
использования на лекционных, практических и лабораторных занятиях,
а также для организации самостоятельной работы студентов.
4
Стр.5
СОДЕРЖАНИЕ
Предисловие…….……..………………..……………………… 3
Глава 1 Теория информации
1.1 Понятие энтропии. Вычисление количества информации.. 5
Задание для лабораторной работы.……………………….. 9
Контрольные вопросы………………………………………… 14
1.2 Кодирование информации. Способы построения двоичных
кодов…………………………………………………………... 14
1.2.1 Построение кода постоянной длины………………….. 15
Задание для лабораторной работы.……………………….. 16
1.2.2 Построение кода переменной длины…………………... 18
Задание для лабораторной работы.……………………….. 22
1.2.3 Кодирование по Шеннону — Фано…………………… 22
Контрольные вопросы………………………………………… 24
Задания для самостоятельной работы……………………... 24
1.3 Представление целых чисел в памяти компьютера……….. 27
Задание для лабораторной работы.………………………... 31
Задания для самостоятельного выполнения……………….. 32
Глава 2 Основы логики и логические основы компьютера
2.1 История логики и основные понятия………………………. 33
2.2 Алгебра высказываний……………………………………… 35
2.3 Логические операции………………………………………... 35
2.4 Логические выражения, таблицы истинности……………... 37
Задание для лабораторной работы.……………………….. 38
2.5 Законы алгебры логики……………………………………… 39
Задание для лабораторной работы.……………………….. 42
2.6. Логические элементы компьютера………………………… 43
Сумматор……………………………………………………... 44
Триггер………………………………………….…………….. 47
Стр.82
Задание для лабораторной работы.……………………….. 48
Контрольные вопросы……………………………………….. 51
Задания для самостоятельного выполнения……………….. 51
Глава 3 Элементы теории алгоритмов
3.1 Нестрогое определение алгоритма…………………………. 53
3.2 Машина Поста……………………………………………….. 59
Задание для лабораторной работы.……………………….. 65
3.3 Машина Тьюринга…………………………………………... 66
Задание для лабораторной работы.……………………….. 76
Контрольные вопросы……………………………………….. 77
Задания для самостоятельного выполнения……………….. 78
Библиографический список…………………………………... 80
Стр.83