Комментарии к списку вопросов

КОНТРОЛЬНАЯ РАБОТА №1

Указания по выбору варианта

Контрольная работа №1 является контрольной работой по главам «Основы теории чисел» и «Отображения и их свойства». Контрольная работа состоит из теоретической и практической частей и содержит 20 вариантов. Студент должен обстоятельно ответить на 2 вопроса из теоретической части (27 вопросов) в соответствии со своим вариантом (табл. 1). Практическая часть состоит из 8 задач и содержит 20 типовых вариантов (табл. 3–10). Выбор номера варианта вопросов и задач осуществляется преподавателем и указывается в сводной таблице вариантов для студентов группы.

Таблица 1

Варианты теоретических вопросов

№ варианта	№№ теоретич. вопросов
	2, 27
	4, 25
	6, 23
	8, 21
	10, 19
	12, 17
	14, 18
	16, 20
	1, 22
	3, 24
	5, 26
	7, 17
	9, 20
	11, 23
	13, 26
	15, 25
	4, 27
	7, 24
	10, 21
	14, 19

Теоретическая часть (вопросы)

1. Целые числа и их свойства. Теорема о делении с остатком. Примеры.

2. Делимость целых чисел. Свойства делимости целых чисел. Примеры.

3. Общий делитель (ОД) и наибольший общий делитель (НОД) целых чисел. Свойства НОД. Нахождение НОД из теоремы о делении с остатком. Примеры.

4. Алгоритм Евклида нахождения НОД целых чисел. Рекурсивное вычисление НОД. Соотношение Безу для НОД целых чисел.

5. Общее кратное (ОК) и наименьшее общее кратное (НОК) целых чисел. Свойства НОК. Рекурсивное вычисление НОК. Связь НОД и НОК целых чисел. Примеры.

6. Простые натуральные числа и их свойства. Теорема о наименьшем делителе натурального числа, большего 1. Метод «решета» Эратосфена проверки чисел на простоту. Теорема Евклида.

7. Значение простых чисел. Теоремы о распределении простых чисел. Числа Мерсенна, Ферма, значения многочлена Эйлера.

8. Взаимно простые целые числа. Критерий взаимной простоты. Свойства взаимно простых чисел.

9. Основная теорема арифметики. Каноническое разложение целого числа. Нахождение НОД и НОК целых чисел по их каноническим разложениям.

10. Диофантовы линейные уравнения. Критерий разрешимости уравнения. Теорема о решении уравнения с двумя неизвестными. Алгоритм решения уравнения с двумя неизвестными. Приложения диофантовых линейных уравнений.

11. Сравнимость целых чисел по натуральному модулю. Свойства сравнений. Примеры.

12. Множество классов вычетов по натуральному модулю. Свойства операций сложения и умножения классов вычетов. Таблицы Кэли. Примеры.

13. Обратимый класс вычетов. Свойства классов вычетов в зависимости от НОД их представителей и модуля. Критерий обратимости класса вычетов. Обратимость классов вычетов по простому модулю.

14. Функция Эйлера и ее вычисление. Примеры.

15. Теорема Эйлера и следствие из нее. Малая теорема Ферма и следствия из нее.

16. Решение линейных сравнений с одним неизвестным в целых числах. Примеры.

17. Соответствия, отображения, функции и их разновидности. Области отправления, прибытия, определения, значений соответствия. График соответствия. Обратное соответствие. Примеры.

18. Способы задания функций. Композиция функций. Лемма о тождественной композиции функций. Обратная функция и критерий ее существования.

19. Сужение функции на множество. Свойства функций и их композиций. Связь инъективности и сюръективности преобразования конечного множества.

20. Взаимно однозначное соответствие. Равномощные множества. Мощность конечного множества. Критерий равномощности конечных множеств. Общее число взаимно однозначных соответствий для двух n-элементных множеств.

21. Мощность декартова произведения конечных множеств и мощность декартовой степени конечного множества. Мощность булеана конечного множества. Число всех k-элементных подмножеств n-элементного множества.

22. Счетное множество. Счетность бесконечного подмножества множества натуральных чисел. Счетность множеств целых и рациональных чисел. Свойства счетных множеств.

23. Несчетное множество. Теорема Кантора. Диагональный метод Кантора. Мощность континуум. Примеры континуальных множеств.

24. Свойства несчетных множеств. Равномощность интервала (0; 1) и полу-интервала (0; 1], интервала (0; 1) и отрезка [0; 1]. Равномощность интервалов (0; 1) и (a; b), (c; d) и (a; b). Континуальность множества всех вещественных чисел и булеана счетного множества. Несуществование множества максимальной мощности. Парадокс Кантора «множество всех множеств» и его разрешимость.

