- •Архитектуры вычислительных систем
- •Нейрокомпьютерные системы
- •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.
|
Выбор |
|
|
1 |
a,l,c,b |
|
|
2 |
d |
|
|
3 |
a,l |
|
|
4 |
c,b |
|
|
5 |
c |
|
|
6 |
-|,d,b |
|
|
7 |
a |
|
|
8 |
l |
|
|
7 Грамматики польского перевода. Построение восходящих МП-трансляторов.
Восходящий МП-транслятор можно построить только по грамматике польского перевода. Это транслирующая грамматика, в которой символы действия самые правые в правой части.
Если задана транслирующая грамматика, не польского перевода с внедренными действиями, тоже модно преобразовать в грамматику польского перевода.
В→<ß{x}>γ
<ß{x}>→ ß{x}
Транслятор строить также, как и распознаватель. Символьные действия выполняются при свертке правила, которому он принадлежит.
Обратная польская нотация (ОПН) (Обратная польская запись, Постфиксная нотация, Бесcкобочная символика Лукашевича, Польская инверсная запись, Полиз) — форма записи математических выражений, в которой операнды расположены перед операторами.
Описание
Отличительной особенностью обратной польской нотации является то, что все аргументы (или операнды) расположены перед знаком операциии. В общем виде запись выглядит следующим образом:
Запись набора операций состоит из последовательности операндов и знаков операций. Операнды в выражении при письменной записи разделяются пробелами.
Выражение читается слева направо. Когда в выражении встречается знак операции, выполняется соответствующая операция над двумя последними встретившимися перед ним операндами в порядке их записи. Результат операции заменяет в выражении последовательность еѐ операндов и еѐ знак, после чего выражение вычисляется дальше по тому же правилу.
Результатом вычисления выражения становится результат последней вычисленной операции.
yao.png
8. Восходящие методы обработки языков.
Распознаватель типа «перенос-свѐртка»
Такой распознаватель задаѐтся таблицей.Строка –магазинный символ,столбец-вх символ.
Множество магазинных символов –все симв грамматики(терминалы и нетерминалы).Вх символытерминалы.В клетках записывается перенос или опознание.В строке,которой соответсвует символ «+» добавляется операция «опознать».
Нужно определить,если в магазине,S-допустить.Процедура опознания включает процедуру свѐртки.
В зависимости от ситуации один и тот же симв может иметь разный код,и код верх магазина симв конкретного опред правила ,по кот. нужно выполнить свертку,поэтому проц.опознания нету,строиться граф ситуацию.
По последней свѐртке можно определить,доп-ся цепочка или нет.
Распознаватель типа «перенос-опознание»
T(табл)[m(машинный символ),x]=П(перенос)
Перенос нужно выполнять,если есть правила A→αmβ,x ПЕРВ(β)
Рассмотрим начальную ситуацию.Переносить можно только те символы,которые принадлежат множеству первых для начального нетерминала.
T[m,x]=ОП,если A→αm,x СЛЕД(А)
ОП-опозн.допускает конечное множество цепочек(предст.собой регулярный язык)Введѐм S‘→S – будет концевом маркере.Такая грамматика называется пополненной.
Самый простой класс грамматик,для которых строится расп «перенос-опознание»без конфликтов:- в одной клетке и П и ОП,нет2х правил А→αβ,В→β
Группа,в которой нет такой ситуации,называется безсуффикснойПО грамматикой.Особенность нет ε-правил.
Грамматики предшествования позволяют описывать более широкий класс языков чем ЛЛ1грамматики, однако менее чем SLR-грамматики. Алгоритм разбора грамматик предшествования относится к восходящим методам разбора, т.е. дерево разбора строится снизу вверх (листья и "ветки" соединяются в более крупные "ветки"). Работает алгоритм по принципу "переноссвертка".
Центральное место во всем, что касается грамматик предшествования занимают отношения предшествования (бинарные отношения между символами полного словаря грамматики и допустимыми символами магазина). Фактически это три отношения: < = > (сворачивается раньше, сворачивается вместе, сворачивается после).
Класс простого предшествования определяется очень просто: грамматика является грамматикой простого предшествования, если для любых двух символов полного словаря существует не более одного отношения предшествования. Неформально, это значит, что в каждой клетке матрицы предшествования должно находится не более одного отношения.
Если ПОД(s) ПОД(с)=(не пересекаются),то можно определить какое правило может применяться.
Такие грамматики наз-ся простыми грамматиками стратегии предшествования.
Самый широкий класс,для которого можно построить распознаватель «переносопознание».Порядка преобразования произвольной грамматики в грамматику смешанной стратегии предшественников нет.Любую гр. можно преобразовать в группу,которая не допускает конфликтов типа «перенос-опознание.
Конфликт возможен,если А→αx;B→βx>γ
Множество следующих за А пересекается с множеством первых для γ.Можно сделать x в конце <βx>→βx.Процедуру опознания не всегда можно построить.