Главная страница 1
скачать файл



Правительство Российской Федерации
федеральное государственное автономное образовательное учреждение высшего профессионального образования
"Национальный исследовательский университет
"Высшая школа экономики"

Факультет бизнес-информатики



Программа дисциплины

Теория алгоритмов и эволюционные вычисления
для направления 080500.62 Бизнес-информатика

подготовки бакалавра


Автор программы: В.В.Морозенко, к.ф.-м.н., доцент, vmorozenko@hse.ru

Одобрена на заседании кафедры информационных технологий в бизнесе

«20» января 2012 г.


И.о. зав. кафедрой __________________________________О.Л. Викентьева

Утверждена Учебно-методическим Советом НИУ ВШЭ - Пермь

«01» марта 2012 г.
Председатель ______________________________________ Г.Е. Володина
Пермь, 2012
Настоящая программа не может быть использована другими подразделениями университета и другими вузами без разрешения кафедры-разработчика программы.

1.Область применения и нормативные ссылки


Настоящая программа учебной дисциплины устанавливает минимальные требования к знаниям и умениям студента и определяет содержание и виды учебных занятий и отчетности для дисциплины «Теория алгоритмов и эволюционные вычисления», изучаемой на втором курсе бакалавриата по направлению «Бизнес-информатика» в НИУ ВШЭ – Пермь.

Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления подготовки 080500.62 – Бизнес-информатика, изучающих дисциплину «Теория алгоритмов и эволюционные вычисления».

Программа разработана в соответствии с:


  • Образовательным стандартом государственного образовательного бюджетного учреждения высшего профессионального образования «Государственный университет – Высшая школа экономики», в отношении которого установлена категория «Национальный исследовательский университет» по направлению подготовки 080500.62 Бизнес-информатика (уровень подготовки: Бакалавр). Утверждён 02.07.2010 г. (протокол № 15);

  • Учебным планом по направлению подготовки 080500.62 Бизнес-информатика, утвержденным в 2010 г.

2.Цели освоения дисциплины


Целями дисциплины «Теория алгоритмов и эволюционные вычисления» являются:

В области обучения - подготовка в области основ гуманитарных, социальных, экономических, математических и естественнонаучных знаний, получение высшего профессионально профилированного (на уровне бакалавра) образования, позволяющего выпускнику успешно работать в сфере проектирования архитектуры предприятия, стратегического планирования развития ИС и ИКТ управления предприятием, организации процессов жизненного цикла ИС и ИКТ управления предприятием, аналитической поддержки процессов принятия решений для управления предприятием, обладать универсальными и предметно-специализированными компетенциями, способствующими его социальной мобильности и устойчивости на рынке труда.

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

А также - изучение важнейших разделов теории алгоритмов, методов анализа сложности алгоритмов и обоснования их корректности, методов разработки алгоритмов для решения сложных вычислительных задач и оценивания их эффективности. Освоение дисциплины должно обеспечить базовые знания, которые дадут возможность выпускнику успешно работать в сфере организации процессов жизненного цикла ИС и ИКТ, аналитической поддержки процессов принятия решений для управления предприятием, обладать универсальными и предметно-специализированными компетенциями, способствующими его социальной мобильности и устойчивости на рынке труда. Программа дисциплины нацелена на формирование организованности, трудолюбия, ответственности, способности к саморазвитию, повышению своей квалификации и мастерства.

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

Для достижения поставленной цели при изучении дисциплины решаются следующие задачи:



  • познакомить студентов с основами теории алгоритмов, их математическими моделями;

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

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

  • дать представление об эволюционных вычислениях, как эффективном методе решения сложных вычислительных задач.

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

3.Компетенции обучающегося, формируемые в результате освоения дисциплины