25. Понятия шифрования и расшифровывания, классического шифра, криптологии, криптографии, криптоанализа, вскрытия шифртекста, стойкости шифра. Классические шифры замены и простой однобуквенной замены (шифр Цезаря). Примеры.

26. Классические шифры перестановки: «сцитала», «поворотная решетка», «вертикальная перестановка». Примеры.

27. Многоалфавитные шифры замены. Шифр Виженера и методы его дешифровки. Примеры.

Комментарии к списку вопросов

Требования к ответам на вопросы при написании контрольных работ и на экзамене одинаковы. На оценки «4» и «5» доказательства не обязательны (кроме вопросов 22 и 24): нужно знать определения, формулировки лемм, теорем, следствий и свойств, самостоятельно уметь приводить примеры. На оценки «6»–«10» дифференцированно требуются также и доказательства утверждений, что указано ниже, в табл. 2. В случае отсутствия номера вопроса или названия утверждения в табл. 2 на все оценки при ответе требуется приводить лишь формулировки, это касается и тех утверждений, которые приводились в теоретическом разделе без доказательств.

Таблица 2

Требования к ответам на вопросы

№ вопроса	Названия утверждений (их номера в теоретическом разделе)	На какую оценку требуются доказательства
	Теорема о делении с остатком (1.1.1)	«6»–«10»
	Свойства делимости целых чисел (1–7)	«6»–«10»
	Свойства НОД целых чисел (1–4). Теорема о нахождении НОД из теоремы о делении с остатком (1.2.1)	«6»–«10»
	Теорема-алгоритм Евклида нахождения НОД целых чисел (1.2.2). Соотношение Безу для НОД целых чисел (1.2.3) и следствие	«6»–«10»
	Свойства НОК целых чисел (1–4)	«6»–«10»

Продолжение табл. 2

	Теорема о наименьшем делителе натурального числа, большего 1 (1.3.1). Свойства простых чисел (1, 2). Теорема Евклида (1.3.2)	«6»–«10»
	Теорема об отрезке натурального ряда, все числа которого составные (1.3.4)	«6»–«10»
	Критерий взаимной простоты чисел (1.4.1). Свойства взаимно простых чисел (1–4)	«6»–«10»
	Основная теорема арифметики (1.4.2)	«6»–«10»
	Критерий разрешимости диофантова линейного уравнения (1.5.1)	«6»–«10»
	Теорема о нахождении решений диофантова линейного уравнения с двумя неизвестными (1.5.2)	«7»–«10»
	Теорема о трех эквивалентных условиях сравнимости целых чисел по натуральному модулю (1.6.1). Свойства сравнений (1–9)	«6»–«10»
	Свойства операций сложения и умножения классов вычетов (1–5)	«6»–«10»
	Леммы о свойствах классов вычетов с представителями, взаимно простыми (1.7.1) и не взаимно простыми с модулем (1.7.2). Теорема о необходимом и достаточном условии обратимости класса вычетов и произведении обратимых классов (1.7.1). Следствие об обратимости классов вычетов по простому модулю	«6»–«10»
	Теорема о вычислении значений функции Эйлера (1.7.2)	«8»–«10»
	Теорема Эйлера (1.7.3)	«7»–«10»
	Следствие из теоремы 1.7.3. Малая теорема Ферма (1.7.4), следствия 1 и 2 из нее	«6»–«10»
	Решение линейных сравнений с одним неизвестным в целых числах (описание методики)	«6»–«10»
	Лемма о тождественной композиции функций (2.1.1). Теорема-критерий существования обратной функции (2.1.1)	«6»–«10»
	Свойства функций и их композиций (1–7). Теорема о связи инъективности и сюръективности преобразования конечного множества (2.1.2)	«6»–«10»
	Критерий равномощности конечных множеств (2.2.1). Теорема об общем числе взаимно однозначных соответствий для двух n-элементных множеств (2.2.2)	«6»–«10»
	Теорема о мощности декартова произведения конечных множеств (2.2.3). Теорема о мощности булеана конечного множества (2.2.4)	«6»–«10»
	Счетность бесконечного подмножества множества натуральных чисел, множеств целых и рациональных чисел. Свойства счетных множеств: конечное объединение счетных множеств и счетное объединение конечных множеств счетны	«4»–«10»
	Теорема Кантора (2.2.5)	«6»–«10»

Окончание табл. 2

	Доказательства равномощности интервала (0; 1) и по-луинтервала (0; 1], интервала (0; 1) и отрезка [0; 1], интервалов (0; 1) и (a; b), (c; d) и (a; b). Доказательство континуальности множества R	«4»–«10»
	Доказательство континуальности булеана счетного множества	«6»–«10»

Практическая часть

Задача №1

Найти (а, b) и записать соотношение Безу, используя расширенный алгоритм Евклида или его обратную прогонку. Значения a и b даны в табл. 3 в соответствии с вариантом.

Таблица 3