О преподавании математических основ информатики в педвузе

Математика является, с одной стороны, естественной областью приложений информатики, а с другой – тем звеном, которое связывает её с другими науками. Учитывая дискретный характер хранения, передачи и обработки информации,  именно дискретная математика  обслуживает запросы современной информатики. Изучение методов  дискретной математики  студентами педвузов, будущими учителями информатики, обеспечивает необходимую  фундаментализацию  образования, при которой студенты способны не только использовать информационные технологии, но и объяснять своим будущим ученикам, на каких математических моделях они основаны. 

В  государственных образовательных стандартах по специальности «информатика» элементы дискретной математики, разнесены по различным учебным дисциплинам (математическая логика, дискретная математика, теоретические основы информатики и др.), что затрудняет целостное представление об идеях и методах дискретной математики.

Одной из основополагающих объединительных идей для различных разделов дискретной математики может быть конструктивная  парадигма. Рассмотрим три примера.

1.    Комбинаторика. Во многих комбинаторных задачах возникает необходимость в генерации таких объектов как  перестановки или сочетания в определенном порядке. Кроме, общеизвестного, лексикографического порядка возможны и другие способы построения каждого последующего объекта из предыдущего. Эти способы могут быть привлекательны тем, что позволяют эффективно определять номер объекта по его свойствам (например, по составу компонент) и наоборот. Причем номер объекта не зависит от мощности исходного запаса, как при лексикографическом порядке.
2.    Функции алгебры логики. Здесь процесс построения одних функций из других задается языком формул. При этом естественным образом  возникает вопрос о множестве функций, получаемых при этом,  а также о множествах функций, суперпозициями которых можно задать любую функцию. Соответствующие задачи, известные как задачи о  выразимости и полноте, традиционно рассматриваются в классических университетах, но, к сожалению, до сих пор не включены в образовательные стандарты для педвузов по дискретной математике [1].
3.    Графы.  Очевидно, что для учителей информатики важно умение решать задачи с использованием разнообразных структур данных. Эти структуры описываются обычно с помощью теоретико-графовых моделей. Важно отметить, что и здесь оказывается плодотворным конструктивный подход, основанный на построении одних графов из других. Конструктивные описания классов графов, замкнутых относительно операций, сохраняющих заданные характеристические свойства графов, позволяют, с одной стороны, лучше понять природу этих свойств, а с другой, - строить графы с заранее заданными свойствами. При этом хорошо иллюстрируются возможности сжатия информации за счет перехода от непосредственного задания графов к заданию лишь алгоритмов их построения.

Интересно сопоставление  конструктивных описаний  замкнутых классов графов и функций алгебры логики по числу замкнутых классов, по количеству и составу элементов в порождающих базисах. Подобный анализ позволяет сравнивать между собой по сложности основные модельные объекты дискретной математики.

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

Следует также выделять и использовать связи  между различными разделами дискретной математики и математической кибернетики. Так, например, методы решения линейных рекуррентных соотношений с постоянными коэффициентами можно применить при оценке значений функции Шеннона для  схем из функциональных элементов в универсальных методах синтеза.

Отметим в заключение, что преподавание математических основ информатики в педвузах должно быть в практической части более адаптировано к специальности, к использованию новых информационных технологий. Необходимо кроме традиционных для математических дисциплин видов учебной деятельности таких, как лекции и практические занятия, активно использовать компьютерные практикумы по различным разделам дискретной математики.