Вопросы по теории: абстрактные исполнители и вычисления,

Здесь вы найдете примеры вопросов по теории первого семестра.

• Абстрактные исполнители и вычисления
  • Что такое конечный автомат?
  • Что такое машина Тьюринга и зачем она нужна?
  • Что такое алгорифмы Маркова и зачем они нужна?
  • Предложите алгорифм Маркова умножения числа в двоичной системе на 3
  • Предложите конечный автомат, который умножает сколь угодно длинные числа, записанные в двоичной системе счисления на 3
  • Что такое вычислимые функции?
  • Приведите пример невычислимой функции.
  • Перечислите некоторые из операций (отличающиеся от арифметических + - . *), относительно которых замкнуты вычислимые функции.
  • Что такое асимптотическая сложность вычислений?
• Язык Си
  • Что такое .... ?
    • препроцессинг (preprocess)
    • компиляция (compile)
    • компоновка (link)
    • прототип (prototype)
    • рекурсивный вызов
    • дерево рекурсивных вызовов
    • стек вызовов
    • segmentation fault
    • page fault
    • compilation error и runtime error
  • Опишите #include и #define. Что такое макроопределения и зачем они нужны? Приведите пример.
  • Чем отличаются статический, динамический и автоматический способы выделения памяти?
  • Опишите прототипы и семантику функций free и malloc.
  • Опишите функцию qsort из стандартной библиотеки C. Приведите пример использования.
  • Перечислите максимальное количество бинарных операторов языка Си (лучше все). Приведите пример правоассоциативного и левоассоцитивного бинарного оператора. Что такое приоритет бинарного оператора? Приведите пример операторов с разным приоритетом.
  • Опишите операторы структурного программирования while, for и if. Когда нужно использовать while, а когда for?
  • Опишите бинарные условные операторы. Чему равны выражения
    • (1 < 5) && (10 > 5) ?
    • (7 == 7) == 1 ?
    • (5 == 7) == 1 ?
    • (5 == 7) || (1 < 5) ?
    • (5 == 7) || (1 > 5) == 0 ?
    • 7 && 5 ?
    • 7 & 5 ?
  • Что такое оператор взятия адреса? Каким должен быть операнд этого оператора? Чему равен результат?
  • Арифметика указателей. Перечислите операции с указателями.
• Алгоритмы и структуры данных
  • Что такое алгоритм?
  • Опишите алгоритм Евклида. Оцените его ассимптотическую сложность?
  • Что такое рекурсивные алгоритмы? Приведите пример задачи, которая естественно решается рекурсивным алгоритмом.
  • Деревья поиска — что это такое и зачем они нужны? Приведите примеры жизненных задач.
  • Хэш-таблицы — что это такое и зачем они нужны? Приведите примеры жизненных задач.
  • Зачем нужно балансировать деревья поиска? Опишите одну из техник поддержки сбалансированности дерева.
  • Когда не имеет смысла использовать хэш-таблицы, а использовать вместо них деревья поиска?
  • Опишите интерфейс "Ассоциативный массив" и расскажите про одну из возможных реализаций этого интерфейса.
  • Опишите интерфейс "Очередь с приоритетом" и расскажите про одну из возможных реализаций этого интерфейса.
  • Опишите интерфейс "String pool" и расскажите про одну из возможных реализаций этого интерфейса.
  • Объясните идею решения одной из сложных задач из TestCProblems.
  • Худшее и среднее время работы алгоритма. Докажите, что алгоритм сортировки qsort работает в худшем случае N^2, а в среднем N log N
  • Докажите, что алгоритм слиянием (merge sort) работает в худшем случае N log N
  • Топологическая сортировка: условие задачи, алгоритм решения, оценка сложности алгоритма.
  • Поиск кратчайшего пути в взвешенном графе: условие задачи, алгоритм решения, оценка сложности алгоритма.