Алгоритмы и модели вычислений

М.Г. Фуругян, ИНТУИТ

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

Приведены и исследованы два алгоритма решения задачи о максимальном потоке (алгоритмы Форда-Фалкерсона и Карзанова). В качестве приложения потоковых алгоритмов дан алгоритм планирования вычислений в многопроцессорных вычислительных системах. Исследован алгоритм сортировки с помощью кучи. Рассматривая в качестве модели процесса вычислений детерминированную машину Тьюринга, введены и исследованы понятия рекурсивных и рекурсивно перечислимых языков, сложностных классов языков и задач (P, NP, co-NP, NPC, NPH и др.), изучена их взаимосвязь. Рассмотрены методы доказательства NP-полноты. Даны некоторые методы решения переборных задач (метод “ветвей и границ”, рандомизированные алгоритмы, приближенные алгоритмы и др.) и показана возможность применения теории NP-полноты к разработке алгоритмов решения этих задач. Приведены и исследованы параллельные алгоритмы решения некоторых задач, связанных с работой со списками и деревьями. Для каждого из приведенных алгоритмов дается обоснование и определяется вычислительная сложность.

  1. Потоки в сетях
  2. Потоки в сетях (продолжение)
  3. Приложение потоковых алгоритмов. Алгоритмы сортировки
  4. Распознающие алгоритмы. Класс P
  5. Проверяющие алгоритмы. Классы NP и NPC
  6. Семь основных NP-полных задач
  7. NP-полнота некоторых задач. Класс co-NP
  8. Сильная NP-полнота
  9. NP-трудные и NP-легкие задачи. Приближенные алгоритмы
  10. Применение теории NP-полноты к разработке приближенных алгоритмов
  11. Метод "ветвей и границ". Рандомизированные алгоритмы
  12. Алгоритмы параллельных вычислений
  13. Алгоритмы параллельных вычислений (продолжение)

Dates:
  • Free schedule
Course properties:
  • Free:
  • Paid:
  • Certificate:
  • MOOC:
  • Video:
  • Audio:
  • Email-course:
  • Language: Russian Ru

Reviews

No reviews yet. Want to be the first?

Register to leave a review

Show?id=n3eliycplgk&bids=695438
Included in selections:
Vyyjayfzd3pynkssdhnqwcrx4bk4ennc1-ren956ujr2e1pya9umefxe-z08yngaz4nptzjr4nqcte0whwul=s0#w=1724&h=1060 Алгоритмизация вычислений
1 курс МИЭМ ВШЭ, 4 кредита
NVIDIA
More on this topic:
B-teaser-0 Алгоритмы и структуры данных поиска
Лектор: Максим Александрович Бабенко, заместитель директора отделения computer...
Extpicture Структуры данных и модели вычислений
В курсе рассматриваются способы структурирования информации в моделях с адр...
Logo Алгоритмы и структуры данных поиска
В курсе рассматриваются базовые алгоритмы и структуры данных, включая хешир...
800x800-05 Прикладные задачи анализа данных
Методы машинного обучения - будь то алгоритмы классификации или регрессии, ...
8a561ceb049c7d7124abc5a58326bbab Квантовые вычисления
В рамках данного курса слушатели познакомятся с математической моделью кван...
More from 'Computer Science':
Netology2016 Новогодняя распродажа в Нетологии
Скидка на ВСЕ курсы 2016 руб! Электронная коммерция и SMM, веб-дизайн и HTML...
150x150 Курсы информационных технологий
Компания «Яндекс» регулярно проводит набор на Курсы информационных технолог...
B-teaser-0 Алгоритмы и структуры данных поиска
Лектор: Максим Александрович Бабенко, заместитель директора отделения computer...
B-teaser-0 Машинное обучение
Лектор: Константин Вячеславович Воронцов, старший научный сотрудник Вычисли...
B-teaser-0 Параллельные и распределенные вычисления
Лектор: Олег Викторович Сухорослов, старший научный сотрудник Центра грид-т...
More from 'Intuit':
Extpicture "Продвинутые" алгоритмы для школьников
В курсе рассказывается о "продвинутых" (advanced) алгоритмах для школьников...
Extpicture Комбинаторные алгоритмы для программистов
Курс начинается с азов комбинаторики и охватывает все основные алгоритмы, ...
Extpicture Алгоритмы: построение и анализ
Курс посвящён теории алгоритмов и элементам дискретной математики. Основная...
Logo Базовые и "продвинутые" алгоритмы для школьников
В курсе рассказывается о базовых и "продвинутых" (advanced) алгоритмах для ...
Extpicture Базовые алгоритмы для школьников
В курсе излагаются базовые алгоритмы для школьников. Этот курс читался на ...

© 2013-2019