- •Архитектуры вычислительных систем
- •Нейрокомпьютерные системы
- •2 Нейронные сети обратного распространения с непрерывной функцией активации: архитектура, алгоритмы обучения, применение.
- •3 Конструируемые нейронные сети с конкурирующими нейронами: архитектура, применение.
- •4. Обучаемые нейронные сети с конкурирующими нейронами: архитектура, алгоритмы обучения, применение.
- •Базы данных
- •1 Понятие «базы данных». Основные компоненты базы данных.
- •2 Архитектура системы баз данных.
- •3 Нормальные формы БД. Нормализация данных.
- •4 Язык SQL для работы с реляционными базами данных.
- •5 Хранимые процедуры, триггеры, транзакции.
- •Системы поддержки принятия решений
- •1 Сравнительный анализ парадигм исследования операций и принятия решений. Классификация типов проблем по Г. Саймону.
- •2 Основные элементы многокритериальной задачи принятия решения. Выявление цели и определение типа задачи. Формирование множества альтернатив, критериев, шкал.
- •Структуры данных
- •1 Временная сложность алгоритма. Сравнительный анализ алгоритмов поиска.
- •Алгоритмы поиска в неупорядоченных массивах
- •Алгоритмы поиска в упорядоченных массивах
- •Анализ алгоритма блочного поиска
- •Сортировка Шелла
- •Пирамидальная сортировка
- •Анализ пирамидальной сортировки
- •Улучшенная сортировка обменом 1
- •Анализ улучшенной сортировки обменом 1
- •Улучшенная сортировка обменом 2
- •Анализ улучшенной сортировки обменом 2
- •Анализ улучшенной сортировки обменом 2 аналогичен анали-зу улучшенной сортировки обменом 1. Порядок функций ВС этих алгоритмов в лучшем и худшем случаях одинаковый.
- •Алгоритм быстрой обменной сортировки
- •7 Структуры данных типа граф. Представление графов в памяти. Алгоритмы прохождения в «глубину» и в «ширину». Топологическая сортировка. Матрица достижимости.
- •Технология разработки программного обеспечения
- •1 Технология разработки программного обеспечения. Основные этапы на примере классического жизненного цикла.
- •2 Описание технического задания по ГОСТ.
- •3 Паттерны проектирования. Формат описания.
- •Описание паттернов.
- •Результаты применения паттернов:
- •4 Кодирование. Стандарты на кодирование. Кодирование и проектирование. Исходный код как главный проектный документ.
- •5 Рефакторинг. Цели, описание, примеры.
- •6 Системы управления версиями. Использование в проектах.
- •7 Тестирование. Виды тестирования. Разработка через тестирование.
- •Человеко-машинное взаимодействие
- •2 Применение метафор, идиом, аффордансов и стандартов в пользовательском интерфейсе. Основные принципы. Примеры.
- •4 Основные элементы пользовательского интерфейса и удобство их использования. Особенности. Рекомендации.
- •Теория языков программирования
- •3 Регулярные языки и конечные распознаватели. Использование конечных распознавателей в трансляторах.
- •4 Лексические анализаторы. Основные функции, проектирование и методы программной реализации.
- •5 Нисходящий анализ методом рекурсивного спуска.
- •6 Транслирующие грамматики. Построение нисходящих МП-трансляторов.
- •7 Грамматики польского перевода. Построение восходящих МП-трансляторов.
- •Теория вычислительных процессов
- •1 Автоматы Мили и Мура. Трансформация автоматов. Эквивалентность и минимизация.
- •2 Функциональная эквивалентность, логико-термальная эквивалентность и изоморфизм стандартных схем программ.
- •3 Стандартные и рекурсивные схемы программ. Алгоритмы трансляции.
- •4 Анализ сетей Петри с использованием дерева достижимости и матричных уравнений.
- •Объектно-ориентированное программирование
- •5 Общая характеристика классов в объектно-ориентированном программировании. Особенности реализации классов в различных объектно-ориентированных языках программирования.
- •Сети ЭВМ и телекоммуникации
- •1 Каналы передачи данных. Физический канал. Логический канал. Понятие блока данных. Пример формата блока данных любого протокола.
- •2 Структуризация сетей. Понятие и характеристики основных сетевых топологий. Структурообразующие аппаратные средства и программное обеспечение.
- •4 Характеристика протоколов IP, TCP, ARP, ICMP, POP3, SMTP.
5 Нисходящий анализ методом рекурсивного спуска.
Для СА (синтаксический анализатор) используется автомат с магазинной (стековой) памятью (сокращенно МП-автомат) – это кортеж из семи элементов P=(Q,T,Г,d,q0,Z0,F) , где
Q- конечное множество символов состояний, представляющих всевозможные состояния управляющего устройства;
T- конечный входной алфавит;
Г - конечный алфавит магазинных символов;
d- функция переходов - отображение множества Q x (T {e}) x Г в множество конечных подмножеств Q x Г* , т.е.d:Q x (T {e}) x Г -> {Q x Г*} ;
q0 Q - начальное состояние управляющего устройства;
Z0 Г- символ, находящийся в стеке в начальный момент (начальный символ);
F Q- множество заключительных состояний
Конфигурацией (текущее состояние) МП-автомата называется тройка (q,w,u) Q x T* x Г* , где
q- текущее состояние управляющего устройства;
w- неиспользованная часть входной цепочки; первый символ цепочки w находится под входной головкой; если we, то считается, что вся вхоная лента прочитана;
u- содержимое стека; самый левый символ цепочки u считается верним символом стека; если u=e, то стек считается пустым.
Начальной конфигурацией МП-автомата P называется конфигурация вида (q0,w,Z0), где w T* , т.е. управляющее устройство находится в начальном состоянии, входная лента содержит цепочку, которую нужно распознать, а в стеке есть только начальный символ Z0 (в лекциях мы как
правило использовали символ S). Заключительная конфигурация - это конфигурация вида (q,e,u), где q F, u Г* .
В таком автомате определены операции:
1) Над входной цепочкой:
-сдвиг
-держать
2) Над магазином:
-втолкнуть
-вытолкнуть
-не изменять
3) Над состоянием:
-перейти в новое состояние
-не изменять
Рассмотрим работу нисходящего распознавателя: входную цепочку можно представить в виде 2 частей: a b -|, где
a - обработанная часть цепочки (изначально пустая)
b – необработанная часть
Магазин содержит цепочку j, которая представляет собой символы языка и считается что j => *b (если так то считается что цепочка допускается). В начальный момент в магазине находится начальный нетерминал (S), и символ дна $.
Цепочку b можно представить в виде: t1 b‘ -|
Магазин можно представить в виде: t2 j‘ $
Если t1=t2, то t1 и t2 считаются обработанными и отбрасываются. Если t2 – нетерминал то его надо заменить на правую часть правила грамматики, которое определяет этот нетерминал.
Можно предложить вариант предсказывающего анализатра, когда каждому нетерминалу сопоставляется, вообще говоря, рекурсивная процедура и стек образуется неявно при вызовах этих процедур.
Процедуры рекурсивного спуска могут быть записаны, как это изображено на рисунке. В процедуре N для случая, когда имеется альтернатива N -> ui -> *e (не может быть более одной альтернативы, из которой выводится e), приведены два варианта 1.1 и 1.2. В варианте 1.1 делается проверка, принадлежит ли следующий входной символ FOLLOW(N). Если нет - выдается ошибка. Во втором варианте этого не делается, так что анализ ошибки откладывается на процедуру, вызвавшую N.
6 Транслирующие грамматики. Построение нисходящих МП-трансляторов.
Для СА (синтаксический анализатор) используется автомат с магазинной (стековой) памятью (сокращенно МП-автомат) – это кортеж из семи элементов P=(Q,T,Г,d,q0,Z0,F) , где
Q- конечное множество символов состояний, представляющих всевозможные состояния управляющего устройства;
T- конечный входной алфавит;
Г - конечный алфавит магазинных символов;
d- функция переходов - отображение множества Q x (T {e}) x Г в множество конечных подмножеств Q x Г* , т.е.d:Q x (T {e}) x Г -> {Q x Г*} ;
q0 Q - начальное состояние управляющего устройства;
Z0 Г- символ, находящийся в стеке в начальный момент (начальный символ);
F Q- множество заключительных состояний
Конфигурацией (текущее состояние) МП-автомата называется тройка (q,w,u) Q x T* x Г* , где
q- текущее состояние управляющего устройства;
w- неиспользованная часть входной цепочки; первый символ цепочки w находится под входной головкой; если we, то считается, что вся вхоная лента прочитана;
u- содержимое стека; самый левый символ цепочки u считается верним символом стека; если u=e, то стек считается пустым.
Начальной конфигурацией МП-автомата P называется конфигурация вида (q0,w,Z0), где w T* , т.е. управляющее устройство находится в начальном состоянии, входная лента содержит
цепочку, которую нужно распознать, а в стеке есть только начальный символ Z0 (в лекциях мы как правило использовали символ S). Заключительная конфигурация - это конфигурация вида (q,e,u), где q F, u Г* .
В таком автомате определены операции:
1) Над входной цепочкой:
-сдвиг
-держать
2) Над магазином:
-втолкнуть
-вытолкнуть
-не изменять
3) Над состоянием:
-перейти в новое состояние
-не изменять
Рассмотрим работу нисходящего распознавателя: входную цепочку можно представить в виде 2 частей: a b -|, где
a - обработанная часть цепочки (изначально пустая)
b – необработанная часть
Магазин содержит цепочку j, которая представляет собой символы языка и считается что j => *b (если так то считается что цепочка допускается). В начальный момент в магазине находится начальный нетерминал (S), и символ дна $.
Цепочку b можно представить в виде: t1 b‘ -|
Магазин можно представить в виде: t2 j‘ $
Если t1=t2, то t1 и t2 считаются обработанными и отбрасываются. Если t2 – нетерминал то его надо заменить на правую часть правила грамматики, которое определяет этот нетерминал.
Можно предложить вариант предсказывающего анализатра, когда каждому нетерминалу сопоставляется, вообще говоря, рекурсивная процедура и стек образуется неявно при вызовах этих процедур.
Процедуры рекурсивного спуска могут быть записаны, как это изображено на рисунке. В процедуре N для случая, когда имеется альтернатива N -> ui -> *e (не может быть более одной альтернативы, из которой выводится e), приведены два варианта 1.1 и 1.2. В варианте 1.1 делается проверка, принадлежит ли следующий входной символ FOLLOW(N). Если нет - выдается ошибка. Во втором варианте этого не делается, так что анализ ошибки откладывается на процедуру, вызвавшую N.
Перевод с математической точки зрения перевод (что собственно и есть трансляция) представляет собой множество пар, где 1 элемент – цепочка символов входного языка, 2 – цепочка символов выходного языка. Если перевод определен с помощью некоторой грамматики, то он называется – синтаксически управляемым.
Один из способов задания транслятора – транслирующая грамматика. Транс. Грамматика содержит 2 типа терминалов:
1)из которых формируется цепочка входного языка
2)из которых формируется цепочка выходного языка (так называемые символы действия)
Пример:
E -> E+T {+}
E -> T
T -> T*P {*}
… {+} и {*} и есть символы действия. Если убрать все символы действия, то получится грамматика входного языка.
Т.о. если входная грамматика принадлежит классу LL(1) грамматик, то по ней можно построить нисходящий МП-транслятор. Магазинными символами будут являться нетерминалы, терминалы и символы действия. Входными символами: терминалы и концевой маркер.
Отличия в работе следующие: если верхний магазинный символ – символ действия, то независимо от терминала во входной цепочке, необходимо выполнить операцию – выдать (обработать) символ действия, вытолкнуть его из стека, остаться на том же символе входной цепочки.
i. A→α
Если α * ε, то ВЫБОР(i) = ПЕРВ(α)
Если α * ε, то ВЫБОР(i) = ПЕРВ(α) СЛЕД(α)
Если множества выбора для любых двух правил с одинаковой левой частью не пересекаются, то грамматики относятся к классу LL(1).
Для грамматик такого вида можно построить нисходящий МП-распознаватель.
Как находить множество первых:
ПЕРВ(t) = {t}
ПЕРВ(А):
Если есть A→ε, то ε включить в множество первых.
Если есть правило A→X1X2…Xn, то в множество первых для А надо добавить множество первых для X1. Если множество первых для X1 содержит ε, то добавить к нему множество первых для X2 и т.д.
A→α
ПЕРВ(α)
Если α=X1X2…Xn, то в первые α включается множество первых для X1. Если множество первых для X1 содержит ε, то добавить к нему множество первых для X2 и т.д.
Определение множества следующих:
СЛЕД(А)
B→αAβ – в множество следующих для А надо добавить множество первых для β. Если множество первых для β содержит ε, то к множеству следующих за А надо добавить множество следующих за В.
Пример:
S->AbB
S->d
A->CAb
A->Bl
B->CSD
B->e
C->a
C->ld
|
Перв |
След |
|
|
|
S |
d,a,l,c,b |
d,-| |
|
|
|
A |
a,l,c,e |
b |
|
|
|
B |
c,e |
-|,d,b |
|
|
|
C |
a,l |
a,l,b,c |
|
|
|