litceysel.ru
добавить свой файл
  1 ... 12 13 14 15 16 ... 18 19

12Приложения

Оглавление базового курса информатики 1999 года

Часть 1. Языки программирования – спецификация


  1. Синтаксис

    1. Грамматики

    2. Автоматы

  2. Семантика

    1. Исполнение

      1. Операционная и денотационная семантики императивного программирования (доказательное программирование)

      2. Абстракция, аппликация, рекурсия аппликативного программирования (интерпретация)

      3. Комбинаторы функционального программирования (программирования без переменных)

      4. Вывод логического программирования (механизм возвратов, метод резолюций)

      5. Параллельность, недетерминированность, взаимодействующие последовательные процессы

      6. Интерактивность

    2. Типизация

      1. Классические пакеты: строки, массивы, множества, списки, деревья, файлы...

      2. Сильная типизированность.

      3. Слабая типизированность: смешанные вычисления, семантика Скотта.

      4. АТД

  3. Прагматика

    1. Тьюринга-модель, Ахо-модель императивного стиля

    2. Маркова-модель, Маркова-Турчина-модель аппликативного стиля

    3. Бэкуса-модель, Клини-модель функционального стиля

    4. Эрбрана-модель, Робинсона-модель логическогоо стиля

    5. Хоара-модель недетерминированности

    6. Гогуэна-модель ООП

  4. Тезис Черча в отношении моделей стилей программирования

Часть 2. Вычислимость

  1. Разрешимость, полуразрешимость (перечислимость)

    1. Счётность

    2. Диагональный метод Кантора (несчётность)

    3. Экстенсиональность

      1. Формализация

        1. Тьюринга-Поста, Маркова, Чёрча (т.Чёрча-Россера), Клини (рекурсия)

        2. Разрешимость, неразрешимость, перечислимость
      2. Гёделизация, универсальность (машины, функции), обощённая рекурсия, т. Клини о нормальной форме


    4. S-m-n теорема, т. Клини о неподвижной точке, т.Райса

    5. Сводимость, сводимость по Тьюрингу, т.Поста

    6. Неперечислимость.

  2. Эффективная вычислимость

    1. Переборные задачи

      1. Теорема об ускорении

      2. Элементы общей теории сложности

      3. Знаменитая цепочка классов сложности: NPSPACE (log N)  P  NP  Pspace = Npspace

      4. NP – класс, т. Кука, сводимость по Тьюрингу, NP – трудные задачи

      5. Эвристические приёмы для пререборных задач

    2. Оценка сложности

      1. В худшем, в среднем

      2. Производящие функции

      3. Уравнения

    3. Полиномиальные алгоритмы

      1. Сортировка и поиск

      2. Деревья

      3. Множества

  3. Выразимость: вычислимость и логика

    1. Противоречия

    2. Теории

      1. Неформальные

      2. Формальные

        1. Исчисление высказываний /* разрешимость*/

        2. Исчисления предикатов /* полуразрешимость */

        3. Разрешимые теории

        4. Неразрешимые теории

    3. Выразимость

      1. Теорема о компактности Мальцева – Гёделя

      2. Теорема Линдстрёма

      3. Усиление логик

        1. Многосортная логика первого порядка: R-логика, N-логика (-логика)

        2. Слабая логика второго порядка (в том числе, бесконечная, с новыми кванторами)

        3. Модальная логика

Часть 3. Информатика – спецификация

  1. VDM – спецификация

  2. Логико-алгебраические спецификации

  3. Системы

  4. Базы

  5. Язык категорий

Оглавление базового курса информатики 2003 года


Часть 1. Языки программирования – спецификация

  1. Синтаксис


    1. Грамматики

    2. Автоматы

  2. Семантика

    1. Исполнение

      1. Операционная и денотационная семантики императивного программирования (доказательное программирование)

      2. Абстракция, аппликация, рекурсия аппликативного программирования (интерпретация)

      3. Комбинаторы функционального программирования (программирования без переменных)

      4. Вывод логического программирования (механизм возвратов, метод резолюций)

      5. Параллельность, недетерминированность, взаимодействующие последовательные процессы

      6. Интерактивность

    2. Типизация

      1. Классические пакеты: строки, массивы, множества, списки, деревья, файлы...

      2. Сильная типизированность.

      3. Слабая типизированность: смешанные вычисления.

      4. Фукциональная модель

      5. АТД модель

  3. Прагматика

    1. Модели императивного стиля Тьюринга, Ахо

    2. Модели аппликативного стиля Маркова, Маркова-Турчина

    3. Модели функционального стиля Бэкуса, Клини

    4. Модели логическогоо стиля Эрбрана, Робинсона

    5. Модель недетерминированности Хоара

    6. Модель ООП Гогуэна

  4. Тезис Черча в отношении моделей стилей программирования

Часть 2. Вычислимость

  1. Разрешимость, полуразрешимость (перечислимость)

    1. Счётность

    2. Диагональный метод Кантора (несчётность)

    3. Экстенсиональность

      1. Формализация

        1. Тьюринга-Поста, Маркова, Чёрча (т.Чёрча-Россера), Клини (рекурсия)

        2. Разрешимость, неразрешимость, перечислимость

      2. Гёделизация, универсальность (машины, функции), обощённая рекурсия, т. Клини о нормальной форме
    4. S-m-n теорема, т. Клини о неподвижной точке, т.Райса


    5. Сводимость, сводимость по Тьюрингу, т.Поста

    6. Неперечислимость.

  2. Эффективная вычислимость

    1. Переборные задачи

      1. Теорема об ускорении

      2. Элементы общей теории сложности

      3. Знаменитая цепочка классов сложности: NPSPACE (log N)  P  NP  Pspace = Npspace

      4. NP – класс, т. Кука, сводимость по Тьюрингу, NP – трудные задачи

      5. Эвристические приёмы для пререборных задач

    2. Оценка сложности

      1. В худшем, в среднем

      2. Производящие функции

      3. Уравнения

    3. Полиномиальные алгоритмы

      1. Сортировка и поиск

      2. Деревья

      3. Множества

  3. Выразимость: вычислимость и логика

    1. Противоречия (порядок Рассела, …)

    2. Теории

      1. Неформальные (т.Стоуна, …)

      2. Формальные

        1. Исчисление высказываний /* разрешимость*/

        2. Исчисления предикатов /* полуразрешимость */

        3. Разрешимые теории

        4. Неразрешимые теории

    3. Выразимость

      1. Теорема о компактности Мальцева – Гёделя

      2. Теорема Линдстрёма

      3. Системы

        1. Вывод

        2. Процессы

        3. БД

Часть 3. Информатика – спецификация

  1. VDM – спецификация (Vienna Development Method; META-W)

  2. Алгебра

    1. Теорема Стоуна

    2. Теорема Биркгофа

  3. Формальные теории

    1. Разрешимость исчисления высказываний

    2. Перечислимость исчисления предикатов (т.Эрбрана)

    3. Усиление логик

      1. Многосортная логика первого порядка: R-логика, N-логика (-логика)
      2. Слабая логика второго порядка (в том числе, бесконечная, с новыми кванторами)

      3. Модальная логика

  4. Логико-алгебраические спецификации: OBJ, FOOPS, EQLOG

Часть 4. Язык категорий

  1. Элементы языка

  2. Категория модели данных


<< предыдущая страница   следующая страница >>