-
Maшина Тьюринга. Конфигурация, протокол, временная и емкостная сложности. Моделирование машины Тьюринга на РАМ. |
-
РАМ. Конфигурация, протокол, временная и емкостная сложности. Равномерный и логарифмический весовые критерии. Моделирование машины Тьюринга на РАМ. |
-
Моделирование вычислений. Моделирование РАМ на машине Тьюринга. |
-
Теорема об ускорении. |
-
Теорема о существовании сколь угодно сложных функций (диагональ Рабина). |
-
Теорема о нижней оценке количества умножений для вычисления Mx+y |
-
Распознование пустоты и эквивалентности конечных автоматов. |
-
Задача поиска в информационном массиве. Деревья поиска, 2-3 деревья. Оценки сложности. |
-
Задача поиска в информационном массиве. АВЛ-деревья. Оценки сложности. |
-
Задача поиска в информационном массиве. Таблицы расстановки. Оценки сложности. |
-
Сортировка массивов. Классификация алгоритмов. Быстрая сортировка. Оценка сложности. |
-
Теоремы о сложности в среднем и в худшем сортировки, основанной на сравнениях. |
-
Задача анализа свойств графа методом разметки. Существование, единственность и безопасность стационарной разметки. |
-
Задача анализа свойств графа методом разметки. Возможность построения точного решения. |
-
Понятие стандартной схемы. Интерпретация, функциональная эквивалетность. |
-
Понятие стандартной схемы. Определение логико-термальной эквивалентности. |
-
Функциональные сети для представления множества утверждений. Полурешетка. |
-
Система преобразований Sлт. Полнота и корректность. |
-
Рекурсивные схемы. Невозможность трансляции рекурсивных схем в стандартные. |
-
Рекурсивные схемы. Алгоритм трансляции стандартных схем в рекурсивные схемы. |
-
Многоленточные и многоголовочные конечные автоматы. Проблемы пустоты и эквивалентности. |
-
Оптимальные деревья двоичного поиска |
-
Порядковые статистики |
-
Древовидные структуры для задачи ОБЪЕДИНИТЬ-НАЙТИ. |
-
Определение смешанных вычислений. Проекции Футамуры. |
-
Интерпретативный, трансляционный и трансформационный подходы к смешанным вычислениям |
-
Поливариантные смешанные вычисления. |
-
Анализ периода связывания как ЗГА. Поливариантный анализ периода связывания. |
