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

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





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






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


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

В. А. Успенский
Видеозаписи:
Real Video 214.0 Mb
Windows Media 226.2 Mb
Flash Video 281.1 Mb
MP4 281.1 Mb

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

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


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

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

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

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

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