Учебное пособие входит в УМК для старших классов наряду с методическим пособием и хрестоматией.

Материал раскрывает взаимосвязь математики и информатики, показывает, как развитие одной из этих научных областей стимулировало развитие другой. Дается углубленное представление о математическом аппарате, используемом в информатике, демонстрируется, как результаты, полученные в математике, послужили источником новых идей и результатов в теории алгоритмов, программировании и в других разделах информатики.

Для учащихся старших классов информационно-технологического, физико-математического и естественно-научного профилей, желающих расширить свои теоретические представления о математике в информатике и информатике в математике.

 

Оглавление
От авторов 8
Глава 1. Системы счисления 11
§1.1. Позиционные системы счисления. Основные определения 13
Вопросы и задания 19
§1.2. Единственность представления чисел в Р-ичных системах счисления 20
Вопросы и задания 24
§1.3. Представление произвольных чисел в позиционных системах счисления 25
1.3.1. Развернутая и свернутая формы записи 25
1.3.2. Перечисление натуральных чисел 26
1.3.3. Представление обыкновенных десятичных дробей в Р-ичных системах счисления 28
Вопросы и задания 30
§1.4. Арифметические операции в Р-ичных системах счисления 31
1.4.1. Сложение 31
1.4.2. Вычитание 33
1.4.3. Умножение 33
1.4.4. Деление 35
Вопросы и задания 37
§1.5. Перевод чисел из Р-ичной системы счисления в десятичную 38
1.5.1. Перевод целых Р-ичных чисел . . 38
1.5.2. Перевод конечных Р-ичных дробей 40
1.5.3. Перевод периодических Р-ичных дробей 42
Вопросы и задания 44
§1.6. Перевод чисел из десятичной системы счисления в Р-ичную 44
1.6.1. Два способа перевода целых чисел 44
1.6.2. Перевод конечных десятичных дробей 47
Вопросы и задания 49
§ 1.7. Смешанные системы счисления 50
Вопросы и задания 54
§ 1.8. Системы счисления и архитектура компьютеров 54
1.8.1. Использование уравновешенной троичной системы счисления 56
1.8.2. Использование фибоначчиевой системы счисления 58
1.8.3. Недвоичные компьютерные арифметики 60
Вопросы и задания 61
Заключение 61
Глава 2. Представление информации в компьютере 63
§ 2.1. Представление целых чисел 65
2.1.1. Представление целых положительных чисел ... 66
2.1.2. Представление целых отрицательных чисел ... 68
2.1.3. Перечисление чисел в целочисленной компьютерной арифметике 71
2.1.4. Особенности реализации арифметических операций в конечном числе разрядов 73
Вопросы и задания 74
§2.2. Представление вещественных чисел 74
2.2.1. Нормализованная запись числа 75
2.2.2. Представление вещественных чисел
в формате с плавающей запятой 80
2.2.3. Выполнение арифметических операций
над вещественными числами 81
2.2.4. Особенности реализации вещественной
компьютерной арифметики 84
Вопросы и задания 88
§ 2.3. Представление текстовой информации 89
Вопросы и задания 95
§ 2.4. Представление графической информации 96
2.4.1. Общие подходы к представлению в компьютере информации естественного происхождения 97
2.4.2. Векторное и растровое представление графической информации 102
2.4.3. Квантование цвета 104
2.4.4. Цветовая модель RGB 107
2.4.5. Цветовая модель CMYK 112
2.4.6. Цветовая модель HSB 115
Вопросы и задания 119
§ 2.5. Представление звуковой информации 120
2.5.1. Понятие звукозаписи 122
2.5.2. Импульсно-кодовая модуляция 123
2.5.3. Формат MIDI 127
2.5.4. Принципы компьютерного воспроизведения звука 128
Вопросы и задания 129
§ 2.6. Методы сжатия цифровой информации 130
2.6.1. Алгоритмы обратимых методов 132
2.6.2. Методы сжатия с регулируемой потерей информации 141
Вопросы и задания 145
Заключение 145
Глава 3. Введение в алгебру логики 147
§ 3.1. Алгебра логики. Понятие высказывания 148
Вопросы и задания 151
§ 3.2. Логические операции. Таблицы истинности 152
Вопросы и задания 162
§ 3.3. Логические формулы. Законы алгебры логики 164
Вопросы и задания 167
§ 3.4. Методы решения логических задач 168
Вопросы и задания 172
§ 3.5. Алгебра переключательных схем 173
Вопросы и задания 175
§ 3.6. Булевы функции 176
Вопросы и задания 178
§ 3.7. Канонические формы логических формул. Теорема о СДНФ 178
Вопросы и задания 184
§ 3.8. Минимизация булевых функций в классе дизъюнктивных нормальных форм 185
Практические задания 189
§ 3.9. Полные системы булевых функций 190
Вопросы и задания 192
§ 3.10. Элементы схемотехники. Логические схемы 193
Вопросы и задания 197
Заключение 197
Глава 4. Элементы теории алгоритмов 199
§ 4.1. Понятие алгоритма. Свойства алгоритмов 200
Вопросы и задания 208
§ 4.2. Уточнение понятия алгоритма. Машина Тьюринга . . 209
4.2.1. Необходимость уточнения понятия алгоритма . 209
4.2.2. Описание машины Тьюринга 212
4.2.3. Примеры машин Тьюринга 215
4.2.4. Формальное описание алгоритма. Математическое описание машины Тьюринга .218
Вопросы и задания 220
§4.3. Машина Поста как уточнение понятия алгоритма . . . 220
Вопросы и задания 223
§4.4. Алгоритмически неразрешимые задачи и вычислимые функции 224
Вопросы и задания 229
§4.5. Понятие сложности алгоритма 230
Вопросы и задания 234
§ 4.6. Анализ алгоритмов поиска 234
4.6.1. Последовательный поиск в неупорядоченном массиве 235
4.6.2. Алгоритм бинарного поиска в упорядоченном массиве 237
Вопросы и задания 238
§ 4.7. Анализ алгоритмов сортировки 238
4.7.1. Обменная сортировка методом «пузырька» . . . 239
4.7.2. Сортировка выбором 241
4.7.3. Сортировка вставками 243
4.7.4. Сортировка слиянием 244
Вопросы и задания 247
Заключение 248
Глава 5. Основы теории информации 249
§ 5.1. Понятие информации. Количество информации. Единицы измерения информации 250
Вопросы и задания 254
§ 5.2. Формула Хартли определения количества информации 254
Вопросы и задания 260
§ 5.3. Применение формулы Хартли 261
Вопросы и задания 265
§ 5.4. Закон аддитивности информации. Алфавитный подход к измерению информации 266
Вопросы и задания 269
§5.5. Информация и вероятность. Формула Шеннона 269
Вопросы и задания 276
§ 5.6. Оптимальное кодирование информации и ее сложность 277
Вопросы и задания 280
Заключение 281
Глава 6. Математические основы вычислительной геометрии и компьютерной графики 283
§ 6.1. Координаты и векторы на плоскости 285
Вопросы и задания 292
§ 6.2. Способы описания линий на плоскости 292
6.2.1. Общее уравнение прямой 292
6.2.2. Нормированное уравнение прямой 294
6.2.3. Параметрические уравнения прямой, луча, отрезка 296
6.2.4. Способы описания окружности 297
Вопросы и задания 298
§6.3. Задачи компьютерной графики на взаимное расположение точек и фигур 298
6.3.1. Прямая, перпендикулярная данной и проходящая через заданную точку 298
6.3.2. Расположение точки относительно прямой, луча или отрезка 299
6.3.3. Взаимное расположение прямых, отрезков, лучей 301
6.3.4. Взаимное расположение окружности и прямой 303
6.3.5. Взаимное расположение двух окружностей . . . 305
Вопросы и задания 307
§ 6.4. Многоугольники 307
6.4.1. Проверка выпуклости многоугольника 308
6.4.2. Проверка принадлежности точки внутренней области многоугольника 308
6.4.3. Вычисление площади простого многоугольника 310
Вопросы и задания 311
§6.5. Геометрические объекты в пространстве 312
6.5.1. Основные формулы 312
6.5.2. Определение пересечения прямой линии и треугольника в пространстве 314
6.5.3. Вращение точки вокруг заданной прямой в пространстве 315
Вопросы и задания 317
Заключение 318
Приложение 319
Предметный указатель 320