Теория алгоритмов

Стоимость очного группового обучения: 1 680 руб.

Стоимость дистанционного индивидуального обучения: 2 800 руб.

Стоимость очного индивидуального или корпоративного обучения: 14 000 руб.

Требования к слушателям:

Для успешного освоения курса от слушателей требуются знания и навыки из курсов математического анализа, линейной алгебры, теории вероятностей и математической статистике, теории игр.

Аннотация:

В данном курсе рассматриваются разделы бинарных отношений и функции выбора, задачи коллективных решений, элементы теории систем и закономерности их функционирования и развития. Изучаются методы и модели теории систем, соотношения категорий типа событие, явление, поведение систем. Устанавливаются принципы разработки алгоритмов экономико-математических моделей, вводится и исследуется понятие имитационного моделирования экономических процессов.

Учебная задача дисциплины:

В результате изучения курса слушатель должен:

- знать точные формулировки основных понятий, уметь интерпретировать их на простых примерах; в том числе свободно использовать экономическую информацию для формулировки и построения алгоритмов;

- знать общие методы разработки алгоритмов имитационных моделей, иметь формировать массивы информации для электронного моделирования;

- знать общие положения разработки алгоритмов в условиях неопределенности и риска.

Тематический план учебной дисциплины

Базовые учебники:

1. Мальцеа А.И. Алгоритмы и рекурсивные функции. М. «Наука», 1985.

2. Вентцель Е.С. Исследование операций. Задачи, принципы, методология. М.: Высшая школа, 2001.

Содержание программы:

Тема 1. Бинарные отношения и функция выбора.

Бинарные отношения и их свойства. Матрицы смежности и инциденций. Специальные классы бинарных отношений. Выбор по отношению предпочтения. Теорема Эрроу.

Тема 2. Основные положения теории граф.

Понятие графа, виды графов. Матричные представления графов. Бинарные отношения и графы. Ориентированные и неориентированные графы. Компоненты связности и условие разбиения графа на компоненты связности. Паросочетание, двудольные графы, трансверсали. Теорема о существовании совершенного паросочетания. Эйлеров и Гамильтонов граф. Задача коммивояжера. Расстояние в графе, диаметр графа, центр графа и радиус графа.

Тема 3. Коллективные решения на графе.

Внутренняя и внешняя устойчивость. Ядро. Нелокальные правила принятия коллективных решений. Позиционное правило, правила, использующие мажоритарное отношение, правило использующее числовую шкалу. Правило турнирной матрицы и q-паретовское правило.

Тема 4. Теория построения алгоритмов.

Машина Тьюринга. Рекурсивные функции. Вычислимость и разрешимость алгоритма. Алгоритмы дискретной оптимизации.

Оценка качества освоения дисциплины

Вопросы к зачету:

1. Бинарные отношения и их свойства.

2. Матрицы смежности и инциденций.

3. Специальные классы бинарных отношений.

4. Выбор по отношению предпочтения.

5. Теорема Эрроу.

6. Понятие графа, виды графов. Матричные представления графов.

7. Бинарные отношения и графы.

8. Ориентированные и неориентированные графы.

9. Компоненты связности и условие разбиения графа на компоненты связности.

10. Паросочетание, двудольные графы, трансверсали.

11. Теорема о существовании совершенного паросочетания.

12. Эйлеров и Гамильтонов граф.

13. Задача коммивояжера.

14. Расстояние в графе, диаметр графа, центр графа и радиус графа.

15. Внутренняя и внешняя устойчивость. Ядро графа.

16. Нелокальные правила принятия коллективных решений.

17. Позиционное правило.

18. Правила, использующие мажоритарное отношение.

19. Правило использующее числовую шкалу.

20. Правило турнирной матрицы и q-паретовское правило.

21. Машина Тьюринга.

22. Рекурсивные функции.

23. Вычислимость и разрешимость алгоритма. Алгоритмы дискретной оптимизации.