Otvety

Билет №1. Абстрактный автомат. Формы представления и моделирование автомата.

Билет №2. Абстрактный автомат. Автоматы Мура, Миля.

Определение. Абстрактным конечным автоматом называется шестерка объектов

A={S, s0, X, Y, φ,ψ},

где S – конечное непустое множество состояний; s0€S – начальное состояние;

X – конечное непустое множество входных сигналов; Y – множество выходных сигналов;

φ : SˣX →S– функция переходов;

ψ : SˣX →S – функция выходов.

По способу формирования функций выходов среди синхронных автоматов выделяют автоматы Мили и автоматы Мура // (первый источник)

Вавтомате Мили функция выходов ψ определяет значение выходного символа по классической схеме абстрактного автомата. Она является двухаргументной и символ y (t) в выходном канале обнаруживается только при наличии символа во входном канале x (t). Функции перехода и выхода для автомата Мили можно записать в виде

s(t+h) φ(s(t),x(t));

y(t+h) ψ(s(t),x(t)), где h – длительность такта.

Зависимость выходного сигнала только от состояния представлена в автоматах типа Мура.

Вавтоматах этого типа функция выходов определяет значение выходного символа только по одному аргументу – состоянию автомата. При этом символ y (t) в выходном канале существует все время, пока автомат находится в состоянии s (t ). Для автомата Мура функции перехода и выхода можно записать как

s(t+h) φ(s(t),x(t)); y(t+h) ψ(s(t)).

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

//(второй источник)

Автомат Мура (абстрактный автомат второго рода) в теории вычислений — конечный автомат, выходное значение сигнала в котором зависит лишь от текущего состояния данного автомата, и, не зависит напрямую, в, отличие от автомата Мили, от входных значений.

Формальное определение:

Автомат Мура может быть определен как кортеж из 6 элементов, включающий: - множество внутренних состояний S (внутренний алфавит);

- начальное состояние S0;

- множество входных сигналов X (входной алфавит);

- множество выходных сигналов Y (выходной алфавит); - функция переходов Φ(z, x).

- Для любого автомата Мура существует эквивалентный ему автомат Мили и наоборот. Любой автомат Мура путем добавления ряда внутренних состояний может быть преобразован в автомат Мили.

Способы задания:

- Диаграмма — изображённый на плоскости ориентированный граф, вершины которого взаимно однозначно соответствуют состояниям автомата, а дуги — входным символам. - Таблица переходов-выходов, в ячейках которой для каждой пары значений аргументов х(t), s(t) проставляются будущие внутренние состояния s(t+1). Значения выходных сигналов y(t) представляются в отдельном столбце.

Таблица переходов

Автомат Мили (англ. Mealy machine) — конечный автомат, выходная последовательность которого (в отличие от автомата Мура) зависит от состояния автомата и входных сигналов. Это означает, что в графе состояний каждому ребру соответствует некоторое значение (выходной символ). В вершины графа автомата Мили записываются выходящие сигналы, а дугам графа приписывают условие перехода из одного состояния в другое, а также входящие сигналы.

Автомат Мили можно описать пятеркой (Q,X,Y,f,g), где Q - множество состояний автомата, X - множество входных символов, Y - множество выходных символов, q=f(Q,X) - функция состояний, y=g(Q,X) - функция выходных символов.

Кодировка автомата Мили:

Вершина (операторная или логическая), стоящая после вершины "Начало", а также вход вершины "Конец" помечается символом S1, вершины, стоящие после операторных помечаются символом Sn (n=2,3..).

Матрица функций переходов

Билет №3.Абстрактный автомат. Переводы автомата Мура в автомат Миля и обратно.

1.3.4. Переход от А Мура к А Мили

Задан автомат

SA={AA, ZA, WA, A, A, a1A} ,

где

AA = {а1 , :, аm , : , aM}, ZA= {z1 , :, zf , :, zF},

WA = {w1 , :, wg , : , wG} ;

A - реализует отображение AA х Z A в AA, A - отображение A A на WA, а a1A = a1 - начальное состояние.

Рис. 1-6. Граф автомата Мура S5 Рис. 1-7. Иллюстрация перехода от модели Мура к модели Мили