В результате освоения дисциплины студент должен:

    Знать:

  • об областях применения теории алгоритмов;

  • о различных формализациях понятия «алгоритм»;

  • о различных методах классификации существующих алгоритмов;

  • об алгоритмически неразрешимых проблемах;

  • наиболее известные алгоритмы для работы с различными структурами данных;

  • точные и приближенные подходы к решению типовых задач, возникающих в области бизнес-информатики;

  • особенности точных, приближенных, эволюционных, эвристических, переборных, «жадных» алгоритмов.

    Уметь:

  • анализировать существующие алгоритмы с точки зрения их эффективности и применимости для решения прикладных задач;

  • разрабатывать новые алгоритмы для решения конкретных задач в области бизнес-информатики;

  • оценивать сложность разработанных алгоритмов и обосновывать их корректность.

    Иметь навыки (приобрести опыт):

  • применения известных и разработки собственных алгоритмов для решения практических задач с учетом требований к точности, времени работы алгоритма и вычислительным ресурсам;

  • формализации конкретных практических проблем в сфере бизнес-информатики и их сведения к известным модельным задачам.

В результате освоения дисциплины студент осваивает следующие компетенции:



Компетенция

Код по ФГОС/ НИУ

Дескрипторы – основные признаки освоения (показатели достижения результата)

Формы и методы обучения, способствующие формированию и развитию компетенции

Владение культурой мышления, способность к обобщению, анализу, восприятию информации, постановке цели и выбору путей её достижения

ОНК 3

Даёт четкие определения основных понятий информатики и программирования, видит их связь

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

Четко формулирует задачи, анализирует условия и обоснованно выбирает методы решения, уверенно интерпретирует результаты

Способность логически верно, аргументировано и ясно строить устную и письменную речь

СЛК-1

Демонстрирует умение обосновывать предлагаемые решения (не только разрабатывать алгоритмы и программы, реализующие их, но и уметь доказывать правильность программ, анализировать и оценивать эффективность решений)

Способность к саморазвитию, повышению своей квалификации и мастерства

СЛК-4

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

Самостоятельное изучение отдельных тем.


Показывает умение сформулировать проблемы, связанные с недостатком знаний и навыков, и выбрать подходы к их решению

Готовность работать  с информацией из различных источников /

Владение основными методами, способами и средствами получения, хранения, переработки информации



ИК- 4 /

ИК-5


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

Самостоятельное изучение отдельных тем при подготовке к контрольным мероприятиям

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

Способность к организованному подходу к освоению и приобретению новых навыков и компетенций

СЛК -7

Демонстрирует способность применять полученные знания для решения новых задач в различных областях

Выполнение заданий с постепенным наращиванием требований к сложности, используемым методам и средствам решения

Владеет навыками самостоятельного поиска, изучения и выбора методов и средств решения поставленных задач

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

Использовать соответствующий математический аппарат и инструментальные средства для обработки, анализа и систематизации информации по теме исследования


ПК-22

Уверенно использует способы формального описания алгоритмов с применением математического аппарата

Использование и сравнение формальных средств при изучении основных методов разработки программ и средств языка Pascal.

Получение формальных оценок и сравнение их с результатами, полученными при практической реализации



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

Знает и может использовать на практике математический аппарат, формальные средства, лежащие в основе различных методов разработки алгоритмов и программ

Может построить оценки и доказать свойства алгоритмов и программ с использованием формальных методов

Владеет методами и инструментальными средствами разработки программ, в частности основными возможностями современных систем программирования, языков высокого уровня:

    1. знает возможности системы программирования и может разрабатывать программы средней сложности на языке Pascal;

    2. владеет средствами тестирования и отладки программ с использованием возможностей системы программирования

Выполнение практических заданий с использованием языка Pascal, их тестирование с использованием различных методов и отладка

4.Место дисциплины в структуре образовательной программы


Настоящая дисциплина относится к факультативам.
Изучение данной дисциплины базируется на следующих дисциплинах:

  1. Программирование.

  2. Теоретические основы информатики.

  3. Методология научных исследований.

Для освоения учебной дисциплины, студенты должны владеть следующими знаниями и компетенциями:



  • понимание основных концепций, принципов, теорий и фактов, связанных с информатикой;

  • умение применять основы информатики и программирования к проектированию, конструированию и тестированию программных продуктов;

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

  • способность оценивать временную и емкостную сложность программного обеспечения.

