Элективные курсы являются неотъемлемыми компонентами вариативной системы образовательного процесса на ступенях основного общего и среднего (полного) общего образования, обеспечивающими успешное профильное и профессиональное самоопределение обучающихся.
Профессиональное самоопределение — самостоятельный выбор профессии, осуществляемый в контексте социализации личности в результате анализа человеком своих внутренних ресурсов, в том числе и своих способностей, и соотнесение их с требованиями профессии.
Теория автоматов имеет широкие возможности применения: проектирование систем логического управления; обработка текстов и построение компиляторов; спецификация и верификация систем взаимодействующих процессов; языки описания документов и объектно-ориентированных программ; оптимизация логических программ др.
Ценность дисциплины «Элементы теории автоматов» заключается в построении учащимися в ходе обучения математических моделей. При этом они переводят практические задачи на математический язык, составляют алгоритмы решения, данных задач, учатся интерпретировать результат и оценивать его, проверяя практикой. Особенно важно изучение данного курса в процессе профильного обучения. Ведь одна из задач профильного обучения — первичная подготовка школьников к избранному ими роду деятельности, к будущей профессиональной деятельности.
Данный элективный курс предназначен для учащихся 11 классов, он является предметно-ориентированным и рассчитан на 18 часов.
Он может быть включен в естественно-математический профиль, поскольку расширяет и углубляет знания школьников по математическим наукам. При этом курс поддерживает изучение информатики на профильном уровне. Материал, с нашей точки зрения, должен содержать три раздела:
1. Понятие автомата.
2. Способы задания абстрактных и структурных автоматов.
3. Основные типы задач, возникающие в связи с понятием конечного автомата.
Условием, позволяющим правильно построить учебный процесс, является актуализация знаний, приобретенных на предыдущих занятиях.
По нашему мнению, основными формами проведения занятий должны стать: традиционные формы занятий (лекции и семинар); индивидуальная (групповая) деятельность учащихся (учебные игры, дискуссии); защита реферативных работ. Реферативная деятельность учащихся позволит удовлетворить их индивидуальные потребности и интересы, выявить возможности школьников, то есть максимально разнообразить обучение.
Чтобы оценить степень усвоения учащимися материала дисциплины и заинтересовать их выполнять задания, необходимо предоставить слушателю курса объективную информацию об уровне его знаний и умений, а, следовательно, и об оценке, которую он получит по итогам.
Не следует забывать и о возможностях, которые предоставляют для поддержания познавательного интереса школьников современные информационные технологии. Например, в процессе преподавания элективного курса рекомендуется широко использовать компьютерные презентации, созданные как учителем, так и учащимися.
Подводя итог вышесказанному, мы сформулировали следующие цели элективного курса:
1. Дать первоначальное представление о целях и основных методах теории автоматов;
2. Способствовать развитию творческих способностей старшеклассников, логического мышления учащихся, формированию положительной мотивации к получению знаний;
3. Способствовать профессиональной ориентации учащихся.
Примерная программа курса «Элементы теории автоматов»
1. Вводное занятие (1ч) Основные понятия и определения, что изучает теория автоматов.
2. Методы задания автоматов (1ч) Теоретико-множественное представление автоматов. Табличная форма. Графовая форма задания абстрактных автоматов. Матричная форма.
3. Эквивалентные автоматы (3ч) Реакция автоматов. Математические модели автоматов: модель Мили и модель Мура. Преобразование автоматов Мура в эквивалентные автоматы Мили. Преобразование автоматов Мили в эквивалентные автоматы Мура.
4. Абстрактный С-автомат (совмещенный) (1ч) Математические модели автоматов: модель Мили и модель Мура, модель совмещенного С-автомата. Отличие С-автомата от моделей Мили и Мура.
5. Типы конечных автоматов (1ч) Понятие конечного автомата, разновидности конечного автомата: с конечной памятью, с конечным запоминанием, автомат без потери информации, связный и несвязный автомат, инициальный автомат.
6. Начальные (стандартные) языки (1ч) Начальные языки: язык регулярных выражений алгебры событий, язык логических схем, язык граф-схем алгоритмов, язык схем алгоритмов.
7. Автоматные языки (1ч) Таблицы переходов и выходов, матрицы переходов и выходов, граф автомата.
8. Язык алгебры логики (булевой алгебры) (2ч) Двоичный алфавит. Высказывание как начальное понятие алгебры логики, типы высказываний. Построение языка регулярных выражений.
9. Язык временных диаграмм (1ч) Дискретные сигналы. Формы дискретных сигналов. Потенциал. Импульсный сигнал.
10. Основные типы задач, возникающие в связи с понятием конечного автомата (5ч) Задачи: классификации автоматов; анализа и синтеза автоматов; способов задания автоматов; полноты элементарных автоматов; минимизации автоматов; эквивалентных преобразований автоматов.
11. Итоговое занятие (1ч)
Тест «Методы задания автоматов»
1. Автомат задан в табличной форме. Представьте его в виде графа.
|
|
u1 |
u2 |
u3 |
u4 |
|
|
a1 |
a2 |
a3 |
a4 |
|
z1 |
a2 |
a2 |
- |
a1 |
|
z2 |
- |
a3 |
a4 |
- |
|
z3 |
a4 |
a1 |
a2 |
a2 |
В) Нет правильного ответа.
2. Для автомата Мили заданы таблицы переходов (табл.1) и выходов (табл.2). Построить граф автомата и его матричную форму задания.
|
Таблица 1 |
Таблица 2 |
||||||
|
z/a |
a1 |
a2 |
a3 |
z/a |
a1 |
a2 |
a3 |
|
z1 |
a2 |
a1 |
a1 |
z1 |
u3 |
u1 |
u4 |
|
z2 |
a3 |
a3 |
a2 |
z2 |
u2 |
u3 |
u2 |
3. Автомат представлен в матричной форме
Задать автомат в виде графа и в табличной форме.
4. На рисунке дан граф автомата Мура. Представьте его в теоретико-множественной форме.
А) A={a1, a2, a3}; Z={z1, z2}; W={u1, u2, u3}; δ: a2=δ(a1,z1); a1=δ(a2,z1); a3=δ(a2,z2); a1=δ(a3,z2); a2=δ(a3,z1); λ: u3=λ(a1,z1); u1=λ(a2,z2); u2=λ(a3,z3).
Б) A={a1, a2, a3}; Z={z1, z2}; W={u1, u2, u3}; δ: a2=δ(a1,z1); a1=δ(a2,z1); a3=δ(a2,z2); a1=δ(a3,z1); a2=δ(a3,z1); λ: u3=λ(a1); u1=λ(a2); u2=λ(a3).
В) A={a1, a2, a3}; Z={z1, z2}; W={u1, u2, u3}; δ: a2=δ(a1,z1); a1=δ(a2,z1); a3=δ(a2,z2); a1=δ(a3,z2); a2=δ(a3,z1); λ: u3=λ(a1); u1=λ(a2); u2=λ(a3).
5. Автомат представлен в теоретико-множественной форме: A={a1, a2, a3}; Z={z1, z2}; W={u1, u2}; δ: a3=δ(a1,z2); a1=δ(a2,z1); a3=δ(a2,z2); a2=δ(a3,z1); a1=δ(a3,z2); λ: u1=λ(a1); u2=λ(a2); u2=λ(a3).
Дайте его табличную форму описания.
Литература:
- Брауэр В. Введение в теорию конечных автоматов.- М.: Радио и связь, 1987,-392с.
- Карпов Ю. Г. Теория автоматов.-СПб.: Питер, 2002,-204с.
- Кудрявцев В. Б., Алешин С. В., Подколзин А. С. Введение в теорию автоматов.-М.: Наука, 1985,-320с.
- Математическая энциклопедия. Ред. коллегия: И. М. Виноградов (гл. ред.) [и др.]. Т.1 — М.: Советская энциклопедия, 1977. — 1152 стб.
- Трахтенброт Б. А., Барздинь Я. М. Конечные автоматы (поведение и синтез).-М.: Наука, 1970,-400с.
- Тюрин С. В. Элементы теории автоматов (Часть 1): Учебное пособие. Воронеж: Воронеж. гос. техн. ун-т, 2002. 98 с.
- Пентус А. Е., Пентус М. Р. Математическая теория формальных языков. БИНОМ. Лаборатория знаний, Интернет университет информационных технологий — ИНТУИТ.ру, 2006,-248с.
- Хопкрофт Дж.Э., Мотвани Р., Ульман Дж.Д. Введение в теорию автоматов, языков и вычислений, 2-у изд.-М.: Вильямс, 2002,-528с.
