Примерный перечень вопросов к государственному экзамену
По специальности САПР
(2012-2013уч.год)
Лингвистическое и программное
Обеспечение САПР
1. Проблематика разработки ЛО САПР. Понятие входного языка САПР и языкового процессора. Обобщенная модель процесса компиляции. Способы реализации языковых процессоров САПР.
2. Языки программирования и формальные языки. Понятие транслятора и компилятора. Фазы компиляции. Инструменты и технологии разработки и реализации языков программирования.
3. Способы задания формальных языков (ФЯ). Задание ФЯ при помощи грамматик и распознавателей (привести примеры грамматик и
распознавателей).
4. Соответствия между способами задания языков. Соответствия между КС-грамматиками и МП-автоматами. Построение МП-автомата, моделирующего левые выводы по заданной КС-грамматике (построить МП-автомат для конкретной КС-грамматики).
5. Понятие о переводе (трансляции). Модели трансляторов (конечные преобразователи и преобразователи с магазинной памятью).
6. Определение синтаксического разбора. Модели анализаторов. Построение левого анализатора по заданной КС-грамматике.
7. Общая характеристика процесса сканирования. Методика конструирования сканера (характеристика каждого этапа построения сканера и применяемые методы). Представление результатов сканирования.
8. Классы лево- и право- анализируемых грамматик (определения). LL(k)- грамматики, их свойства и роль в разработке языков программирования. Приведение грамматик к LL -форме (устранение рекурсии и факторизация). Привести пример устранения левой рекурсии.
9. Общая модель процесса компиляции. Понятие синтаксического анализа. Общая характеристика моделей и методов детерминированного синтаксического анализа. Модель LL(k)- анализатора.
10. Основные функции семантического анализа. Способы представления промежуточной программы. Применение моделей синтаксически управляемой трансляции (СУ-перевода) в разработке анализаторов.
Разработка САПР
1. Интерфейс программы Autocad
2. Ядро Parasolid в T-Flex
3. Панели инструментов программы Autocad
4. Сравнение программ МКЭ
5. Анимация в Blender
6. Обзор возможностей пакета Abacus Student
7. Программирование в среде Visual LISP
8. Проект освещения NanoCAD-Электро
9. Основы метода конечных элементов
Интеллектуальные подсистемы в САПР
1. Формальные системы. Способ описания, основная терминология. Логики высказываний как формальная система. Прямая и обратная дедукция. Метод резолюций для логики высказываний.
2. Модель логики предикатов первого порядка. Основные понятия логики предикатов. Логика предикатов как формальная система.
3. Унификация в логике предикатов первого порядка. Приведение формул логики предикатов к множеству предложений. Метод резолюций для логики предикатов первого порядка.
4. Продукционные модели. Методы построения вывода в этих моделях. И/ИЛИ графы.
5. Семантические сети. Основные концепции, используемые в семантических сетях. Поиск решения в семантических сетях.
6. Фреймы и сценарии. Примеры фреймов и сценариев.
7. Нечеткие знания, виды нечеткостей. Нечеткость, связанная с недетерминированным выводом.
8. Нечеткие знания, виды нечеткостей. Нечеткости, связанные с недостоверностью знаний. Метод Байеса. Метод MYCIN.
9. Задача планирования. Планирование в пространстве состояний и планирование в пространстве задач. Алгоритмы и методы построения планов.
10. Экспертные системы (ЭС). Основные составляющие ЭС и их назначение. Статические и динамические ЭС. Этапы разработки ЭС и их сущность.
Геометрическое моделирование в САПР
1. Аффинные преобразования в пространственном и плоскостном случае геометрического моделирования. Основные типы и свойства аффинных преобразований. Композиция аффинных преобразований. Аффинные преобразования в локальной системе отсчета. Применение аффинных преобразований для деформаций геометрических моделей.
2. Основные принципы аппроксимации кривой сплайнами в геометрическом моделировании. Принципы построения составной кривой при помощи соединения («склейки») или суперпозиции частичных сплайнов.
3. Минимально-достаточная степень полинома для аппроксимации участка кривой (частичного сплайна) между двумя опорными точками в геометрическом моделировании. Требуемый порядок аппроксимирующей функции для обеспечения условий непрерывности и гладкости составной сплайн-кривой, кривизны и кручения участка кривой.
4. Составные сплайны Безье в геометрическом моделировании. Обеспечение условий непрерывности и гладкости. Уравнения «склейки» частичных сплайнов в векторной и параметрической форме для классического сплайна Безье. Характеристическая ломаная кривой Безье. Случаи получения кривых переменной вогнутости и самопересечения кривой
5. Базисные сплайны (В-сплайны) в геометрическом моделировании. Свойства частичного В-сплайна. Составные В-сплайны (NURBS). Принцип суперпозиции В-сплайнов при построении составных кривых. Случай использования нормированных В-сплайнов. Весовые коэффициенты.
6. Основные способы построения геометрических моделей пространственных объектов инструментальными средствами компьютерной графики. Полигональное представление поверхности на этапе визуализации в инструментальных комплексах.
7. Метод каркасного геометрического моделирования поверхностей пространственных объектов инструментальными средствами компьютерной графики.
8. Метод твердых тел геометрического моделирования пространственных объектов инструментальными средствами компьютерной графики.
9. Метод геометрического моделирования поверхностей пространственных объектов инструментальными средствами компьютерной графики при помощи плоских кривых (лофтинг). Метод геометрического моделирования поверхности вращения и метод выдавливания как частные случаи лофтинга.
10. Методы геометрического моделирования поверхностей пространственных объектов инструментальными средствами компьютерной графики при помощи сплайн-структур. Геометрическое моделирование поверхностей при помощи двухпараметрических сплайнов Безье (patch-моделирование). Геометрическое моделирование поверхностей при помощи пространственных (двухпараметрических) В-сплайнов (NURBS).
Объектно-ориентированное программирование
1. Перечислить и дать характеристику основным причинам сложности программного обеспечения. Общие признаки любой сложной системы; приемы борьбы со сложностью ПО.
2. Перечислить и дать характеристику основным разновидностям стилей (парадигм) программирования. Роль объектно-ориентированной парадигмы. Основные и дополнительные элементы объектной модели.
3. Ссылки в языке С++, использование ссылок. Отличие ссылок от указателей. Передача аргументов функций по ссылке. Перегрузка функций; правила перегрузки.
4. Общее понятие класса языка С++. Классы как абстрактные типы данных. Синтаксис описания класса. Виды членов класса. Управление доступом к членам класса. Инкапсуляция. Интерфейс и реализация класса. Объекты (экземпляры) класса и способы их создания.
5. Конструкторы и деструкторы класса. Виды конструкторов класса: конструктор по умолчанию, копирующий конструктор, конструкторы преобразования типа, прочие конструкторы. Правила вызова конструкторов различных видов. Вызов деструктора.
6. Перегрузка операций для классов. Назначение и способы перегрузки. Принципы и правила перегрузки операций. Пример перегрузки операции «=». Рекомендации по перегрузке операций; правильные форматы перегруженных операций.
7. Перечислить и дать характеристику видов отношений между классами. Привести примеры для каждого вида отношений.
8. Отношение между классами типа «наследование». Отличия наследования от агрегации. Иерархия наследования. Синтаксис наследования. Открытое и закрытое наследование. Назначение «защищенных» (protected) членов базового класса. Виртуальные функции и их назначение. Полиморфизм. Виртуальные деструкторы и правила их использования. Чисто виртуальные функции и абстрактные классы. Наследование интерфейса и наследование реализации.
9. Концепция параметризуемых типов (шаблонов) в языке С++. Шаблоны классов. Различия между шаблонами и классами. Синтаксис описания шаблона. Создание объекта шаблонного класса (инстанцирование шаблона). Шаблоны функций. Связь между шаблонами функций и перегрузкой.
10. Понятие исключения (особой ситуации). Механизм обработки исключений. Синтаксические конструкции языка для обработки исключений. Различение особых ситуаций. Имена особых ситуаций. Группирование исключений. Повторная генерация исключений; перехват всех исключений.
Структуры и алгоритмы обработки данных
1. Линейные списки – стеки, очереди, деки. Набор процедур для работы со связанным стеком, очередью.
2. Кольцевые списки. Многосвязные списки, примеры применения.
3. Древовидная структура, основные понятия. Способы обхода бинарного дерева.
4. Дерево поиска. Включение элементов. Удаление элементов из дерева поиска.
5. В-деревья, их свойства, построение. Индексирование массивов данных. Индексные деревья.
6. Применение бинарных деревьев. Кодирование и сжатие данных. Кодовые деревья, дерево Хаффмена.
7. Сортировка. Методы вставок и обмена. Метод Шелла. Быстрая сортировка. Обменная поразрядная сортировка.
8. Сортировка. Методы выбора и слияния. Простой, квадратичный выбор. Выбор из дерева. Двухпутевое слияние. Метод слияния списков.
9. Алгоритмы поиска данных. Последовательный, двоичный, блочный, интерполяционный, Фибоначчиев поиск.
10. Хеширование, хеш-функции. Способы разрешения коллизий.