Раздел 5. Алгебра

27. Ранг матрицы над полем, способы его вычисления. Ранг произведения матриц. Обратная матрица и способы ее вычисления.

28. Кольца вычетов. Малая теорема Ферма. Сравнения первой степени. Китайская теорема об остатках.

29. Кольцо многочленов над кольцом с единицей. Делимость многочленов с остатком. Теорема Безу.

30. Делимость многочленов над полем. Наибольший общий делитель (НОД) и наименьшее общее кратное многочленов. Взаимно простые многочлены и их свойства. Неприводимые многочлены и их свойства. Каноническое разложение многочлена и его однозначность.

31. Группы и их основные свойства. Смежные классы по подгруппе, теорема Лагранжа. Циклические группы. Конечные абелевы группы.

32. Подстановки конечных множеств, их четность. Разложение подстановок в произведение независимых циклов.

33. Векторные пространства над полем, их базисы и размерность. Координаты векторов в базисе и их изменение при переходе к другому базису. Свойства конечномерных векторных пространств. Подпространства векторного пространства, операции над ними. Размерности суммы и пересечения подпространств.

34. Транзитивные и примитивные группы подстановок. Сопряженность подстановок в симметрической группе, уравнения Коши.

35. Системы образующих групп. Понятия свободной группы. Подгруппы свободных групп.

36. Примеры системы образующих элементов симметрической и знакопеременной групп подстановок, оценки длины групп относительно этих систем образующих. Описание групп подстановок, порождаемых наборами транспозиций.

37. Нормальные делители группы. Факторгруппа, теорема об эпиморфизме.

38. Конечные поля, характеристика поля, число элементов, теорема о примитивном элементе. Существование поля с заданным примарным числом элементов. Описание подполей.

39. Неприводимые многочлены над конечными полями. Существование неприводимых многочленов данной степени над конечным полем. Построение конечного поля с заданным числом элементов.

40. Линейные рекуррентные последовательности (ЛРП) над полем. Характеристический многочлен. Семейства ЛРП. Минимальный многочлен, способы его нахождения.

41. Периодические последовательности и ЛРП. Нахождение периодов многочленов и ЛРП над конечными полями. Многочлены и ЛРП максимального периода над GF(q).

Раздел 6. Математическая логика и теория алгоритмов

42. Булевы функции. Представление булевых функций формулами алгебры высказываний и многочленами Жегалкина.

43. Псевдобулевы функции и их представление рядами Фурье.

44. Замкнутые классы функций. Критерии полноты для булевых функций.

45. Основные подходы к формализации понятия алгоритма: машины Тьюринга, рекурсивные функции, нормальные алгоритмы Маркова.

46. Понятие сложности алгоритма. Классы сложности.

47. Дискретное преобразование Фурье и его связь с задачами вычисления значений и интерполяции многочленов. Алгоритм быстрого преобразования Фурье (БПФ).

Раздел 7. Теория информации и кодирования

48. Понятие энтропии, свойства энтропии. Теоремы Шеннона о пропускной способности канала связи.

49. Линейный код и способы его задания. Число линейных (n,k)-кодов. Процесс декодирования линейного кода.