Вопросы и задачи по курсу

Вопросы.

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

2. Классические задачи комбинаторной оптимизации: задача о рюкзаке и задача коммивояжера (симметричная задача коммивояжера, асимметричная задача коммивояжера, метрическая задача коммивояжера).

3. Задачи построения расписаний и их классификация.

4. Задача построения статико-динамических расписаний.

5. Задача построения расписания обменов по шине с централизованным управлением для схемы с подциклами (на примере стандарта MIL-STD 1533В).

6. Задача построения расписания обменов по шине с централизованным управлением для схемы без подциклов (на примере стандарта MIL-STD 1533В).

7. Алгоритм направленного случайного поиска с парной пробой. Алгоритм наилучшей пробы.

8. Алгоритм направленного случайного поиска с возвратом при неудачном шаге.

9. Алгоритм направленного случайного поиска с пересчетом при неудачном шаге.

10. Алгоритм направленного случайного поиска с линейной экстраполяцией.

11. Алгоритм статистического градиента.

12. Принципы построения алгоритмов случайного направленного поиска с самообучением. Самообучение методом исключения. Покоординатное экспоненциальное обучение. Алгоритм покоординатного самообучения с произвольным законом изменения вероятности.

13. Принципы построения алгоритмов случайного направленного поиска с самообучением. Способы решения проблемы передетерминирования алгоритма, повышения чувствительности алгоритма к выбору наилучшего направления, способы устранения положительной обратной связи.

14. Концепция построения алгоритмов имитации отжига. Общая схема алгоритмов и проблемы построения алгоритмов для решения задач условной оптимизации.

15. Асимптотическая сходимость алгоритмов имитации отжига: описание поведения алгоритма имитации отжига цепью Маркова, теоремы о сходимости, скорость сходимости.

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

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

18. Параллельный алгоритм имитации отжига для построения статических многопроцессорных расписаний: разбиение исходного пространства решений на области, операции преобразования расписания внутри области, распределение областей по узлам вычислительной системы.

19. Простой генетический алгоритм (алгоритм Холланда).

20. Теория схем. Гипотеза строительных блоков.

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

22. Муравьиные алгоритмы: концепция построения алгоритмов (биологическая модель), общая схема работы муравьиных алгоритмов.

23. Модификации муравьиных алгоритмов: максиминный алгоритм, алгоритм с поглощением феромона, совместное использование с алгоритмами локального поиска, элитные муравьи, ранговый алгоритм, список кандидатов.

24. Муравьиный алгоритм для решения задачи построения статико-динамических расписания.

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

26. Методика статистической обработки результатов экспериментов по исследованию свойств алгоритмов.

Задачи

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

2. Доказать NP-трудность задачи построения расписания обменов по шине с централизованным управлением для схемы с подциклами.

3. Доказать NP-трудность задачи построения расписания обменов по шине с централизованным управлением для схемы без подциклов.

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

5. Построить алгоритм направленного случайного поиска с возвратом при неудачном шаге и обосновать его свойства для решения задачи о рюкзаке.

6. Построить алгоритм направленного случайного поиска с возвратом при неудачном шаге и обосновать его свойства для решения симметричной задачи коммивояжера.

7. Построить генетический алгоритм и обосновать его свойства для решения задачи о рюкзаке.

8. Построить генетический алгоритм и обосновать его свойства для решения симметричной задачи коммивояжера.

9. Построить генетический алгоритм и обосновать его свойства для решения асимметричной задачи коммивояжера.

10. Построить генетический алгоритм и обосновать его свойства симметричной метрической задачи коммивояжера.

11. Построить алгоритм имитации отжига и обосновать его свойства для решения задачи о рюкзаке.

12. Построить алгоритм имитации отжига и обосновать его свойства для решения симметричной задачи коммивояжера.

13. Построить алгоритм имитации отжига и обосновать его свойства для решения асимметричной задачи коммивояжера.

14. Построить алгоритм имитации отжига и обосновать его свойства для решения симметричной метрической задачи коммивояжера.

15. Построить муравьиный алгоритм и обосновать его свойства для решения задачи о рюкзаке.

16. Построить муравьиный алгоритм и обосновать его свойства для решения асимметричной задачи коммивояжера.