Построим автомат Мили

SB={AB, ZB, WB, B , B, a1B},

у которого

AB = AA = {а1 , :, аm , : , aM}, ZB= ZA = {z1 , :, zf , :, zF},

WB = WA = {w1 , :, wg , : , wG}; B = A, a1B = a 1A = a1

Функцию выходов Мили B определим следующим образом. Если в автомате Мура

A(am,zf)=as и A(as)=wg, то в автомате Мили B(am,zf)=wg.

Переход от автомата Мура к автомату Мили при графическом способе задания иллюстрируется рис.1-7: выходной сигнал (wg), записанный рядом с вершиной (аs), переносится на все дуги, входящие в эту вершину. На рис. 1-8 приведен граф автомата Мили S6, эквивалентного автомату Мура S3 (рис. 1-4).

При табличном способе задания автомата SA таблица переходов автомата SB совпадает с таблицей переходов SA, а таблица выходов SB получается из таблицы переходов заменой символа as, стоящего на пересечении строки zf и столбца am, символом выходного сигнала wg, отмечающего столбец as , в таблице переходов автомата SA.

Из самого способа построения автомата Мили SB очевидно, что он эквивалентен автомату Мура SA. Действительно, если некоторый водной сигнал zf Z поступает на вход автомата SA, находящегося в состоянии аm, то он перейдет в состояние аs= A(аm,zf) и выдаст входной сигнал wg= A(аs). Но соответствующий автомат Мили SB из состояния am, также перейдет в состояние as, поскольку B(аm,zf) = A(аm,zf) = аs- и выдаст тот же выходной сигнал wg согласно способу построения функции В. Таким образом, для входной последовательности длины один поведение автоматов SA и SBполностью совпадает. По индукции нетрудно показать, что любое входное слово конечной длины, поданное на входы автоматов SA и SB , установленных в состояния am, вызовет появление одинаковых выходных слов и, следовательно, автоматы SA и SA аm эквивалентны.

Рис. 1-8. Автомат Мили S6эквивалентный автомату Мура S5 Рис. 1-9. Построение множества As

1.3.5. Переход от А Мили к А Мура

Прежде чем рассмотреть трансформацию автомата-Мили в автомат Мура, наложим на автомат Мили следующее ограничение: у автомата не должно быть преходящих состояний. Под преходящим будем понимать состояние, в которое при представлении автомата в виде графа не входит ни одна дуга, но которое имеет по крайней мере одну выходящую дугу (пример - состояние a1 на рис. 1-3). Итак, пусть задан автомат Мили

SA={AA, ZA, WA, A, A, a1A} ,

где

AA = {а1 , :, аm , : , aM}, ZA= {z1 , :, zf , :, zF},

WA = {w1 , :, wg , : , wG};

A - реализует отображение AA х ZA в AA, A - отображение AA на WA , а a1A = a1 - начальное состояние.

Построим автомат Мура

SB={AB, ZB, WB, B, B, a1B},

у которого

ZB= ZA = {z1 , :, zf , :, zF},

WB = WA = {w1 , :, wg , : , wG};

Для определения АB каждому состоянию as AA поставим в соответствие множество As всевозможных пар вида (аs,w g), где wg - выходной сигнал, приписанный входящей в аs

дуге (рис. 1-9): Аs={(as, wg) | (am, zf) = as и (am, zf) = wg}

Число элементов в множестве Аs равно числу различных выходных сигналов на дугах автомата S A, входящих в состояние as.

Множество остояний автомата SB получим как обединение множеств AS (s=1,:,M):

Рис. 1-10. Иллюстрация перехода от модели Мили к модели Мура

Функции выходов B и переходов B определим слудиющим образом. Каждому состоянию автомата Мура SB , представляющему собой пару вида (as, Wg), поставим в

соответствие выходной сигнал Wg. Если в автомате Мили SA был переход а1B (аm, zf) = Wk , то в SB (рис. 1-10) будет переход из множества состояний Am , порождаемых am , в состояние (as, Wk) под действием входного сигнала zf.