Основные положения дисциплины должны быть использованы в дальнейшем при изучении следующих дисциплин:



  • Дискретная математика.

  • Объектно-ориентированный анализ и программирование.

  • Информационные процессы, системы и сети.

  • Криптографические методы защиты.

  • Распределенные алгоритмы и параллельное программирование.

  • Моделирование информационных систем.

  • Оптимизация и математические методы принятия решений.

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




Название раздела

Всего часов

Аудиторные часы

Самостоя­тельная работа

Лекции

Семинары

Практические занятия

1

Раздел 1. Основы теории алгоритмов

50

10




10

30

2

Тема 1. Рекурсивные функции как формализация понятия «алгоритм»

10

2




2

6

3

Тема 2. Машина Тьюринга и нормальные алгорифмы Маркова как формализации понятия «алгоритм»

10

2




2

6

4

Тема 3. Алгоритмическая разрешимость и неразрешимость

10

2




2

6

5

Тема 4. Модели вычислений и меры сложности

10

2




2

6

6

Тема 5. Классы сложности P и NP

10

2




2

6

7

Раздел 2. Точные и приближенные методы и алгоритмы

58

10




14

34

8

Тема 6. Комбинаторные алгоритмы

10

2




2

6

9

Тема 7. Алгоритмы комбинаторной оптимизации на графах

10

2




2

6

10

Тема 8. Потоковые алгоритмы

10

2




2

6

11

Тема 9. Точные и приближенные алгоритмы

14

2




4

8

12

Тема 10. Генетические алгоритмы и эволюционные вычисления

14

2




4

8

13

Всего:

108

20




24

64

6.Контроль знаний студентов


6.1. Формы контроля знаний студентов


Тип контроля

Форма контроля

1 год

Параметры

1

2

3

4

Текущий (неделя)

Контрольная работа










8

Письменная работа (90 минут)

Итоговый

Зачет










*

Письменный зачет (90 минут)
    1. Критерии оценки знаний, навыков


Текущий контроль предусматривает выполнение письменной контрольной работы.

Оценка по письменной контрольной работе выставляется по 10-ти балльной шкале.


7.Содержание дисциплины


Раздел 1. Основы теории алгоритмов

Тема 1. Рекурсивные функции как формализация понятия «алгоритм»

Простейшие рекурсивные функции, операции суперпозиции и примитивной рекурсии. Обоснование примитивной рекурсивности некоторых элементарных функций. Частично-рекурсивные функции и предикаты. Операция минимизации. Примеры всюду определенных и частичных рекурсивных функций и предикатов, функция Аккермана. Существование нерекурсивных функций.



Лекции: 2 часа.

Практические занятия: 2 часа.

Самостоятельная работа: 6 часов.

Отведенное время на практических занятиях используется для изучения рекурсивных функций и операций над ними.

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

Тема 2. Машина Тьюринга и нормальные алгорифмы Маркова как формализации понятия «алгоритм»

Интуитивное понятие алгоритма. Машина Тьюринга, устройство и функционирование. Простейшие машины Тьюринга. Операции над машинами Тьюринга. Вычислимые по Тьюрингу функции, примеры. Совпадение классов частично-рекурсивных и вычислимых по Тьюрингу функций. Формулы, подстановки, схемы. Функции, вычислимые с помощью нормальных алгорифмов Маркова, примеры. Операции над алгорифмами Маркова.



Лекции: 2 часа.

Практические занятия: 2 часа.

Самостоятельная работа: 6 часов.

Отведенное время на практических занятиях используется для изучения машины Тьюринга и вычислимых с её помощью функций, нормальных алгорифмов Маркова.

Самостоятельная работа предусматривает написание программ для машины Тьюринга и нормальных алгорифмов Маркова.

Тема 3. Алгоритмическая разрешимость и неразрешимость

Сопоставление различных формализаций понятия «алгоритм». Тезисы Черча, Тьюринга, Маркова. Кодирование машин Тьюринга. Алгоритмическая разрешимость и неразрешимость проблемы. Примеры алгоритмически разрешимых неразрешимых проблем. Алгоритмические проблемы самоприменимости, применимости, останова, их алгоритмическая неразрешимость. Разрешимые и перечислимые множества. Нумерация алгоритмов. Теоремы Клини и Райса.



