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

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

  1. Общие понятия процедурного программирования
    • программа
    • компилятор
    • переменная
    • цикл
    • функция
    • массив
    • ветвление программы
    • рекурсия
  2. Базовые знания языка С или С++
    • основы синтаксиса
    • встроенные арифметические типа
    • опеределение переменных
    • арифметические выражения (целочисленные и вещественные)
    • циклы (for, while)
    • логические конструкции (if, if/else)
    • определение функций
    • работа со встроенными массивами
    • работа со стандартным вводом-выводом
    • основы ООП

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

Базовые знания алгоритмов, таких как

  • поиск наибольшего/наименьшего элемента в массиве
  • алгоритмы сортировки
  • двоичный поиск

Предполагается, что, если абитуриент знает некоторый алгоритм,
то он может его запрограммировать.

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

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

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

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

По программированию

  • Напишите функцию, которая по массиву double mas[100] вычисляет среднее квадратичное отклонение.
  • Есть два отсортированных массива double a[100] и double b[100].
    Напишите функцию, которая заполняет массив double c[200] числами из массивов a и b так,
    чтобы он тоже был отсортирован.

По алгоритмам и структурам данных

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

    bool first_knows_second(int first, int second);

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

  • Дан массив $a[1],\ldots,a[N]$.
    Найти $m,k$ $(m Количество операций должно быть порядка $N$.