Учебное пособие / Е. В. Андреева, Л. Л. Босова, И. Н. Фалина — М.:
2005 — 328 с.: ил.
ISBN 5-94774-139-3 Учебное пособие входит в УМК для старших классов наряду с методическим пособием и хрестоматией. Материал раскрывает взаимосвязь математики и информатики, показывает, как развитие одной из этих научных областей стимулировало развитие другой. Дается углубленное представление о математическом аппарате, используемом в информатике, показывается, как теоретические результаты, полученные в математике, послужили источником новых идей и результатов в теории алгоритмов, программировании и в других разделах информатики.
Для учащихся старших классов информационно-технологического, физико-математического и естественно-научного профилей, желающих расширить свои теоретические представления о математике в информатике и информатике в математике. Содержание
От авторов
Системы счисления
Позиционные системы счисления. Основные определения
Вопросы и задания
Единственность представления чисел в Р-ичных системах счисления
Вопросы и задания
Представление произвольных чисел в позиционных системах счисления
Развернутая и свернутая формы записи
Перечисление натуральных чисел
Представление обыкновенных десятичных дробей в Р-ичных системах счисления
Вопросы и задания
Арифметические операции в Р-ичных системах счисления
Сложение
Вычитание
Умножение
Деление
Вопросы и задания
Перевод чисел из Р-ичной системы счисления в десятичную
Перевод целых Р-ичных чисел
Перевод конечных Р-ичных дробей
Перевод периодических Р-ичных дробей
Вопросы и задания
Перевод чисел из десятичной системы счисления в Р-ичную
Два способа перевода целых чисел
Перевод конечных десятичных дробей
Вопросы и задания
Смешанные системы счисления
Вопросы и задания
Системы счисления и архитектура компьютеров
Использование уравновешенной троичной системы счисления
Использование фибоначчиевой системы счисления
Недвоичные компьютерные арифметики
Вопросы и задания
Заключение
Представление информации в компьютере
Представление целых чисел
Представление целых положительных чисел
Представление целых отрицательных чисел
Перечисление чисел в целочисленной компьютерной арифметике
Особенности реализации арифметических операций в конечном числе разрядов
Вопросы и задания
Представление вещественных чисел
Нормализованная запись числа
Представление вещественных чисел в формате с плавающей запятой
Выполнение арифметических операций над вещественными числами
Особенности реализации вещественной компьютерной арифметики
Вопросы и задания
Представление текстовой информации
Вопросы и задания
Представление графической информации
Общие подходы к представлению в компьютере информации естественного происхождения
Векторное и растровое представление графической информации
Квантование цвета
Цветовая модель RGB
Цветовая модель CMYK
Цветовая модель HSB
Вопросы и задания
Представление звуковой информации
Понятие звукозаписи
Импульсно-кодовая модуляция
Формат MIDI
Принципы компьютерного воспроизведения звука
Вопросы и задания
Методы сжатия цифровой информации
Алгоритмы обратимых методов
Методы сжатия с регулируемой потерей информации
Вопросы и задания
Заключение
Введение в алгебру логики
Алгебра логики. Понятие высказывания
Вопросы и задания
Логические операции. Таблицы истинности
Вопросы и задания
Логические формулы. Законы алгебры логики
Вопросы и задания
Методы решения логических задач
Вопросы и задания
Алгебра переключательных схем
Вопросы и задания
Булевы функции
Вопросы и задания
Канонические формы логических формул.
Теорема о СДНФ
Вопросы и задания
Минимизация булевых функций в классе дизъюнктивных нормальных форм
Практические задания
Полные системы булевых функций
Вопросы и задания
Элементы схемотехники. Логические схемы
Вопросы и задания
Заключение
Элементы теории алгоритмов
Понятие алгоритма. Свойства алгоритмов
Вопросы и задания
Уточнение понятия алгоритма. Машина Тьюринга
Необходимость уточнения понятия алгоритма
Описание машины Тьюринга
Примеры машин Тьюринга
Формальное описание алгоритма
Математическое описание машины Тьюринга
Вопросы и задания
Машина Поста как уточнение понятия алгоритма
Вопросы и задания
Алгоритмически неразрешимые задачи и вычислимые функции
Вопросы и задания
Понятие сложности алгоритма
Вопросы и задания
Анализ алгоритмов поиска
Последовательный поиск в неупорядоченном массиве
Алгоритм бинарного поиска в упорядоченном массиве
Вопросы и задания
Анализ алгоритмов сортировки
Обменная сортировка методом «пузырька»
Сортировка выбором
Сортировка вставками
Сортировка слиянием
Вопросы и задания
Заключение
Основы теории информации
Понятие информации. Количество информации.
Единицы измерения информации
Вопросы и задания
Формула Хартли определения количества информации
Вопросы и задания
Применение формулы Хартли
Вопросы и задания
Закон аддитивности информации. Алфавитный подход к измерению информации
Вопросы и задания
Информация и вероятность. Формула Шеннона
Вопросы и задания
Оптимальное кодирование информации и ее сложность
Вопросы и задания
Заключение
Математические основы вычислительной геометрии и компьютерной графики
Координаты и векторы на плоскости
Вопросы и задания
Способы описания линий на плоскости
Общее уравнение прямой
Нормированное уравнение прямой
Параметрические уравнения прямой, луча, отрезка
Способы описания окружности
Вопросы и задания
Задачи компьютерной графики на взаимное расположение точек и фигур
Прямая, перпендикулярная данной и проходящая через заданную точку
Расположение точки относительно прямой, луча или отрезка
Взаимное расположение прямых, отрезков, лучей
Взаимное расположение окружности и прямой
Взаимное расположение двух окружностей
Вопросы и задания
Многоугольники
Проверка выпуклости многоугольника
Проверка принадлежности точки внутренней области многоугольника
Вычисление площади простого многоугольника
Вопросы и задания
Геометрические объекты в пространстве
Основные формулы
Определение пересечения прямой линии и треугольника в пространстве
Вращение точки вокруг заданной прямой в пространстве
Вопросы и задания
Заключение
Приложение
Предметный указатель
ISBN 5-94774-139-3 Учебное пособие входит в УМК для старших классов наряду с методическим пособием и хрестоматией. Материал раскрывает взаимосвязь математики и информатики, показывает, как развитие одной из этих научных областей стимулировало развитие другой. Дается углубленное представление о математическом аппарате, используемом в информатике, показывается, как теоретические результаты, полученные в математике, послужили источником новых идей и результатов в теории алгоритмов, программировании и в других разделах информатики.
Для учащихся старших классов информационно-технологического, физико-математического и естественно-научного профилей, желающих расширить свои теоретические представления о математике в информатике и информатике в математике. Содержание
От авторов
Системы счисления
Позиционные системы счисления. Основные определения
Вопросы и задания
Единственность представления чисел в Р-ичных системах счисления
Вопросы и задания
Представление произвольных чисел в позиционных системах счисления
Развернутая и свернутая формы записи
Перечисление натуральных чисел
Представление обыкновенных десятичных дробей в Р-ичных системах счисления
Вопросы и задания
Арифметические операции в Р-ичных системах счисления
Сложение
Вычитание
Умножение
Деление
Вопросы и задания
Перевод чисел из Р-ичной системы счисления в десятичную
Перевод целых Р-ичных чисел
Перевод конечных Р-ичных дробей
Перевод периодических Р-ичных дробей
Вопросы и задания
Перевод чисел из десятичной системы счисления в Р-ичную
Два способа перевода целых чисел
Перевод конечных десятичных дробей
Вопросы и задания
Смешанные системы счисления
Вопросы и задания
Системы счисления и архитектура компьютеров
Использование уравновешенной троичной системы счисления
Использование фибоначчиевой системы счисления
Недвоичные компьютерные арифметики
Вопросы и задания
Заключение
Представление информации в компьютере
Представление целых чисел
Представление целых положительных чисел
Представление целых отрицательных чисел
Перечисление чисел в целочисленной компьютерной арифметике
Особенности реализации арифметических операций в конечном числе разрядов
Вопросы и задания
Представление вещественных чисел
Нормализованная запись числа
Представление вещественных чисел в формате с плавающей запятой
Выполнение арифметических операций над вещественными числами
Особенности реализации вещественной компьютерной арифметики
Вопросы и задания
Представление текстовой информации
Вопросы и задания
Представление графической информации
Общие подходы к представлению в компьютере информации естественного происхождения
Векторное и растровое представление графической информации
Квантование цвета
Цветовая модель RGB
Цветовая модель CMYK
Цветовая модель HSB
Вопросы и задания
Представление звуковой информации
Понятие звукозаписи
Импульсно-кодовая модуляция
Формат MIDI
Принципы компьютерного воспроизведения звука
Вопросы и задания
Методы сжатия цифровой информации
Алгоритмы обратимых методов
Методы сжатия с регулируемой потерей информации
Вопросы и задания
Заключение
Введение в алгебру логики
Алгебра логики. Понятие высказывания
Вопросы и задания
Логические операции. Таблицы истинности
Вопросы и задания
Логические формулы. Законы алгебры логики
Вопросы и задания
Методы решения логических задач
Вопросы и задания
Алгебра переключательных схем
Вопросы и задания
Булевы функции
Вопросы и задания
Канонические формы логических формул.
Теорема о СДНФ
Вопросы и задания
Минимизация булевых функций в классе дизъюнктивных нормальных форм
Практические задания
Полные системы булевых функций
Вопросы и задания
Элементы схемотехники. Логические схемы
Вопросы и задания
Заключение
Элементы теории алгоритмов
Понятие алгоритма. Свойства алгоритмов
Вопросы и задания
Уточнение понятия алгоритма. Машина Тьюринга
Необходимость уточнения понятия алгоритма
Описание машины Тьюринга
Примеры машин Тьюринга
Формальное описание алгоритма
Математическое описание машины Тьюринга
Вопросы и задания
Машина Поста как уточнение понятия алгоритма
Вопросы и задания
Алгоритмически неразрешимые задачи и вычислимые функции
Вопросы и задания
Понятие сложности алгоритма
Вопросы и задания
Анализ алгоритмов поиска
Последовательный поиск в неупорядоченном массиве
Алгоритм бинарного поиска в упорядоченном массиве
Вопросы и задания
Анализ алгоритмов сортировки
Обменная сортировка методом «пузырька»
Сортировка выбором
Сортировка вставками
Сортировка слиянием
Вопросы и задания
Заключение
Основы теории информации
Понятие информации. Количество информации.
Единицы измерения информации
Вопросы и задания
Формула Хартли определения количества информации
Вопросы и задания
Применение формулы Хартли
Вопросы и задания
Закон аддитивности информации. Алфавитный подход к измерению информации
Вопросы и задания
Информация и вероятность. Формула Шеннона
Вопросы и задания
Оптимальное кодирование информации и ее сложность
Вопросы и задания
Заключение
Математические основы вычислительной геометрии и компьютерной графики
Координаты и векторы на плоскости
Вопросы и задания
Способы описания линий на плоскости
Общее уравнение прямой
Нормированное уравнение прямой
Параметрические уравнения прямой, луча, отрезка
Способы описания окружности
Вопросы и задания
Задачи компьютерной графики на взаимное расположение точек и фигур
Прямая, перпендикулярная данной и проходящая через заданную точку
Расположение точки относительно прямой, луча или отрезка
Взаимное расположение прямых, отрезков, лучей
Взаимное расположение окружности и прямой
Взаимное расположение двух окружностей
Вопросы и задания
Многоугольники
Проверка выпуклости многоугольника
Проверка принадлежности точки внутренней области многоугольника
Вычисление площади простого многоугольника
Вопросы и задания
Геометрические объекты в пространстве
Основные формулы
Определение пересечения прямой линии и треугольника в пространстве
Вращение точки вокруг заданной прямой в пространстве
Вопросы и задания
Заключение
Приложение
Предметный указатель