В качестве начального состояния а1B можно взять любое из состояний множества А1, которое порождается начальным состоянием а1 автомата SA. Напомним, что при сравнении реакции автоматовSA и SB на всевозможные входные слова не должен учитываться выходной сигнал в момент времениt=0, связанный с состоянием а1B автомата

SB .

Билет №4.Абстрактный автомат. Автоматы без выхода. Распознающие автоматы.

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

Билет №5. Абстрактный автомат. Минимизация автоматов.

//Лекции Теперь перейдём к описанию процесса минимизации конечного автомата.

1.Мы начнём с поиска и удаления всех недостижимых состояний.

2.Затем мы должны найти такое разбиение множества состояний автомата, чтобы каждое подмножество содержало неразличимые состояния, т.е. если s и t принадлежат некоторому подмножеству, то для всех a из (s,a) и (t,a) также принадлежат этому подмножеству. Для этого мы разобьём множество состояний на два подмножества: F и S-F.

3.В дальнейшем, мы попытаемся разбить каждое из подмножеств, соблюдая указанное выше условие. Если возникает ситуация, при которой мы не можем разбить никакое множество состояний, то мы заканчиваем процесс разбиения.

4.В результате мы получим некоторый набор множеств состояний S1…Sk. Каждое из Si содержит только неразличимые состояния.

5.Наконец, внесём в множество состояний минимизированного автомата по одному представителю каждого из множеств Si. На этом процесс завершается.

Алгоритм минимизации детерминированного конечного автомата (эквивалентный начальному)

1, Находим и удаляем из начального автомата все недостижимые и непродуктивные состояния.

2, Все состояния конечного автомата разделяются на классы эквивалентности (0).

1.Все состояния, которые являются конечными в автомате (qi in F)

2.Все состояния, не вошедшие в F

3, Строим новое одно эквивалентное разбиение, выделив те состояния, которые по одинаковым символам переходят в 0 эквивалентные.

4, Повторяется шаг 3, последовательно создавая n+1 эквивалентное состояние по n эквивалентным, увеличивая так число классов эквивалентности.

5, Алгоритм заканчивается, когда n+1 эквивалентные состояния совпадают с n эквивалентными.

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

В множество F' автомата внесём те состояния, которые содержат хотя бы одно состояние из начального.

Пример.

Задан избыточный детерминированный KA=( ,Q,Q0, ,F)

={0,1}

Q={A,B,C,D,E,F,G}

F={D,E} : (d)

d(A,0)={B}

