Форма обучения:
дистанционная
Стоимость самостоятельного обучения:
бесплатно
Доступ:
свободный
Документ об окончании:
 
Уровень:
Профессионал
Длительность:
15:50:00
Студентов:
531
Выпускников:
42
Качество курса:
4.45 | 4.18
Курс написан по материалам лекций и семинаров, проводившихся авторами для студентов младших курсов мехмата МГУ. В нем рассказывается об основных понятиях общей теории вычислимых функций (вычислимость, разрешимость, перечислимость, универсальные функции, нумерации и их свойства, m-полнота, теорема о неподвижной точке, арифметическая иерархия, вычисления с оракулом, степени неразрешимости) и о конкретных вычислительных моделях (машины Тьюринга, рекурсивные функции).
Изложение рассчитано на учеников математических школ, студентов математиков и всех интересующихся основами теории алгоритмов. Книга включает себя много задач различной трудности.
Специальности: Программист, Математик
 

План занятий

Занятие
Заголовок <<
Дата изучения
Лекция 1
39 минут
Вычислимость, разрешимость и перечислимость
Посвящена основным понятиям теории вычислимых функции и перечислимых множеств: вычислимость, разрешимость, перечислимость, а также некоторым критериям выполнения этих условий.
Оглавление
    -
    Тест 1
    24 минуты
    -
    Лекция 2
    30 минут
    Универсальные функции и неразрешимость
    Посвящена основным теоремам существования (не существования) вычислимых функций двух переменных, перечислимости множеств пар натуральных чисел, рассмотрены условия перечислимости таких множеств, некоторые конструкции перечислимых неразрешимых множеств.
    Оглавление
      -
      Тест 2
      24 минуты
      -
      Лекция 3
      33 минуты
      Нумерации и операции
      Посвящена основным понятиям и теоремам относительно нумерации, существования алгоритма нахождения номеров объектов в нумерациях, использованию главных универсальных функции и множества.
      Оглавление
        -
        Тест 3
        24 минуты
        -
        Лекция 4
        58 минут
        Свойства главных нумераций
        Посвящена условиям (выяснению) "нигде не определенности" функции, приводится теорема Успенского-Райса и ее усиления, а также теорема Роджерса об изоморфизме геделевых нумераций.
        Оглавление
          -
          Тест 4
          24 минуты
          -
          Лекция 5
          49 минут
          Теорема о неподвижной точке
          Посвящена одной из центральных проблем – существованию неподвижной точки (теорема Клини), а также некоторым приложениям этой теоремы, в частности, вопросу существования программы, печатающей свой код.
          Оглавление
            -
            Тест 5
            24 минуты
            -
            Лекция 6
            1 час 25 минут
            m-сводимость и свойства перечислимых множеств
            Посвящена проблема m-сводимости перечислимых множеств (существованию m – сводящей функции), а также их свойствам, в частности, эффективной неперечислимости, m – полноте, изоморфизму.
            Оглавление
              -
              Тест 6
              24 минуты
              -
              Лекция 7
              1 час 41 минута
              Вычисления с оракулом
              Посвящена проблеме сводимости по Тьюрингу (Т – сводимости) и относительной вычислимости (вычислимости относительно всюду определенной функции), релятивизации теории вычислимых функции, теореме Мучника-Фридберга о существовании несравнимых по Тьюрингу перечислимых множеств.
              Оглавление
                -
                Тест 7
                24 минуты
                -
                Лекция 8
                1 час 13 минут
                Арифметическая иерархия
                Посвящена критериям принадлежности свойств классам свойств, определяющихся последовательностями дескрипторов – кванторов существования и общности, свойствам пересечений, объединений, дополнений множеств из этих классов.
                Оглавление
                  -
                  Тест 8
                  24 минуты
                  -
                  Лекция 9
                  1 час 8 минут
                  Машины Тьюринга
                  Посвящена простой классической вычислительной модели (описанию) алгоритма (алгоритмизируемого процесса) – машине А.Тьюринга, проблеме остановки такой машины (завершаемости такого процесса) и связям этой проблемы с классической алгоритмической проблемой равенства слов в свободных полугруппах.
                  Оглавление
                    -
                    Тест 9
                    24 минуты
                    -
                    Лекция 10
                    1 час 7 минут
                    Арифметичность вычислимых функций
                    Посвящена критериям вычислимости на машине Тьюринга, арифметичности множеств, теоремам Тарского и Геделя.
                    Оглавление
                      -
                      Тест 10
                      24 минуты
                      -
                      Лекция 11
                      1 час 23 минуты
                      Рекурсивные функции
                      Посвящена рекурсивным операциям, функциям и множествам, приведены примеры, рассмотрены различные виды рекурсии (примитивная, совместная, возвратная), а также частично рекурсивные функции и нормальные алгоритмы Маркова.
                      Оглавление
                        -
                        Тест 11
                        24 минуты
                        -
                        1 час 40 минут
                        -