МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ
Основная гипотеза теории алгоритмов.
Любая практическая задача, приводящая к необходимости создания эффективного вычислительного метода (алгоритма), может быть поставлена в точных математических терминах.
Содержание
- Математическая логика
- Парадигмы формальной логики.
- Предмет, цель, задачи и содержание читаемого курса лекций.
- Место читаемого курса о законах и формах правильного мышления.
- Концептуальный базис математической логики.
- Построение математической логики.
- Классическая логика высказываний.
- Язык классической логики предикатов (я.Л.П.).
- Примеры:
- Алгебра логики предикатов.
- Пояснения:
- Квантификация предикатов.
- Эквивалентные преобразования кванторных формул.
- Классические логические исчисления.
- Цель классических и.В. И и.П.
- Метасимволика и.В. И и.П.
- Построение логических исчислений.
- Интуитивное (наивное) понятие алгоритма как основное первичное понятие математики.
- Основные требования к алгоритмам.
- Основная терминология теории алгоритмов.
- Основные теоремы теории алгоритмов.
- Параметры алгоритма.
- Основная гипотеза теории алгоритмов.
- Алгоритмические (формальные математические) модели.
- Блок-схемы алгоритмов.
- Машина Тьюринга. Машина Тьюринга т – название, закрепившееся за вычислительными абстрактными машинами некоторого точно охарактеризованного типа.
- 1) Пусть последовательность k0k2kzимеет видq0a2a1a4q1a1qza4a2(очевидно, что последовательность команд следующая:q0a2q1a4 dп,q1a1qza2dЛ).
- Формальное определение машины Тьюринга.
- Основной тезис Тьюринга.
- Нормальные алгорифмы (алгоритмы).
- Рекурсивные функции.
- Примитивно-рекурсивные функции.
- Оператор минимизации (- орератор).
- Основной тезис Черча.
- Алгоритмически неразрешимые проблемы.