Сортировка.

48. Быстро отсортировать массив из 16 элементов слияниями

Сложность алгоритма

обусловлена масштабирующим соотношением , начальное условие(т.к. массив из одного элемента всегда упорядочен).

(иллюстрируется рисунком)

Проверим

49. отсортировать массив из первых 6-7 элементов предыдущего массива пузырьком. Для контроля числа операций проделать каждую операцию в отдельной строке ( всего 15-25 строк).

Алгоритм Карацубы.

50. Алгоритмом Анатолия Карацубы перемножить 2 8-ми значных числа. Масштабное соотношение. (Использовать формулы… св этом стилеуровня рекурсии

Алгоритм Штрассена быстрого перемножения матриц.

51. Алгоритмом Штрассена перемножить 2 матрицы 4х4

.

, уровня рекурсии. Операцию повторить только при (повторном) подсчете НАИБОЛЕЕ сложных в ДАННОМ Условии матриц.,(и только их). Проверка – прямым перемножением. Презентация теория алгоритмов.

Криптография

Таблица кодировка букв из Ф.И.О.

а

б

В

г

д

е

ё

ж

з

и

й

к

л

м

н

о

п

o1

o2

o3

o4

o5

o6

o7

o8

o9

10

11

12

13

14

15

16

17

р

с

Т

у

ф

х

ц

ч

ш

щ

ъ

ы

ь

э

ю

я

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

В случае непопадания буквы в модуль или её попадания в исключения берётся первая СНАЧАЛА ПОДХОДЯЩАЯ буква ФАМИЛИИ

Все операции умножения заканчиваются взятием модуля. Для облегчения расчетов допускается использование отрицательных чисел. Возводить числа в степень больше 2 без взятия модуля запрещено. Запрещено перемножать более 2х чисел без взятия модуля.

Освоение вычетов.

Таблица умножения в конечных полях.

Пример:

52. Составить таблицу умножения по модулю , еслиперейти к выполнению, иначе добавить/вычесть целое число кратное 10 (как правило 10), так чтобы неравенствобыло выполнено (т.е. последний разряд Никогда НеМЕНЯЕТСЯ…). Найти порождающий элемент (иначе доказать его отсутствие). Для этого и перед этим построить таблицу обращения. Построить таблицу дискретного логарифма ПО ОСНОВАНИЮ ПОРОЖДАЮЩЕГО Элемента. Сделать 2-3 раза перемножения элементов (чтобы сумма оснований превосходила порядок МУЛЬТИПЛИКАТИВНОЙ Группы)

Алгоритм Евклида.

53. (1 задача) Алгоритмом Евклида обратить , исключения

54. вычислить алгоритмом Евклида

    1. “abc”^-1 mod 997 (где "abc"=100a+10b+c).

    2. , где,

    3. , где,

    4. “ab”^-1 mod 997, где "ab"=10a+b.

Пример

Пример2:

Алгоритм Масси-Омуры

55. (~2 задачи) Алгоритмом Масси-Омуры использовав ,, закодировать и раскодировать первую букву фамилии в диапазоне от 2 до 29. Если буква не подходит взять первую подходящую от начала фамилии, - сначала проверить вторую (и т.д.) Использовать(для облегчения расчёта применять). Исключения 25 и 5(при их наступлении взять следующую букву).

Пример (Фамилия Ёжиков). Букве Ё соответствует текст 07.

Последовательно вычисляем первый шифр, (),

второй шифр, , третий, и итоговое полученное сообщение.

56. В алгоритме Масси-Омуры. Можно применять модуль , с парой. Обратные вычислить алгоритмом Евклида. (для облегчения расчёта применять). Букве И соответствует 10.