Наверх

С. Юрцева, 2001 (Rus)
Алгоритмы в школьной информатике

От автора
Методическое пособие подготовлено по материалам, используемым в курсе информатики профильных классов информатика-математика и занятиях команды гимназии N42 г.Барнаула по программированию. В пособии большое внимание уделяется реализации задачи с точки зрения оптимальности алгоритма ее решения (что фактически не рассматривается в школьном курсе). Примеры задач реализованы на языке Паскаль, который является не только стартовым языком профессионального программирования, но и оптимален при реализации олимпиадных задач

Разделы пособия достаточно независимы, что позволяет их изучать непоследовательно, при этом темы, рассматриваемые в отдельных разделах,
имеют свои сложности. Как показывает опыт, при использовании данных материалов следует соблюдать принцип дидактической спирали: изучать
разделы не целиком, а частично и последовательно, т.е. возвращаться к каждому разделу всякий раз для более детального рассмотрении. Строение разделов одинаково: небольшие теоретические выкладки с пояснениями на примерах и задачи для самостоятельного решения

Методическое пособие предназначено как для преподавателей в качестве материалов к уроку или дополнительным занятиям, так и для самостоятельной работы, увлекающихся программированием школьников (прим. CHAS: в процессе работы с материалом следует быть внимательным и аккуратным в связи с замеченными неточностями, опечатками)


СОДЕРЖАНИЕ

ГЛАВА 1. ВВЕДЕНИЕ В КОМПЬЮТЕРНУЮ АЛГОРИТМИКУ
   1.1 Анализ алгоритма

ГЛАВА 2. ПРИНЦИПЫ ПРОВЕРКИ УЧЕБНЫХ И ОЛИМПИАДНЫХ ЗАДАЧ ПО ИНФОРМАТИКЕ

ГЛАВА 3.ЧИСЛА
  
3.1 Цифры числа
   3.2 Простые числа
      3.2.1 Простые делители
   3.3 Числа Фибоначчи

ГЛАВА 4. СОРТИРОВКА
   4.1 Понятие сортировки
      4.1.1 Сортировка простым обменом
   4.2 Поиск данных
      4.2.1 Линейный поиск
      4.2.2 Бинарный поиск
   
ГЛАВА 5. ГЕОМЕТРИЧЕСКИЕ ФИГУРЫ НА ПЛОСКОСТИ
   5.1 Прямая и отрезок прямой
   5.3 Треугольник
      5.3.1 Площадь произвольного треугольника
      5.3.2 Замечательные линии и точки треугольника
      5.3.3 Свойства треугольников
   5.4 Многоугольник
      5.4.1 Выпуклый многоугольник
      5.4.2 Площадь простого плоского многоугольника

ГЛАВ 6. ПЕРЕБОР И МЕТОДЫ ЕГО СОКРАЩЕНИЯ
   6.1 NP-полные задачи
      6.1.1 Решение NP-полных задач
         6.1.1.1 Типы рекурсивных алгоритмов
      6.1.2 Примеры NP-полных задач
   6.2 Перебор вариантов
   6.3 Перебор с возвратом
   6.4 Перебор с отсечением и склеиванием ветвей
   6.5 Динамическое программирование
      6.5.1 Алгоритм
      6.5.2 Условия применения динамического программирования
      6.5.3 Реализация алгоритма ДП
         6.5.3.1 Сведение задачи к подзадачам
         6.5.3.2 Понятие рекуррентного соотношения
         6.5.3.3 Правильные рекуррентные соотношения
         6.5.3.4 Использование таблиц для запоминания решений подзадач
         6.5.3.6 Восстановление решения по матрице
   6.6 Волновые алгоритмы
   6.7 «Жадные" алгоритмы
      6.7.1 Условия применения «жадных» алгоритмов

ГЛАВА 7. ГРАФЫ
   7.1 Основные понятия и определения
   7.2 Способы описания графов
      7.2.1 Матрица смежности
      7.2.2 Перечень ребер
      7.2.3 Список смежных вершин
   7.3 Понятие достижимости
   7.4 Поиск кратчайших путей в графе
      7.4.1 Поиск в глубину
      7.4.2 Поиск в ширину
      7.4.3 Волновой алгоритм