Правообладателям
Математические основы информатики. Андреева Е.В., Босова Л.Л., Фалина И.Н.
М.: 2005. - 328 с.
Учебное пособие входит в УМК для старших классов наряду с методическим пособием и хрестоматией. Материал раскрывает взаимосвязь математики и информатики, показывает, как развитие одной из этих научных областей стимулировало развитие другой. Дается углубленное представление о математическом аппарате, используемом в информатике, показывается, как теоретические результаты, полученные в математике, послужили источником новых идей и результатов в теории алгоритмов, программировании и в других разделах информатики.
Для учащихся старших классов информационно-технологического, физико-математического и естественно-научного профилей, желающих расширить свои теоретические представления о математике в информатике и информатике в математике.
Формат: pdf
Размер: 13,7 Мб
Скачать: drive.google
Оглавление
От авторов................................................................................ 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
О том, как читать книги в форматах pdf, djvu - см. раздел "Программы; архиваторы; форматы pdf, djvu и др."
.
|
Начальная школа |
||
|
|
||
|
||