Exam tickets and answers for the Information Technology course in the St. Petersburg State University.
Lecturer: Igor Solovyov
-
⌛ История создания методов структуризации данных. Цели и принципы структурной методологии. Сложность, присущая программному обеспечению. Оценки сложности алгоритмов и представления данных.
-
⌛ Представление полиномов вектором коэффициентов и вектором значений. Оценки сложности основных операций. Связь двух видов представлений полиномов. Быстрое умножение полиномов — основные идеи и проблемы.
-
⌛ Свойства комплексных корней степени п из 1. Быстрое умножение полиномов с помощью дискретного преобразования Фурье.
-
⌛ Абстракция данных. Основные понятия и примеры. Абстракция булевского типа данных. Абстракция типа целого числа. Абстракция типа список.
-
⌛ Абстракция типа стек, Определение новых типов. Абстракция типа очередь. Обобщение типов стек и очередь. Пример реализации стека. Вычисление выражений в ОПЗ.
-
⌛ Деревья, их представление, примеры, сложность представления. Представление деревьев массивами. Бинарные деревья, основные операции над ними. Применение стека.
-
⌛ Лемма о пустых ссылках в бинарных деревьях. Прошитые деревья.
-
⌛ Изоморфизм бинарных деревьев. Лемма об изоморфных бинарных деревьях.
-
⌛ Лемма о флагах прошитого бинарного дерева. Теорема об изоморфизме бинарных деревьев.
-
⌛ Формализация понятия алгоритма. Понятие МНР. Программы МНР и вычислимые функции. Иллюстративные примеры. Примеры МНР-программ.
-
⌛ Свойства МНР-программ и тезис Черча. Соединение и композиция программ. Доказательство с помощью тезиса Черча. Вычислимые отношения и предикаты.
-
⌛ Примитивная рекурсия. Теорема о ее вычислимости.
-
⌛ Примитивно рекурсивные функции. Определение и простые примеры: сумма, произведение, степень, константы, разности.
-
⌛ Примитивно рекурсивные функции. Примеры: знаки, модули, мин, макс, остаток и частное.
-
⌛ Ограниченные сумма и произведение. Примеры: признак делимости, число делителей, свойство простоты. Разрешимые предикаты и разбор случаев. Алгебра разрешимости.
-
⌛ Ограниченная минимизация. Теоремы о ее вычислимости и примитивной рекурсивности. Ограниченная минимизация и подстановка. Примеры: простые числа и показатель их степени.
-
⌛ Числа Фибоначчи, примитивная рекурсия, лемма, возвратная рекурсия.
-
⌛ Неограниченная минимизация. Теорема о вычислимости минимизации. Примеры неограниченной минимизации и ее свойства. Обращение функций.
-
⌛ ЧР и теорема о ЧРФ и МНР.
-
⌛ Нумерации и соответствия. Нумерация Кантора.
-
❌ Нумерация Геделя пар и кортежей. Нумерация программ и функций. Свойства нумераций функций.
-
❌ Теорема о параметризации в простой форме.
-
❌ Теорема о параметризации в полной форме.
-
❌ Универсальные функции. Теорема. Предикаты Клини и теорема Клини о нормальной
-
❌ Неразрешимость. Проблемы самоприменимости и останова.
-
❌ Теорема Райса. Примеры.
-
❌ Разрешимые и частично разрешимые предикаты. Примеры. Теорема.
-
❌ Разрешимые множества и их связь с перечислимыми. Примеры и основные утверждения.
-
❌ Перечислимые множества. Примеры и основные утверждения.
-
❌ Машины Тьюринга.
-
❌ Системы Поста и алгоритмы Маркова.