Математические основы информатики. Андреева Е.В., Босова Л.Л., Фалина И.Н.
М.: 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. Особенности
реализации вещественной Вопросы и задания......................................................... 88 §2.3. Представление текстовой информации............................. 89 Вопросы и задания.......................................................... 95 § 2.4. Представление графической информации........................ 96 2.4.1. Общие подходы к представлению
в компьютере информации естественного 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 § 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 и др."
|
||
|
Начальная школа |
||
|
|
||
|
||
