RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ЛИЧНЫЙ КАБИНЕТ
Видеотека
Архив
Популярное видео

Поиск
RSS
Новые поступления





Для просмотра файлов Вам могут потребоваться






Летняя школа «Современная математика», 2009
22 июля 2009 г. 12:45, г. Дубна
 


Начальные понятия дескриптивной теории алгоритмов. Лекция 2

В. А. Успенский
Видеозаписи:
Flash Video 413.8 Mb
MP4 413.8 Mb

Количество просмотров:
Эта страница:144
Видеофайлы:29

В. А. Успенский


Видео не загружается в Ваш браузер:
  1. Установите Adobe Flash Player    

  2. Проверьте с Вашим администратором, что из Вашей сети разрешены исходящие соединения на порт 8080
  3. Сообщите администратору портала о данной ошибке

Аннотация: В отличие от метрической теории алгоритмов, дескриптивная теория не занимается измерением ресурсов (таких как время, объём памяти), затрачиваемых при применении алгоритма к его возможным исходным данным (в другой терминологии — к его входам). Её интересует лишь, возможен алгоритм для решения данной задачи или нет. Начальные понятия дескриптивной теории алгоритмов суть:
  • конструктивный обьект;
  • алгоритм;
  • число шагов алгоритма;
  • вычислимая функция;
  • перечислимое множество;
  • разрешимое множество;
  • сводимость нумераций;
  • главная вычислимая нумерация;
  • вычислимая операция.

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

ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru
 
Обратная связь:
 Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2017