Лекции: 2 часа.

Практические занятия: 2 часа.

Самостоятельная работа: 6 часов.

Отведенное время на практических занятиях используется для изучения алгоритмических проблем самоприменимости, применимости и останова.

Самостоятельная работа предусматривает изучение разрешимых и перечислимых множеств и их свойств.

Тема 4. Модели вычислений и меры сложности

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



Лекции: 2 часа.

Практические занятия: 2 часа.

Самостоятельная работа: 6 часов.

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

Самостоятельная работа предусматривает изучение эвристических, комбинированных и генетических алгоритмов.

Тема 5. Классы сложности P и NP

Задачи распознавания. Недетерминированные вычисления. Два подхода к определению недетерминированных машин Тьюринга. Классы P и NP. Соотношение между ними. Примеры задач из классов P и NP. Полиномиальная сводимость и NP-полные задачи, примеры. Задача о «выполнимости КНФ» и теорема Кука. Методы доказательства NP-полноты. NP-трудные задачи. Подходы к решению NP-полных и NP-трудных задач.



Лекции: 2 часа.

Практические занятия: 2 часа.

Самостоятельная работа: 6 часов.

Отведенное время на практических занятиях используется для изучения различных задач — представителей классов P и NP.

Самостоятельная работа предусматривает изучение NP-трудных задач и подходов к их решению.
Литература по разделу:


  1. Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы. М.: Издательский дом «Вильямс», 2000. (Глава 1. Построение и анализ алгоритмов).

  2. Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ, 2-е издание. М.: Издательский дом «Вильямс», 2005. (Глава V. NP-полнота. Приближенные алгоритмы).

  3. Игошин В.И. Математическая логика и теория алгоритмов: Учеб. пособие. М.: Академия, 2004. (Глава VII. Элементы теории алгоритмов).

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


Раздел 2. Точные и приближенные методы и алгоритмы

Тема 6. Комбинаторные алгоритмы

Рекурсивные алгоритмы, примеры. Исследование сложности рекурсивных алгоритмов с помощью рекуррентных соотношений. Матричный метод решения систем рекуррентных соотношений. Производящие функции, операции над ними, использование для решения рекуррентных соотношений. Алгоритмы генерации комбинаторных объектов. Теория перечисления Пойа и теорема Бернсайда для подсчета числа комбинаторных объектов.



Лекции: 2 часа.

Практические занятия: 2 часа.

Самостоятельная работа: 6 часов.

Отведенное время на практических занятиях используется для изучения рекурсивных алгоритмов и оценке их сложности.

Самостоятельная работа предусматривает производящих функций и их использование для решения рекуррентных соотношений.

Тема 7. Алгоритмы комбинаторной оптимизации на графах

Задача о максимальном паросочетании в графе. Чередующиеся цепи. Метод «волны» для поиска чередующихся цепей. Теорема Бержа. Алгоритм поиска максимального паросочетания с помощью чередующихся цепей. Задача о совершенном паросочетании. Чередующееся дерево. Метод «волны» для поиска чередующихся деревьев. Теорема Холла. Алгоритм поиска совершенного паросочетания с помощью чередующихся деревьев. Задача о назначениях. Матрица затрат и её свойства. Диагональная редукция матрицы затрат. Венгерский алгоритм для решения задачи о назначении.



Лекции: 2 часа.

Практические занятия: 2 часа.

Самостоятельная работа: 6 часов.

Отведенное время на практических занятиях используется для изучения наиболее известных алгоритмов на графах.

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

Тема 8. Потоковые алгоритмы

Поток в двухполюсной сети. Величина потока. Задача о максимальном потоке в двухполюсной сети. Разрез сети. Пропускная способность разреза. Теорема Форда-Фалкерсона. Остаточная сеть. Алгоритм поиска максимального потока в двухполюсной сети с помощью остаточной сети. Стоимость потока в двухполюсной сети. Задача о максимальном потоке минимальной стоимости в двухполюсной сети. Остаточная сеть. Алгоритм поиска максимального потока минимальной стоимости путем устранения циклов отрицательной стоимости в остаточной сети. Сведение задачи о максимальном паросочетании в двудольном графе к задаче о максимальном потоке в измененном графе.



