Вопросы для собеседования по специализации "Алгоритмы и анализ данных в биоинформатике"

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

Уверенное знание алгоритмов и структур данных:

  • Эффективное хранение и поиск данных (массивы, списки, сортировки, кучи, хэш-таблицы, суффиксные деревья, B-деревья, сжатие данных).
  • Построение и анализ деревьев и графов (поиск в глубину/ширину, поиск минимальных путей, минимальное остовное дерево, максимальный поток).
  • Эвристики и приближённые алгоритмы для сложных задач.

Осведомлённость о последних алгоритмических достижениях приветствуется.

II. Программирование

Умение программировать основные алгоритмы и выражать в коде свои идеи:

  • Общие понятия процедурного программирования, компьютерной архитектуры (фон Неймана).
  • Базовые знания языка С++ или Java.

III. Дискретная математика

Уверенное владение дискретной математикой и комбинаторикой (сочетания, перестановки, биномиальные коэффициенты, целочисленные последовательности, основы теории графов).

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

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

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

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

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

  • Дана строка S над 4-х буквенным алфавитом {A, C, G, T} и число K.
    Найти строку длины K, которая встречается в S чаще всего.
    Найти среднее число повторений подстрок длины K в S. Можно ли сделать это быстрее, чем за O(K*|S|)?

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

    bool first_knows_second(int first, int second);

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

  • Дана строка S и множество строк P = {s_1, s_2, ..., s_n}.
    Какие дополнительные структуры данных размером меньше O(|S|) необходимы, чтобы эффективно выполнять запросы вида "для данной позиции x (0 <= x < |S|) вывести все подстроки из P, вхождение которых в S включает позицию x"?