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

1. Вычислительные Машины И Труднорешаемые Задачи Купить
2. Первые Вычислительные Машины
3. Вычислительные Машины И Труднорешаемые Задачи

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

1. Труднорешаемые задачи. (цифровая вычислительная машина). Цепи и машины.
2. Гэри М., Джонсон Д. - Вычислительные машины и труднорешаемые задачи Гэри М., Джонсон Д.

Гэри М., Джонсон Д. - Вычислительные машины и труднорешаемые задачи [1982, pdf, rus] торрент. Пособие - М.: ВМК МГУ, 2006. Задачи на составление алгоритмов в виде машины.

Понятие вычислимой функции, разрешимого множества. Перечислимые множества. Перечислимость и разрешимость (теорема Поста, теорема о. проекции разрешимого множества). Теорема о графике вычислимой функции. Универсальные вычислимые функции.

Нумерации вычислимых функций. Главные универсальные функции.

Вычислительные Машины И Труднорешаемые Задачи Купить

Построение перечислимого неразрешимого множества. Алгоритмически неразрешимые проблемы в теории алгоритмов. Неразрешим ость проблемы тождества в полугруппах. Примеры других алгоритмически неразрешимых проблем в алгебре и теории чисел. m-Сводимость, m-полные перечислимые множества. Машины с оракулом и сводимость по Тьюрингу.

Первые Вычислительные Машины

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

Доказуемо трудные алгоритмические проблемы: проверка эквивалентности расширенных регулярных выражений, выяснение истинности формул языка первого порядка в аддитивной группе действительных числах. Задачи поиска и класс SearchP. Сведение задач поиска к задачам разрешения из класса NP.

Задачи подсчета и класс #P. NP-трудные и NP-полные задачи.

Проблема перебора (P=NP?) и предположительная трудность NP-трудных задач. Схемы их функциональных элементов. Теорема Кука-Левина об NP-полноте проблемы выполнимости схем из функциональных элементов.

NP-полнота других задач: 3-КНФ, 3-РАСКРАСКА, КЛИКА, ВЕРШИННОЕ ПОКРЫТИЕ, ГАМИЛЬТОНОВ ЦИКЛ, РЮКЗАК, КОММИВОЯЖЕР, ЦЕЛОЧИСЛЕННОЕ ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ. Задачи оптимизации и их сводимость к задачам из NP. Приближенное решение оптимизационных задач. Трудность задачи апроксимации хроматического числа данного графа. Рекомендуемая литература:.

Н. Верещагин и А. Вычислимые функции. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. Классические и квантовые вычисления.

М.: МЦНМО, ЧеРо, 1999. Лейзерсон, Р. Алгоримты: построение и анализ. М.: МЦНМО, 2001.

Алексеева Теория принятия решений Курс лекций (слайды) НГУ, Факультет информационных технологий 3 курс 2 семестр Лекция 1. Динамическое программирование.

Задача о ближайшем соседе Лекция 2. Задачи о рюкзаке Лекция 3. Задачи о рюкзаке (Продолжение) Лекция 4. Задачи упаковки в контейнеры Лекция 6.

Задачи раскроя и упаковки Лекция 7. Сетевое планирование. Сетевое планирование. Задача коммивояжера.

Вычислительные Машины И Труднорешаемые Задачи

Задача коммивояжера. Задача о назначениях. Задачи теории расписаний. Задачи теории расписаний. Дискретные задачи размещения Лекция 14. Задачи о покрытии Лекция 15.

Матричные игры Литература. S. Matello, P.Toth Knapsack Problems. Algorithms and Computer Implementations.-John Wiley & Sons. Coffman, M.R. Approximation algorithms for bin packing: A survey. О некоторых математических моделях и методах планирования крупномасштабных проектов //Модели и методы оптимизации.

Труды Института математики. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. Введение в теорию расписаний.

Кооперативное принятие решений: Аксиомы и модели. М.: Мир, 1991. Дискретные задачи размещения и полиномы от булевых переменных. Новосибирск.: Изд-во Инст.

Production Planning by Mixed Integer Programming. Springer 2006. 499 pp. Лектор: к.ф.-м.н., доцент e-mail: Редакция.