Лекции: 2 часа.

Практические занятия: 2 часа.

Самостоятельная работа: 6 часов.

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

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

Тема 9. Точные и приближенные алгоритмы

Метод ветвей и границ. Задача о рюкзаке, её точное решение методом ветвей и границ. Приближенные алгоритмы, оценки их погрешности. Приближенный алгоритм для задачи о рюкзаке с гарантированной погрешностью. Динамическое программирование. Задача о минимальном покрытии, её точное решение с помощью динамического программирования. Задача коммивояжера. Метод ветвей и границ для точного решения задачи коммивояжера. Алгоритм Литтла. Приближенный алгоритм Кристофидиса для евклидовой задачи коммивояжера.



Лекции: 2 часа.

Практические занятия: 4 часа.

Самостоятельная работа: 8 часов.

Отведенное время на практических занятиях используется для изучения метода ветвей и границ и метода динамического программирования.

Самостоятельная работа предусматривает применение указанных методов для сокращения перебора при решении прикладных задач комбинаторной оптимизации.

Тема 10. Генетические алгоритмы и эволюционные вычисления

Кодирование объектов. Определение фенотипа объекта по его генотипу. Основные генетические операции: кроссовер, отбор, мутация. Фитнесс-функция. Схема работы эволюционного алгоритма на примере задачи коммивояжера. Шаблоны. Теорема шаблонов. Настройка эволюционного алгоритма. Стратегии отбора. Модели эволюционных вычислений: Genitor, СНС, Hybrid Algorithms, Island Models, Cellular Genetic Algorithms. Эволюционное программирование.



Лекции: 2 часа.

Практические занятия: 4 часа.

Самостоятельная работа: 8 часов.

Отведенное время на практических занятиях используется для изучения генетических алгоритмов и их модификаций.

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

Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы. М.: Издательский дом «Вильямс», 2000. (Глава 9. Методы анализа алгоритмов, Глава 10. Методы разработки алгоритмов).

Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ, 2-е издание. М.: Издательский дом «Вильямс», 2005. (Глава I. Математические основы анализа алгоритомв, Глава IV. Методы построения и анализа алгоритмов).

Гладков Л.А., Курейчик В.В., Курейчик В.М. Генетические алгоритмы. М.: ФИЗМАТЛИТ, 2006. (Глава 3. Основные понятия и структура генетических алгоритмов).
Формы и методы проведения занятий по разделу, применяемые учебные технологии: лекционные и практические занятия.

8.Образовательные технологии


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

На практических занятиях используются следующие методы обучения и контроля усвоения материала:



    1. написание контрольной работы по теоретической части курса;

    2. разработка алгоритмов для конкретных задач и их практическая реализация в виде программного продукта с последующей отладкой и тестированием.

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

Методические указания студентам:

Студенту рекомендуется следующая схема подготовки к контрольной работе или выполнения домашних заданий:



  • проработать конспект лекций;

  • проанализировать основную и дополнительную литературу, рекомендованную по изучаемому разделу;

  • проанализировать варианты решений, предложенные преподавателем на практических занятиях;

  • при затруднениях сформулировать вопросы к преподавателю.

При подготовке рекомендуется использовать электронные учебные материалы, имеющиеся в медиатеке.

Выполненные задания должны сопровождаться данными анализа результатов (теоретическими оценками, сравнением результатов, полученных различными способами).


9.Оценочные средства для текущего контроля и аттестации студента

      9.1. Тематика заданий текущего контроля


