Е. А. Перминов методическая система обучения дискретной математике в аспекте интеграции образования монография

Пример. Формальная теория палиндромов в алфавите {a, b}. 
Палиндромом является слово, которое одинаково читается слева 

ются, например, слова «топот» и «потоп». 

A4 = bb. 

1) A| –aAa; 2) A| –bAb. 

непустые слова – палиндромы в алфавите. 

Пример теоремы 

Доказательство. Рассмотрим аксиому A2 = b. На основании пра- 

вила вывода A| –aAa при A = b получаем B1 = aba. По правилу вывода 

следует abababa. 

достаточное количество подобных примеров. 

зываний и аксиоматическом методе построения формальных теорий: 
геометрии Евклида, Лобачевского, векторного пространства, теории 

дать яркими историческими экскурсами (фактами из жизни Н. И. Ло- 
бачевского, К. Ф. Гаусса, Я. Больяй, Э. Галуа и др.). 

245 

При первоначальном обучении дискретной математике можно 
ограничиться только примерами «палиндромного» типа, выводом про- 

и ассоциативно-коммутативного кольца, рассмотрением аксиом про- 
извольного векторного пространства (с последующими различными 

Важнейшим в изучении понятий алгоритма и алгоритмической 
разрешимости является «дискретный» подход, заключающийся в ре- 

графов, комбинаторного анализа, булевых функций и других разделов 
ДМ). Напомним, что под алгоритмической разрешимостью понимает- 

ных задач). При этом задача является алгоритмически разрешимой 
или неразрешимой, если существует или, соответственно, не существу- 

основе понятия алгоритмически разрешимой задачи сформировалось 
понятие исполнителя, было уточнено само понятие алгоритма. В ре- 

горитмов, являющиеся ключевыми для понимания сути и корректно- 
сти вычислений на компьютере. 

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

Сначала на основе ряда занимательных, практических примеров 
и задач, рассмотрения вращений правильных многоугольников изу- 

пятиэлементного поля P и таблицы истинности алгебры высказыва- 
ний B. Вычисляются значения буквенных выражений алгебр Z4, P, B 

Далее предлагаются упражнения на доказательство тождеств 
и решение уравнений (в том числе с параметрами) в каждой из алгебр 

доказательства тождеств и решений уравнений. 

246 

Вводятся персонажи Ленивкин, Смекалкин и совсем не знаю- 
щий математику Кнопкин [126, 155]. Рассматриваются различные ал- 

задач в кольце целых чисел Z и поле рациональных чисел Q, алгорит- 
мы вычислений и решения простых уравнений в алгебрах Z4, P, B. 

правильно составленным условием; нерешенные задачи; задачи, ко- 
торые не имеют решения; задачи с бесконечным и конечным числом 

Q, Z4, P, B на микрокалькуляторах, различающихся перечнем выпол- 
няемых операций и размером табло. Выясняется возможность вычис- 

ненных при вычислении точного ответа. Приводятся примеры вычис- 
лений Кнопкина, Ленивкина и Смекалкина, алгоритмы решений квад- 

Далее рассматриваются устройство и команды машины Поста, 
виды и примеры программ, массивы и их объединения (программы 

ножения и деления натуральных чисел). 

и линейкой, нахождения наибольшего общего делителя двух нату- 
ральных чисел, решения системы двух линейных уравнений с двумя 

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

1. Понятие алгоритма. Определенность, массовость, результатив- 
ность алгоритма. 

куляторы с возможностями вычислений x + y, x – y, 1 : x ≠ 0), 
xy + x + y + 1 и др. 

га. Программа сложения натуральных чисел. Понятие конечного ав- 

томата. Примеры конечных автоматов. Понятие исполнителя. Уточ- 

247 

нение понятия алгоритма. Эквивалентные и эффективные алгоритмы 
и их примеры. От машины Поста и Тьюринга к ЭВМ. 

Разрешимость уравнений в радикалах. Разрешимость уравнений в ал- 
гебрах Z, Q, Z4, P, B. Распознавание конечных изоморфных (равных) 

5. Проблема разрешимости. Разрешающие алгоритмы. Полино- 
миальное и экспоненциальное время работы алгоритма. Новые при- 

Естественно, с учетом профиля обучения дискретной математи- 
ке возможны сокращения или модификации предложенной методики. 

студентам следует дать классификацию видов задач, кратко представ- 
ленную в п. 4.2. Вначале необходимо предложить задачи с неверно 

шения. Затем перейти к задачам, которые имеют решение на выбран- 
ном математическом языке, и к первоначальным задачам на понятие 

с бесконечным и конечным числом действий (исполнителя). Благода- 
ря таким задачам студенты впервые познакомятся с проблемой суще- 

дить проблему разрешимости уравнений в алгебрах Z, Q, Z4, P, 
B. Далее нужно рассмотреть задачи на составление эффективного ал- 

личные виды микрокалькуляторов, машину Поста и т. д. 

ют занимательные, практические и теоретико-модельные задачи: за- 
дачи на проблему изоморфизма, проблему разрешимости (существо- 

дачи на выразимость на языке первого порядка тех или иных понятий; 
задачи на составление алгоритмов по всем изученным ранее разделам 

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

248 

Итак, основными особенностями методики обучения студентов 
педагогических направлений подготовки математическому языку, по- 

дующие. Во-первых, рассматриваются понятия алфавита, формулы (сло- 
ва), аксиомы, правила вывода, теоремы, доказательства, формальной 

осуществляется поэтапное преемственное изучение перечисленных 
понятий. В-третьих, при изложении материала учитываются психоло- 

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

глубокому профильному обучению студентов математическому язы- 
ку, понятиям алгоритма и алгоритмической разрешимости, используя 

Содержательная часть этого раздела может быть использована 
при построении элективных курсов по математике и информатике для 

нятий и их свойств.

249