Математические основы информатики. Андреева Е.В., Босова Л.Л., Фалина И.Н.

М.: БИНОМ. Лаборатория знаний, 2005. - 328 с.

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

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

Формат: pdf / zip

Размер: 13 Мб

Скачать / Download файл (Яндекс - Народ. Диск.) 1) Введите 6 цифр. 2) Нажмите зеленую кнопку. 3) На следующей странице (если стоит галочка) обязательно уберите галочку из графы "Установить Яндекс Бар", иначе Вы ничего не сможете скачать. 4) Нажмите ссылку и начнется скачивание.

Оглавление

От авторов................................................................................ 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