По дисциплине предусмотрена одна контрольная работа по теме «Основы теории алгоритмов». Примерный перечень заданий:

  • для заданной всюду определенной функции построить вычисляющую её машину Тьюринга;

  • доказать рекурсивность заданной функции;

  • к заданной паре всюду определенных рекурсивных функций применить операцию примитивной рекурсии;

  • к заданной не всюду определенной рекурсивной функции одного или двух аргументов применить операцию минимизации по одному из аргументов.

      9.2. Вопросы для оценки качества освоения дисциплины


  1. Какая функция называется примитивно рекурсивной?

  2. В чем заключаются операции суперпозиции и примитивной рекурсии?

  3. Что такое частично рекурсивная функция?

  4. Как выполняется операция минимизации?

  5. Как можно закодировать и пронумеровать машины Тьюринга?

  6. Какие функции вычислимы по Тьюрингу? В чем состоит тезис Тьюринга?

  7. Существуют ли невычислимые функции?

  8. Какая функция соответствуют проблеме самоприменимости? Вычислима ли эта функция?

  9. В чем состоит проблема останова и что означает её алгоритмическая неразрешимость?

  10. Что такое разрешимое и перечислимое множество?

  11. Какие проблемы в теории алгоритмов алгоритмически неразрешимы?

  12. В чем смысл теорем Клини и Райса?

  13. Какие существуют оценки эффективности алгоритма? Чем сложность «в худшем» отличается от сложности «в среднем»?

  14. Чем полиномиальные алгоритмы отличаются от экспоненциальных?

  15. Чем нижние оценки сложности алгоритмов отличаются от верхних? Чем отличаются методы их доказательства?

  16. Что такое недетерминированная машина Тьюринга?

  17. Чем отличаются классы задач P и NP?

  18. Какая задача считается NP-полной?

  19. Каковы методы доказательства NP-полноты задачи?

  20. В чем состоят матричный метод и метод исключения неизвестных для решения системы линейных рекуррентных соотношений с постоянными коэффициентами?

  21. Каковы этапы решения неоднородного рекуррентных соотношения с постоянными коэффициентами?

  22. Как полиномиальные производящие функции используются для решения рекуррентных соотношений с переменными коэффициентами?

  23. Как формулируются первая и вторая теоремы Пойа о цикловом индексе группы подстановок?

  24. Что такое максимальное паросочетание и как его можно найти с помощью алгоритма чередующихся цепей?

  25. Что такое совершенное паросочетание и как его можно найти с помощью чередующихся деревьев?

  26. Что такое поток и разрез в сети? Как формулируется теорема Форда–Фолкерсона?

  27. В чем состоит задача о максимальном потоке в сети и как она решается?

  28. В чем состоит задача о максимальном потоке минимальной стоимости и как она решается?

  29. В чем состоит задача о назначениях? Как она решается с помощью венгерского алгоритма?

  30. Каков алгоритм построения расписания минимальной стоимости для независимых заданий и одного исполнителя?

  31. Каков алгоритм построения расписания минимальной длительности для единичных заданий с древовидным графом предшествования?

  32. Каков алгоритм построения расписания минимальной длительности с прерываниями для независимых заданий?

  33. В чем заключается задача о рюкзаке? Как она решается методом ветвей и границ?

  34. В чем заключается приближенный алгоритм для задачи о рюкзаке с гарантированной погрешностью?

  35. Как формулируется задача коммивояжера? Как она решается методом ветвей и границ?

  36. Как формулируется евклидова задача коммивояжера? В чем состоит алгоритм Кристофидиса для её решения?

  37. Что такое «жадный» алгоритм и эвристика? Чем они отличаются?

  38. Какова общая схема работы генетического алгоритма? Каковы его параметры?

  39. Что такое генетические операторы? Какие существуют методы отбора особей?

  40. Как решается задача коммивояжера с помощью генетического алгоритма?

      9.3. Примеры заданий итогового контроля


Билет №1

  1. Классический алгоритм (5 требований) на примере задачи о минимальном времени выполнения работ (задача календарного планирования), алгоритм Демукрона.

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

Билет №2

  1. Сложность алгоритмов: полиномиальные и экспоненциальные алгоритмы, особенности полиномиальных алгоритмов (замкнутость класса полиномиальных алгоритмов, «позитивная» реакция на технический прогресс).

  2. Потоковые задачи и алгоритмы: задача о максимальном потоке минимальной стоимости.

