Задание 1. Математическая логика и теория автоматов
Конечный автомат задан графом, определенным в задании 1 контрольной работы. Вершины графа отожествляются с состояниями автомата таким образом, что множество состояний Q = {q1, q2,…, qn}. Переход автомата из одного состояния в другое осуществляется под воздействием множества входных сигналов X = {x1, x2, x3, x4}. Переходы определяются законом отображения Г вершин графа, причем каждому переходу соответствует только одна из букв множества X. При задании графа эти буквы расставить произвольно. Автомат позволяет вырабатывать выходные сигналы Y = {y1, y2, y3}:
y1 – переход из состояния qi в состояние qi (петля);
y2 – переход из состояния qi в qj при i < j;
y3 – переход из состояния qi в qj при i > j.
Осуществить структурный синтез конечного автомата. Реализацию осуществить на элементах, указанных в табл. 2.3, в соответствии с номером варианта. Обязательной является минимизация реализуемых функций.
Таблица 16
| № варианта | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| Тип элемента | И НЕ | И ИЛИ НЕ | И НЕ | ИЛИ НЕ | И НЕ | И ИЛИ НЕ | И НЕ | ИЛИ НЕ | И ИЛИ НЕ | И НЕ |
| Тип триггера | D | JK | T | D | RS | RS | D | JK | T | D |
| № варианта | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 |
| Тип элемента | И НЕ | И ИЛИ НЕ | ИЛИ НЕ | И ИЛИ НЕ | И НЕ | ИЛИ НЕ | ИЛИ НЕ | И ИЛИ НЕ | И НЕ | ИЛИ НЕ |
| Тип триггера | RS | JK | T | RS | JK | D | RS | T | D | RS |
| № варианта | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 |
| Тип элемента | ИЛИ НЕ | И ИЛИ НЕ | И НЕ | ИЛИ НЕ | И ИЛИ НЕ | И НЕ | ИЛИ НЕ | И ИЛИ НЕ | И НЕ | ИЛИ НЕ |
| Тип триггера | RS | T | JK | RS | D | T | JK | RS | T | D |
|
|
|
Рассмотрим пример перехода от графа, заданного аналитически, к аналитическому способу задания конечного автомата. Пусть в задаче 1 (контрольная работа №1) граф задан следующим образом:
X = {x1, x2, x3, x4, x5}, Гx1 = {x2, x3, x5}, Гx2 = {x1}, Гx3 = {x2, x4}, Гx4 = {x1, x3, x5}, Гx5 = {x1, x5}. При переходе к конечному автомату множество состояний Q = {q1, q2, q3, q4, q5}. Закон отображения состояний запишется следующим образом:
Гq1 = {q2(x1/y2), q3(x3/y2), q5(x4/y2)}, Гq2 = {q1(x3/y3)} (читается: автомат переходит из состояния q2 в состояние q1, если на входе действует буква x3 входного алфавита, при этом на выходе появляется буква y3 выходного алфавита);
Γq3={q2(x1/y3),q4(x2/y2}; Γq4={q1(x2/y3),q3(x1/y3),q5(x4/y2)}, Γq5={q1(x2/y3),q5(x3/y1)}/
Обобщенная таблица переходов и выходов соответствующего конечного автомата представлена в табл. 17.
Таблица 17
| X | Q | q1 | q2 | q3 | q4 | q5 | |
| X1 | q2/y2 | - | q2/y3 | q3/y3 | - | ||
| X2 | - | - | - | q1/y3 | 11/y3 | ||
| X3 | q3/y2 | q1/y3 | q4/y2 | - | q5/y1 | ||
| X4 | q5/y2 | - | - | q5/y2 | - | ||
10.5. Методические материалы, определяющие процедуры оценивания знаний, умений, навыков и / или опыта деятельности, характеризующих этапы формирования компетенций, содержатся в Положениях «О текущем контроле успеваемости и промежуточной аттестации студентов ГУАП, обучающихся по программы высшего образования» и «О модульно-рейтинговой системе оценки качества учебной работы студентов в ГУАП».
|
|
|
Методические указания для обучающихся по освоению дисциплины
Методические указания для обучающихся по освоению лекционного материала (если предусмотрено учебным планом по данной дисциплине)
Основное назначение лекционного материала – логически стройное, системное, глубокое и ясное изложение учебного материала. Назначение современной лекции в рамках дисциплины не в том, чтобы получить всю информацию по теме, а в освоении фундаментальных проблем дисциплины, методов научного познания, новейших достижений научной мысли. В учебном процессе лекция выполняет методологическую, организационную и информационную функции. Лекция раскрывает понятийный аппарат конкретной области знания, её проблемы, дает цельное представление о дисциплине, показывает взаимосвязь с другими дисциплинами.
Планируемы результаты при освоении обучающимся лекционного материала:
|
|
|
- получение современных, целостных, взаимосвязанных знаний, уровень которых определяется целевой установкой к каждой конкретной теме;
- развитие профессионально–деловых качеств, любви к предмету и самостоятельного творческого мышления.
- появление необходимого интереса, необходимого для самостоятельной работы;
- получение знаний о современном уровне развития науки и техники и о прогнозе их развития на ближайшие годы;
- научится методически обрабатывать материал (выделять главные мысли и положения, приходить к конкретным выводам, повторять их в различных формулировках);
- получение точного понимания всех необходимых терминов и понятий.
Лекционный материал может сопровождаться демонстрацией слайдов и использованием раздаточного материала при проведении коротких дискуссий об особенностях применения отдельных тематик по дисциплине.
Структура предоставления лекционного материала может быть такой:
Лекция 1. Эффективная вычислимость функции. Уточнение понятия алгоритма. Примитивная рекурсия. Примитивно-рекурсивные функции. Оператор минимизации. Частично-рекурсивные функции. Общерекурсивные функции.
Примитивная рекурсивность и общерекурсивность некоторых арифметических функций. Тезис Чёрча. Словарные множества и функции.
|
|
|
Лекция 2. Операции над словарными функциями. Словарная примитивная рекурсия. Компоненты машины Тьюринга: внешний и внутренний алфавиты, команды и программа. Конфигурация машины Тьюринга. Распознавание применимости машины Тьюринга к начальной конфигурации. Понятие функции, вычислимой по Тьюрингу.
Лекция 3 Примеры машин Тьюринга, вычисляющих некоторые арифметические функции. Тезис Тьюринга. Действия над машинами Тьюринга.
Композиция машин Тьюринга.
Лекция 4. Основные понятия и определения. Способы задания. Автоматы Мили и Мура. Переход от автомата Мили к эквивалентному автомату Мура и наоборот. Абстрактный и структурный автоматы. Минимизация числа состояний конечного автомата. Понятие элементарного автомата. Общая структурная схема конечного автомата.
Лекция 5. Постановка задачи синтеза автоматов. Структурно полные системы автоматов. Теорема о структурной полноте. Понятие о структурном синтезе конечных автоматов. Основные этапы синтеза структурного автомата.
Лекция 6. Временное представление сигналов. Классификация сигналов. Простейшие непрерывные сигналы. Преобразование Лапласа. Преобразование Фурье. Свойства преобразований Фурье и Лапласа.
Лекция 7. Разложение произвольного сигнала по заданной системе функций. Теорема Котельникова. Представление сигналов в виде ряда Котельникова. Дискретные представления сигналов, полиномы Чебышева, функции Уэлша.
Методические указания для обучающихся по прохождению практических занятий (если предусмотрено учебным планом по данной дисциплине)
Практическое занятие является одной из основных форм организации учебного процесса, заключающаяся в выполнении обучающимися под руководством преподавателя комплекса учебных заданий с целью усвоения научно-теоретических основ учебной дисциплины, приобретения умений и навыков, опыта творческой деятельности.
Целью практического занятия для обучающегося является привитие обучающемся умений и навыков практической деятельности по изучаемой дисциплине.
Планируемые результаты при освоении обучающемся практических занятий:
- закрепление, углубление, расширение и детализация знаний при решении конкретных задач;
- овладение новыми методами и методиками изучения конкретной учебной дисциплины;
- выработка способности логического осмысления полученных знаний для выполнения заданий;
Функции практических занятий:
- познавательная;
- развивающая;
По характеру выполняемых обучающимся заданий по практическим занятиям подразделяются на:
- ознакомительные, проводимые с целью закрепления и конкретизации изученного теоретического материала;
- аналитические, ставящие своей целью получение новой информации на основе формализованных методов;
Формы организации практических занятий определяются в соответствии со специфическими особенностями учебной дисциплины и целями обучения. Они могут проводиться:
- в не интерактивной форме (выполнение упражнений, решение типовых задач, решение ситуационных задач и другое).
Методика проведения практического занятия может быть различной, при этом важно достижение общей цели дисциплины.
Дата добавления: 2021-03-18; просмотров: 113; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!