С момента появления компьютера, с момента использования его для решения самых разнообразных задач получила развитие системная область знаний математики, связанная с программированием. Компьютер, при всех его огромных возможностях, может работать только с конечным множеством объектов (задача проецируется на конечномерный случай), причем на этом множестве объектов должно быть определено отношение порядка [1]. Только в этом случае проблема (задача) подвластна компьютеру при условии, что найден эффективный способ её решения. Эффект «комбинаторного взрыва» показывает, что компьютер бессилен при решении даже очень простых задач. Обобщая, можно сказать, что практически компьютер решает только две задачи: подсчет количества объектов определенной природы (счет) или поиск объекта (из известного множества объектов), удовлетворяющего определенным условиям (перебор).
Потребности практики, а именно программирования, определяют развитие «стыка» информатики и математики. Эта область знаний не исчерпывается одним предметом «дискретной математикой», но он является характерным, основополагающим. На основе анализа учебной литературы попытаемся определить тенденции развития курса и высказать предположение об особенностях содержания физико-математического профиля обучения информатике в старших классах школы. Основное содержание учебников и их авторы представлены в таблице.
|
Авторы |
Содержание |
|
А. Ахо и др.[2] |
Модели вычислений, разработка эффективных алгоритмов, сортировка и порядковые статистики, структуры данных для работы со множествами, алгоритмы на графах, умножение матриц, арифметические операции над целыми числами и полиномами и др. |
|
Э. Рейнгольд и др. [3] |
Комбинаторные вычисления, представление комбинаторных объектов, подсчет и оценивание, исчерпывающий поиск, порождение элементарных комбинаторных объектов, быстрый поиск, сортировка, алгоритмы на графах, эквивалентность некоторых комбинаторных задач |
|
В. Липский [4] |
Введение в комбинаторику, алгоритмы на графах, нахождение кратчайших путей в графе, потоки в сетях и родственные задачи, матроиды |
|
Д. Кук, Г. Блейз [5] |
Множества, отношения, функции, основные понятия арифметики, алгебраические структуры, матрицы, теория графов, языки и грамматики, конечные автоматы, компьютерная геометрия |
|
В. Л. Матросов, В. А. Стеценко [6] |
Конечные функции, элементы комбинаторики, конечные графы, алгоритмы на графах |
|
С. В. Яблонский [7] |
Алгебра логики, k-значная логика, ограниченно-детерминированные функции с операциями, вычислимые функции, комбинаторный анализ, графы и сети, теория кодирования |
|
Р. Грэхем и др. [8] |
Возвратные задачи, исчисление сумм, целочисленные функции, элементы теории чисел, биномиальные коэффициенты, специальные числа, производящие функции, дискретная вероятность, асимптотика |
|
Т. Кормен и др. [9] |
Математические основы анализа алгоритмов, сортировка и порядковые статистики, структуры данных, методы построения и анализа алгоритмов, более сложные структуры данных, алгоритмы на графах |
|
Б. Н. Иванов [10] |
Комбинаторные схемы, представление абстрактных объектов, методы подсчета и оценивания, генерация комбинаторных объектов, сортировка и поиск, введение в теорию графов (алгоритмы на графах), введение в теорию групп (приложения), элементы теории чисел |
|
А. И. Белоусов, С. Б. Ткачев [11] |
Множества и отношения, группы и кольца, полукольца и булевы алгебры, алгебраические системы, теория графов, булевы функции, конечные автоматы и регулярные языки, контекстно-свободные языки |
|
Ф. А. Новиков [12] |
Множества и отношения, алгебраические структуры, булевы функции, логические исчисления, комбинаторика, кодирование, графы, связность, деревья, циклы, независимость и покрытия, раскраска графов |
|
Р. Хаггарти [13] |
Логика и доказательство, теория множеств, отношения, функции, комбинаторика, графы, ориентированные графы, булева алгебра |
|
Д. Андерсон [14] |
Таблицы истинности, логика, доказательства, теория множеств, целые числа, функции и матрицы, алгоритмы и рекурсия, графы, теория чисел, комбинаторика и вероятность, алгебраические структуры, теория рекурсии, комбинаторные подсчеты, производящие функции, сети, теория вычислений, теория кодов, перечисление цветов, кольца, области целостности и поля, характеры групп и полугрупп |
|
И. В. Романовский [15] |
Элементы теории множеств, элементы комбинаторики, элементарная теория вероятностей, строки переменной длины, сжатие и защита информации, информационный поиск и организация информации, предикаты и отношения, теория графов, экстремальные задачи, процессы, связи дискретного и непрерывного анализа |
о стандартизации курса «дискретная математика» – 2
Условно данные учебники по времени издания можно разделить на учебники «первой волны» [2-7] и учебники «второй волны» [8-14][1]. Большинство из них написаны на основе курсов лекций, читаемых в университетах (так, во всяком случае, декларируется). Уже в первых книгах просматриваются две позиции. Первая – курс дискретной математики, чисто математический курс [5-7]. Эта концепция курса и далее развивается в книгах [8, 12, 13] и особенно в работах [11, 14]. В соответствии с установкой в курс включаются такие темы, как множества и отношения, логика, алгебраические структуры, теория чисел, теория вероятностей, конечные автоматы и регулярные языки, контекстно-свободные языки и т. д. Курс при использовании этой учебной литературы строится традиционно: лекции и практические занятия по разбору тем, решению задач. Вторая позиция, обозначенная в [2, 3] и затем развиваемая в [9, 10, 14], характеризуется тем, что в курсе рассматриваются как абстрактные структуры данных, так и различные алгоритмы, в основном сортировки и поиска. Подразумевается, что часть практических занятий должна проходить с использованием компьютера. Причины такого различия, как по содержанию, так и по методике проведения кроются, видимо, в том, что учебники первого типа ориентированы на технические университеты и курс предназначен для «постановки» математической культуры студентов, а второго типа – для классических университетов, и в курсе имеющейся математической культуре студентов придается направленность на проблемы информатики.
Определим первый ориентир рассмотрения. Курс (учебник) обязан быть компьютерно-ориентированным, то есть практически любой теоретический факт должен быть исследован, проверен с помощью его программной реализации. В таком случае инструментом педагога становится огромный методический пласт наработок, усиливающий глубину изучения материала у обучаемого. Это требование накладывает ограничения на структуру теоретического материала.
Второй ориентир определяется областью пересечения предметного поля, задаваемого учебниками вне зависимости от их ведомственной принадлежности. Книга В. Липского [4] специально не включена ни в тот, ни в другой перечень. Она является компьютерно-ориентированной, и её содержание состоит из двух больших тем: «Комбинаторика» и «Алгоритмы на графах». Естественно, рассматриваются и производящие функции как инструмент подсчета количества комбинаторных объектов. Первой темы нет в [5, 11], поверхностно затронута, несмотря на объем книги, в [9] и дана частично через методы вычисления специальных чисел в [8]. Второй темы нет в [5, 8].
Loading ...