Билет №3

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

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

Билет №4

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

  2. Потоковые задачи и алгоритмы: задача о максимальном потоке в двухполюсной сети (теорема Форда-Фолкерсона, полиномиальный алгоритм на основе остаточной сети).

Билет №5

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

  2. Решение задач комбинаторной оптимизации с помощью потоковых алгоритмов: транспортная задача, её сведение к задаче о максимальном потоке минимальной стоимости.

Билет №6

  1. Задачи и алгоритмы теории расписаний: минимизация времени выполнения с прерываниями комплекса независимых работ произвольной длительности для произвольного числа одинаковых исполнителей (ленточная стратегия).

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

Билет №7

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

  2. Метод ветвей и границ для решения сложных задач комбинаторной оптимизации на примере задачи о рюкзаке.

Билет №8

  1. Задачи и алгоритмы теории расписаний: минимизация времени выполнения с прерываниями комплекса независимых работ произвольной длительности для произвольного числа неодинаковых исполнителей (стратегия деления и объединения исполнителей).

  2. Генетические алгоритмы как метод решения сложных задач комбинаторной оптимизации на примере задачи о рюкзаке.

Билет №9

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

  2. Решение задач комбинаторной оптимизации с помощью потоковых алгоритмов: задача о кратчайшем пути, её сведение к задаче о максимальном потоке минимальной стоимости.

Билет №10

  1. Классический алгоритм (5 требований) на примере задачи о минимальном времени выполнения работ (задача календарного планирования), алгоритм Демукрона.

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

Билет №11

  1. Сложность алгоритмов: полиномиальные и экспоненциальные алгоритмы, особенности полиномиальных алгоритмов (замкнутость класса полиномиальных алгоритмов, «позитивная» реакция на технический прогресс).

  2. Потоковые задачи и алгоритмы: задача о максимальном потоке минимальной стоимости.

Билет №12

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

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

Билет №13

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

  2. Потоковые задачи и алгоритмы: задача о максимальном потоке в двухполюсной сети (теорема Форда-Фолкерсона, полиномиальный алгоритм на основе остаточной сети).

Билет №14

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

  2. Решение задач комбинаторной оптимизации с помощью потоковых алгоритмов: транспортная задача, её сведение к задаче о максимальном потоке минимальной стоимости.

Билет №15

  1. Задачи и алгоритмы теории расписаний: минимизация времени выполнения с прерываниями комплекса независимых работ произвольной длительности для произвольного числа одинаковых исполнителей (ленточная стратегия).

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

Билет №16

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

  2. Метод ветвей и границ для решения сложных задач комбинаторной оптимизации на примере задачи о рюкзаке.

Билет №17

  1. Задачи и алгоритмы теории расписаний: минимизация времени выполнения с прерываниями комплекса независимых работ произвольной длительности для произвольного числа неодинаковых исполнителей (стратегия деления и объединения исполнителей).

  2. Генетические алгоритмы как метод решения сложных задач комбинаторной оптимизации на примере задачи о рюкзаке.

Билет №18

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

  2. Решение задач комбинаторной оптимизации с помощью потоковых алгоритмов: задача о кратчайшем пути, её сведение к задаче о максимальном потоке минимальной стоимости.

Билет №19

  1. Классический алгоритм (5 требований) на примере задачи о минимальном времени выполнения работ (задача календарного планирования), алгоритм Демукрона.

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

10.Порядок формирования оценок по дисциплине:


В НИУ ВШЭ – Пермь принята следующая система весов:

20% результирующей оценки – оценка за работу на семинарских занятиях;

40% результирующей оценки – взвешенная сумма оценок за контрольные мероприятия;

40% результирующей оценки – оценка за итоговый (или промежуточный контроль).

Таким образом, 60% результирующей оценки – это накопительная оценка и 40% – это оценка за итоговый (или промежуточный контроль).

Результирующая оценка рассчитывается с помощью взвешенной суммы накопительной оценки и оценки за зачет.

