Вопросы для специализации "Теоретическая информатика"

I. Математика

Предполагается оперативное владение основами

  • дискретной математики и математической логики (отображения и отношения и их свойства. транзитивное замыкание отношения, эквивалентность, отношения порядка, логика высказываний, кванторы, метод математической индукции),
  • математического анализа (предел, обозначения O( ) и o( ), умение корректно доказывать и применять асимптотические оценки, при необходимости переформулируя в "терминах эпсилон и дельта", непрерывность, производная, первообразная, дифференциал, нахождение экстремума функции от одной и от многих переменных, формула Тейлора),
  • теории вероятности (зависимые и независимые события, условные вероятности, формула полной вероятности, математическое ожидание, второй момент, неравенства Маркова и Чебышева),
  • алгебры и теории чисел (группы, поля, кольца, факторизация, идеал, сравнения, алгоритм Евклида, теоремы Эйлера и Ферма, кольцо многочленов, число корней многочлена, линейные пространства и операторы, базис, размерность, ранг, собственные числа и собственные вектора, собственный базис, характеристический многочлен).

II. Алгоритмы и структуры данных

Общая алгоритмическая культура, включающая понимание того, как можно

  • хранить данные (массив, список, более сложные структуры),
  • искать нужные данные (поиск заданного элемента, наибольшего элемента),
  • сортировать данные.

III. Примеры тестовых задач

По алгоритмам и структурам данных (кроме объяснения алгоритма может потребоваться написать программу на любом распостранённом языке)

  • Дана группа из N человек. Каждый человек в этой группе имеет уникальный номер от 1 до N.
    Какие-то члены этой группы знакомы друг с другом, какие-то нет.
    В этой группе есть один и только один особенный человек (будем называть его "звезда"),
    который отличатся от других членов группы тем, что его знают все, а он не знает никого.
    Существует функция (уже реализована):

    bool first_knows_second(int first, int second);

    Эта функция возвращает true, если first знает second, в противном
    случае, возвращает false.
    Какого количество вызовов этой функции необходимо и достаточно, что бы
    найти в этой группе звезду?

  • Дан массив a[1]...a[N].
    Найти m,k (m<k) такие, что сумма a[m]+...+a[k] максимальна.
    Количество операций должно быть O(N).