Элементы теории алгоритмов




ВОПРОСЫ

по курсу «Математическое обеспечение конструкторского

И технологического проектирования с применением САПР»

Введение

1. Автоматизация конструирования РЭС – составная часть научно-технического процесса, основные аспекты АК.

2. Взаимосвязь конструкторского этапа проектирования со схемотехническим и системотехническим этапами.

3. Математическое обеспечение (МО) САПР, специальная и инвариантная части.

4. Требования к МО САПР: универсальность, алгоритмическая надежность, точность, затраты машинного времени, используемая память.

5. Способы повышения экономичности МО: учет разряженности матриц, исследование сложных систем по частям, микромоделирование, событийность анализа, рациональное использование эвристических способностей человека.

Элементы теории множеств

6. Понятия конечного и бесконечного множеств, подмножества.

7. Действия над множествами. Объединение и пересечение двух и более множеств, разность, дизъюнктивная сумма множеств.

8. Универсальное множество, дополнение множества, разбиение множеств.

9. Упорядоченное множество (кортеж).

10. Прямое произведение и степень множеств.

11. Соответствие и отображение множеств.

12. Отношение, свойства отношений, операции над отношениями.

Элементы теории расплывчатых множеств

13. Расплывчатые (нечеткие) множества.

14. Равенство расплывчатых множеств, подмножество и дополнение.

15. Операции над расплывчатыми множествами.

16. Произведение, степень, концентрация и растяжение расплывчатых множеств.

17. Расплывчатые отношения.

18. Расплывчатая и лингвистическая переменные.

19. Расплывчатый алгоритм и его основные инструкции.

Элементы математической логики

20. Двузначная и многозначная логика.

21. Булевы переменные и функции.

22. Логические функции одной и двух переменных.

23. Зависимости между булевыми функциями.

24. Высказывания. Простые и составные высказывания.

25. Представление логических функций.

26. Алгебра высказываний, нормальной формы логических выражений, совершенные формы.

27. Законы булевой алгебры, тождества и упрощения формул.

Элементы теории графов

28. Понятие графа, элементы графа, типы графов.

29. Части графа (дополнение, суграф, кусок графа, надграф, сверхграф).

30. Изоморфность графов.

31. Маршрут, цепь, простая цепь.

32. Типы циклов и условия их существования (Эйлера, Гамильтона, простой, сложный, минимальный, максимальный). Их прикладное значение.

33. Деревья, лес, остров, прадерево.

34. Способы задания графов. Матричный способ задания оргафов и неографов (матрицы смежности, инцидентности, связности, длин).

35. Действия над графами: объединение, пересечение и вычитание графов, заданных в аналитической и матричной формах. Их прикладное значение.

36. Метрика графов, матрицы расстояний и геометрия. Их прикладное значение.

37. Экстремальные (характеристические) числа графа: цикломатическое, хроматическое, внутренней и внешней устойчивости. Метод Магу в оценке экстремальных чисел. Их прикладное значение.

38. Понятие клики в графе. Число внутренней полноты.

39. Планарность графов, критерии планарности.

40. Графы Понтрягина-Куратовского. Понятия расширения и сжатия графов.

41. Гипотеза о четырех красках. Понятия толшины графа и числа планарности.

42. Алгоритм Бадера в оценке планарности.

43. Кратчайший путь в графе. Алгоритм Форда.

44. Задача Штейнера в построении кратчайшего дерева.

45. Гиперграф и способы его представления. Понятия цепи, цикла, дерева и раскраски гиперграфа.

46. Кенигово представление гиперграфа.

47. Расплывчатые (нечеткие) графы.

Элементы теории алгоритмов

48. Понятие алгоритма, виды алгоритмов.

49. Общая, прикладная и структурная теория алгоритмов.

50. Понятия алфавита, алфавитного оператора.

51. Способы задания алфавитных операторов.

52. Кодирующие отображения, коды, кодирование и его обратимость.

53. Основные свойства алгоритмов, машина Тьюринга.

54. Полиноминальные, экспоненциальные, детерминированные и недетермини-

рованные алгоритмы.

55. Методы оценки алгоритмов: сложность и временная сложность алгоритма.

56. Задачи на допустимость и оптимальность. N, NP и NPC – задачи.

57. Операторные алгоритмы Ван Хао.

58. Операторные алгоритмы Ляпунова, логические схемы алгоритмов.

59. Алгоритм Маркова.

60. Блок-схемный метод алгоритмизации.

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

 

ЛИТЕРАТУРА

1. Курейчик В.М. Математическое обеспечение конструкторского и технологического проектирования с применением САПР: Учеб. Для вузов. – М.: Радио и связь, 1990.

2. Деньдобренко Б.Н., Малика А.С. Автоматизация конструирования РЭА. – М.: Высшая школа, 1980.

3. Мактас М.Я. Алгоритмические методы конструирования РЭА. – Саратов: Изд-во СГУ, 1983.

4. Мактас М.Я. Математические основы автоматизированного проектирования в примерах и задачах: Учеб. пособие, - Ульяновск: УлГТУ, 1995.

5. Морозов К.К., Одиноков В.Г., Курейчик В.Н. Автоматизированное проектирование конструкций радиоэлектронной аппаратуры: Учебное пособие для вузов. – М.: Радио и связь, 1983.

6. Петренко А.И., Тетельбаум А.Я. Формальное конструирование ЭВА. – М.: Сов. Радио, 1979.

7. Савельев А.Я., Овчинников В.А. Конструирование ЭВМ и систем. – М.: Высшая школа, 1984.

8. Куземин А.Я. Конструирование и микроминиатюризация ЭВА. – М.: Радио и связь, 1985.

9. Колосов В.Г., Мелехин В.Ф. Проектирование узлов и систем автоматики и вычислительной техники. – Л.: Энергоатомиздат, ЛО, 1983.

10. Алипов Н.В. Задачник по автоматизации конструкторского проектирования РЭА и ЭВА. – М.: Высшая школа, 1986.

11. Автоматизированное конструирование монтажных плат РЭА: Справочник специалиста. Под ред. Л.П. Рябова. – М.: Радио и связь, 1986.





©2015-2017 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Нарушение авторских прав и Нарушение персональных данных

Обратная связь

ТОП 5 активных страниц!