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

Алгоритмы и комбинаторика

  1. Время работы алгоритма. Скорость роста функций (логарифм, полином, экспонента).
  2. Рекуррентные соотношения.
  3. Сортировка слиянием. Сортировка с помощью кучи.
  4. Быстрая сортировка.
  5. Нижняя оценка Ω( log ) для сортировки. Сортировка подсчетом и цифровая сортировка.
  6. Порядковые статистики.
  7. Двоичное дерево поиска. Хеш-таблица.
  8. АВЛ-дерево.
  9. Графы и способы их представления. Поиск в глубину в неориентированных графах. Связность неориентированных графов.
  10. Поиск в глубину в ориентированных графах. Ориентированные ациклические графы. Топологическая сортировка вершин.
  11. Нахождение сильно связных компонент графа.
  12. Поиск в ширину.
  13. Алгоритм Дейкстры.
  14. Кратчайшие пути при наличии ребер отрицательного веса (алгоритм Беллмана-Форда). Кратчайшие пути в ациклических ориентированных графах.
  15. Остовное дерево, поиск минимального остовного дерева.
  16. Потоки в графах, поиск максимального потока.
  17. Сочетания, перестановки, бином Ньютона, биномиальные коэффициенты и их свойства. Треугольник Паскаля.

Литература

  • S. Dasgupta, C. H. Papadimitriou, and U. Vazirani. Algorithms. McGraw-Hill, 2006.
  • T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms.The MIT Press, Cambridge, second edition, 2001.
  • А. Шень. Программирование: теоремы и задачи. М., МЦНМО, 2-е издание,2004.

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

  1. Архитектура компьютера: архитектура фон Неймана, гарвардская архитектура. (Э. Таннанбаум. Архитектура компьютера)
  2. Компиляция программ. Как устроен компилятор? Зачем нужен компилятор. Интерпретация программ. (Ахо, Сети, Ульман. Компиляторы: принципы, технологии, инструменты)
  3. Языки программирования высокого уровня. Переменные, массивы, условия, циклы. Функции. Рекурсия. (Б. Страуструп. Язык программирования C++)
  4. Объектно-ориентированное программирование. Основные принципы. (И. Грэ-хем. Объектно-ориентированные методы. Принципы и практика)
  5. Язык программирования С++. Основы синтаксиса. Встроенные типы. (Б. Страуструп. Язык программирования C++)
  6. Язык программирования С++. Массивы и структуры. (Б. Страуструп. Язык программирования C++)
  7. Язык программирования С++. Функции. (Б. Страуструп. Язык программирования C++)

Теория вероятностей

(А.А. Боровков. Теория вероятностей.)

  1. Вероятностное пространство. Независимые события. Теорема сложения. Условная вероятность. Полная система событий. Формула полной вероятности. Формула Байеса.
  2. Случайная величина и ее функция распределения. Совместное распределение случайных величин. Распределение суммы независимых случайных величин.
  3. Математическое ожидание и дисперсия случайной величины, их свойства.
  4. Неравенство Маркова. Неравенство Чебышева и закон больших чисел для испытаний Бернулли.
  5. Предельная теорема Пуассона и теорема Муавра-Лапласа для испытаний Бернулли.

Теория множеств

(Н.К. Верещагин, А. Шень. Начала теории множеств.)

  1. Множества и теоретико-множественные операции. Отображения множеств. Равномощные множества.

Алгебра

(А.Г. Курош. Курс высшей алгебры.)

  1. Системы линейных алгебраических уравнений. Теорема Кронекера-Капелли. Общее решение системы алгебраических уравнений.
  2. Матрицы, ранг матрицы, ранг произведения матриц, ранг транспонированной матрицы.
  3. Определитель матрицы. Определитель произведения.
  4. Евклидово пространство.
  5. Билинейные формы. Квадратичные формы и их приведение к каноническому виду.
  6. Многочлены, делимость, наибольший общий делитель, теорема Безу, число корней многочлена.
  7. Основная теорема алгебры.

Теория чисел

(И.М. Виноградов. Основы теории чисел.)

  1. Основная теорема арифметики.
  2. Малая теорема Ферма, функция Эйлера, ее мультипликативность. Теорема Эйлера.

Аналитическая геометрия

(А.В. Погорелов. Аналитическая геометрия.)

  1. Различные способы задания прямой и плоскости. Углы между прямыми и плоскостями. Формулы расстояния от точки до прямой и плоскости.

Математический анализ

(В.М. Зорич. Математический анализ; Г.М. Фихтенгольц. Курс дифференциального и интегрального исчисления.)

  1. Теорема Больцано-Вейерштрасса и критерий Коши для числовой последовательности.
  2. Два определения предела функции одной и нескольких переменных: с помощью окрестностей и через пределы последовательностей.
  3. Свойства функций, непрерывных на ограниченных замкнутых множествах в R п . Теорема о равномерной непрерывности.
  4. Производные и дифференциалы функции одной и нескольких переменных. Достаточные условия дифференцируемости функции в точке. Теорема Лагранжа о среднем (формула конечных приращений).
  5. Выпуклые функции. Выпуклость и вторая производная.
  6. Исследование функции одной переменной с помощью производных: возрастание или убывание, экстремумы, выпуклость или вогнутость, точки перегиба. Асимптоты.
  7. Определенный интеграл и его свойства. Интегрируемость непрерывной функции. Формула Ньютона-Лейбница.
  8. Числовые ряды. Абсолютная и условная сходимость.
  9. Формула Тейлора.