Накопительная оценка рассчитывается с помощью взвешенной суммы оценок за отдельные формы текущего контроля. К формам текущего контроля относятся контрольные мероприятия (контрольные работы, эссе, коллоквиумы и пр.), которые определены учебным планом.

Формулы расчета оценок:



О текущая = n1Ок/р

где Оi – оценки за контрольные мероприятия (эссе, контрольная работа, реферат и пр.)



ni – вес контрольных мероприятий (определяются преподавателем и ∑ni=1 или 100%), при этом

Веса по контрольным мероприятиям:

n1 = 100% - контрольная работа.
О накопительная = k1Отекущая + k2Оаудиторная

где ki – вес текущей и аудиторной оценки, при этом k1=2/3, k2=1/3


О результирующая = q1Онакопительная + q2Оитог.контроль

где qi – вес накопительной оценки и оценки за итоговый контроль, при этом q1=0,6, q2=0,4


11.Учебно-методическое и информационное обеспечение дисциплины

    1. Базовый учебник


  1. Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ, 2-е издание. М.: Издательский дом «Вильямс», 2005.
    1. Основная литература


  1. Математические методы анализа и распознавания генетической информации: Монография / В.М. Гупал. - М.: ИЦ РИОР: НИЦ Инфра-М, 2012

  2. Гладков Л.А., Курейчик В.В., Курейчик В.М. Генетические алгоритмы. М.: ФИЗМАТЛИТ, 2006.

  3. Иванов Б.Н. Дискретная математика. Алгоритмы и программы: Учеб. пособие. М.: Лаборатория Базовых Знаний, 2002.
    1. Дополнительная литература


  1. Игошин В.И. Математическая логика и теория алгоритмов: Учеб. пособие. М.: Академия, 2004.

  2. Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы. М.: Издательский дом «Вильямс», 2000.

  3. Генетические алгоритмы, искусственные нейронные сети и проблемы виртуальной реальности / Г.К.Вороновский, К.В.Махотило, С.Н.Петрашев, С.А.Сергеев. – Х.: ОСНОВА, 1997.

  4. Мальцев А.И. Алгоритмы и рекурсивные функции. М.: Наука, 1986.

  5. Судоплатов С.В., Овчинникова Е.В. Математическая логика и теория алгоритмов: Учебник. М.: ИНФРА-М; Новосибирск: Изд-во НГТУ, 2004.

  6. Успенский В.А., Семенов А.Л. Теория алгоритмов: основные открытия и приложения. М.: Наука, 1987.
    1. Программные средства


Для успешного освоения дисциплины, студент использует следующие программные средства:

            • Средства разработки, тестирования, отладки программ, написанных на языке Pascal (Pascal ABC, Free Pascal).

            • Система контроля стиля программирования Style Checker.

12.Материально-техническое обеспечение дисциплины


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

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




скачать файл



Смотрите также:
Программа дисциплины Теория алгоритмов и эволюционные вычисления для направления 080500. 62 Бизнес-информатика подготовки бакалавра
321.66kb.
Программа дисциплины "Электронный бизнес"
155.54kb.
1Область применения и нормативные ссылки
229.42kb.
Рабочая программа дисциплины теория алгоритмов направление подготовки 230700 прикладная информатика профиль подготовки
215.84kb.
Программа дисциплины Дискретная математика 2 для направления 010500. 62 «Прикладная математика и информатика» подготовки бакалавра
90.97kb.
Программа дисциплины «История и теория литературы»
611.74kb.
Программа дисциплины нис «Геометрия и динамика»
108.67kb.
Программа дисциплины «Организационное поведение» для направления 080200. 68 «Менеджмент»
216.4kb.
Программа дисциплины [Введите название дисциплины] для направления/ специальности [код направления подготовки и «Название направления подготовки»
351.94kb.
Программа дисциплины «Языковое разнообразие» для направления 035800. 62 «Фундаментальная и прикладная лингвистика» подготовки бакалавра
175.83kb.
Программа дисциплины "Теория и история культуры" для направления 030600. 68 «История» подготовки магистра
333.57kb.
Программа дисциплины Динамическая микроэкономика для направления 080100. 62 «Экономика» подготовки бакалавра
78.43kb.