d(A,1={C}

d(B,1)={D}

d(D,1)={E}

d(E,1)={D}

d(D,0)={C}

d(E,0)={B}

d(C,1)={E}

d(G,1)={E}

d(G,0)={F}

d(F,0)={G}

d(F,1)={D}

Минимизация.

Первый шаг. Удаляем недоститжимые и непродуктивные состояния. В состояния F и G нельзя попасть, в них нет стрелок – они недостижимые.

Строим 0 эквивалентные:

0-> (D,E), остальные → A, B, C

1-> (DE)(BC)(A) — из них можно попасть через один и тот же символ в (D,E)

2->(DE)(BC)(A)

Алгоритм завершён.

Строим новый автомат с состояниями (DE)(BC)(A)

Билет №6. Абстрактный автомат. Эквивалентность автоматов.

//Интернет

Состояние q автомата М и состояние q1 автомата М1 считаются эквивалентными, если оба автомата, получив одну и ту же (любую) входную последовательность символов, перерабатывают ее в одинаковую выходную последовательность.

Автоматы М и М1 называются эквивалентными, если для каждого состояния автомата М существует эквивалентное ему состояние автомата М1 и наоборот.

Другими словами, эквивалентные автоматы реализуют одинаковые преобразования, но могут иметь различное число внутренних состояний.

Понятие эквивалентности состояний применимо и к одному автомату(формально можно считать то М и М1 совпадают). Для одного автомата эквивалентными будут различные состояния, через которые одна и та же последовательность символов преобразуется в одинаковую выходную.

Автомат, эквивалентный заданному и имеющий наименьшее из всех возможных число состояний называется минимальным.

//Лекции Эквивалентность конечных автоматов

Определение. Два автомата M1=(Q1, , 1 ,q10 ,F1) и M1=(Q2, , 2 ,q20 ,F2) называются эквивалентными, если они распознают один и тот же язык над алфавитом .

Определение. Два состояния si и sj – эквивалентными, если x * верно, что (qi,x)F (qj,x) F. Очевидно, что если два состояния si и sj эквивалентны, то a * состояния (si,a) и (sj,a) также эквивалентны.

Кроме того, т.к. в детерминированном конечном автомате переход (q, ) может возникнуть только для конечного состояния q, то никакое заключительное состояние не может быть эквивалентно незаключительному состоянию. Таким образом, если мы предположим, что начальные состояния автоматов эквивалентны, то мы можем получить и другие пары эквивалентных состояний. Если в одну из таких пар попадет заключительное состояние вместе с незаключительным, то si и sj неэквивалентны. Напишем алгоритм разбиения множества состояний на классы эквивалентности:

Добавить (q10, q20) в Список;

Список = 0; /* Множество эквивалентных множеств */ for each (q in Q1 +Q2) { Добавить {q} в Список; } while (есть пара (qi, qj), входящая в Список) {

Удалить пару (qi, qj) из Списка; Пусть A и A' - такие множества, что

qi A и qj A’; if (A != A') {

A = A + A';

for (a from ) { Добавить ( (qi,a), (qj,a) в Список; }

}

}

Таким образом, мы получим разбиение множества Q1 Q2 на множества эквивалентных состояний, если q10 и q20 – эквивалентны. Теперь осталось проверить, что никакое из этих множеств не содержит заключительное и незаключительное соcтояния. Если это верно, то автоматы эквивалентны.

Билет №7. Язык HTML. Основные операторы. Основные теги:

<html></html> - Указывает программе просмотра страниц что это HTML документ. <head></head> - Определяет место, где помещается различная информация не отображаемая в теле документа. Здесь располагается тег названия документа и теги для поисковых машин.

<body></body> - Определяет видимую часть документа Теги оглавления:

<title></title> - Помещает название документа в оглавление программы просмотра страниц Атрибуты тела документа:

<body bgcolor=?> - Устанавливает цвет фона документа, используя значение цвета в виде RRGGBB - пример: FF0000 - красный цвет.

<body text=?> - Устанавливает цвет текста документа, используя значение цвета в виде RRGGBB - пример: 000000 - черный цвет.

Теги для форматирования текста: <b></b> - Создает жирый текст <i></i> - Создает наклонный текст Форматирование:

<p> - Создает новый параграф <br> - Вставляет перевод строки. Таблицы :

<table></table> - Создает таблицу.

<tr></tr> - Определяет строку в таблице.

<td></td> - Определяет отдельную ячейку в таблице.

<th></th> - Определяет заголовок таблицы (нормальная ячейка с отцентрованным жирным текстом)

Билет №8. Обучающие программы. Модели обучения. Билет №9. Обучающие программы. Этапы обучения. Билет №10. Обучающие программы. Типы упражнений.

Билет №11. Обучающие программы. Клиент серверные системы.

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

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

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

Понятие архитектуры клиент-сервер в системах управления предприятием связано с делением любой прикладной программы на три основных компонента или слоя. Этими тремя компонентами являются:

компонент представления (визуализации) данных; компонент прикладной логики; компонент управления базой данных.

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

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

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

Билет №12. Машинная графика. Методы кодировки: ВМР – точечная, площадями, векторная графика.

Компьютерная графика – совокупность методов для преобразования данных с помощью ЭВМ в графические представления и наоборот. компьютерной графики – это система автоматизации (СА) подготовки, преобразования и хранения различной информации с помощью ЭВМ. компьютерной графики - совокупность средств и приемов автоматизации, обработки, кодирования и декодирования информации.

Геометрическое моделирование – описание предметов и явлений, обладающих геометрическими свойствами.

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

Bit MaP image (BMP) — универсальный формат растровых графических файлов, используется в операционной системе Windows. Этот формат поддерживается многими графическими редакторами, в том числе редактором Paint. Рекомендуется для хранения и обмена данными с другими приложениями.

Наиболее известными растровыми форматами являются BMP, GIF и JPEG форматы. В формате BMP (от BitMaP) задается цветность всех пикселов изображения. При этом можно выбрать монохромный режим с 256 градациями или цветной с 16 256 или 16 777 216 цветами. Этот формат требует много памяти.

у bmp точечная структура, то есть, в файле идут сначала данные о палитре, а потом о цвете каждой точки.

Точечный формат. Сохраняет информации без какой-либо компрессии. Поэтому и файлы получаются очень большими. Однако, если сохранять 1 цветные изображения, то можно добиться и достаточно малого размера. Читается на всех компьютерах на Windows - платформе. При сохранении в это изображение качество не теряются. В bmp изображение не архивируется, поэтому получаются очень большие файлы.

Векторная графика.

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

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

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

Билет №13. Машинная графика. Графические средства языка Паскаль.

Графические средства языка Паскаль Графический экран состоит из маленьких точек - пикселов, каждый из которых закрашен

в какой-либо цвет. Для работы в графическом режиме существует обширная библиотека процедур и функций, находящихся в модуле Graph. Структуру модуля и правила создания пользовательских модулей мы рассмотрим несколько позже. Чтобы использовать стандартные модули, вам достаточно знать лишь один оператор:

USES модуль , ... ;

Этот оператор должен быть первым оператором в программе, в нем перечисляются все модули, используемые данной программой; в частности, чтобы работать с графикой, вам достаточно записать USES Graph;. Теперь рассмотрим графические средства, предоставляемые этим модулем. Здесь описаны только наиболее употребительные и наиболее полезные, по мнению автора, средства. Тот, кто хочет изучить все возможности модуля Graph, может сделать это, пользуясь справочной службой среды Turbo Pascal (или

Borland Pascal).

1.PROCEDURE InitGraph(VAR GraphDriver,GraphMode: Integer; PathToDriver: STRING); -

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

2.PROCEDURE CloseGraph; - закрывает графический режим.

3.FUNCTION GetMaxX : Integer; .

4.FUNCTION GetMaxY : Integer; - возвращают соответственно номер самого правого и самого нижнего пиксела экрана. Пикселы нумеруются от 0 до GetMaxX слева направо и от

0до GetMaxY сверху вниз.

5.PROCEDURE SetBkColor(Color: Word); - устанавливает фоновый цвет, после ее выполнения весь экран будет закрашен в цвет Color. Цветовая палитра также зависит от типа монитора и выбранного графического режима, но стандартная палитра для цветного монитора включает 16 цветов [ 0 – Black, 1 – Blue, 2 – Green, 3 – Cyan, 4 – Red, 5 – Magenta, 6 – Brown, 7 – LightGray, 8 – DarkGray, 9 – LightBlue, 10 – LightGreen, 11 – LightCyan, 12 – LightRed, 13 – LightMagenta, 14 – Yellow, 15 – White].

6.PROCEDURE SetViewPort(x1,y1,x2,y2: Integer; Clip: Boolean); - устанавливает графическое окно. x1,y1,x2,y2 - координаты соответственно левого верхнего и правого нижнего углов окна. После выполнения этой процедуры пикселы будут отсчитываться от левого верхнего угла окна. Логический параметр Clip определяет, следует ли усекать изображения на границах окна. Выполнять эту процедуру вовсе не обязательно, по умолчанию графическое окно занимает весь экран.

7.PROCEDURE ClearDevice; - закрашивает экран фоновым цветом.

8.PROCEDURE PutPixel(X,Y: Integer; Color: Word); - закрашивает пиксел с координатами

X,Y цветом Color.

9.FUNCTION GetPixel(X,Y: Integer): Word; - возвращает цвет пиксела с координатами X,Y.

10.PROCEDURE SetColor(Color : Word); - устанавливает цвет линий, все выводимые на экран линии будут иметь цвет Color до выполнения следующей процедуры SetColor.

11.PROCEDURE SetLineStyle(LineStyle, Pattern, Thickness: Word); - устанавливает стиль линий, действует для всех выводимых линий до выполнения SetLineStyle с другими аргументами. Параметр LineStyle может принимать следующие значения:

0- SolidLn - сплошная линия;