1. Контрольные вопросы

1. Назовите 2 класса методов поиска подстроки.

2. Какие методы поиска с предварительным анализом вы знаете?

3. Назовите главный недостаток прямого поиска.

4. Дайте краткое описание алгоритма КМП.

5. Дайте краткое описание алгоритма БМ.

120. Лабораторная работа №10. Вычислительные алгоритмы

     1. Цель работы

Приобретение навыков реализации простейших вычислительных алгоритмов.

2. Содержание работы

Реализация вычислительных алгоритмов представляет собой важный, но достаточно специфический раздел программирования. Главная особенность состоит в том, что подобные алгоритмы часто являются итерационными. Основную проблему при этом составляет теоретический и практический контроль за величиной вычислительной погрешности.

1. Программа работы и последовательность выполнения

1. Создайте новый проект. Процессор – dsPIC33FJ256GP710.

2. Подключите необходимые библиотеки.

3. Подключите отладчик (симулятор), встроенный в среду MPLABIDE.

4. Разработать программу, выполняющую

   № Варианта	Задание
   1	Нахождение всех простых чисел в диапазоне от 1 до 100.
   2	Нахождение 7!
   3	Нахождение всех чисел Фибоначчи в диапазоне от 1 до 100.
   4	Дано целое число. Получить целое число, записанное теми же цифрами в обратном порядке.
   5	Вычисление разложения натурального числа на простые множители.
   6	Вычисление наименьшего общего делителя двух чисел.
   7	Нахождение суммы всех простых чисел в диапазоне от 100 до 200.
   8	Нахождение произведения всех простых чисел в диапазоне от 1 до 20.
   9	Нахождение суммы всех чисел Фибоначчи в диапазоне от 1 до 20.
   10	Нахождение произведения всех чисел Фибоначчи в диапазоне от 1 до 20.
   11	Перевод числа из шестнадцатеричной системы счисления в двоичную
   12	Перевод числа из двоичной системы счисления в шестнадцатиричную

5. Открыть окно Watchи внести в него все регистры, которые используются в коде. В пошаговом режиме отладить код, контролируя изменение регистров в окнеWatch. После отладки программы, показать код и результаты работы программы преподавателю.

6. Создать блок схему программы.

7. Подготовить отчет.

1. Контрольные вопросы

1. Какие простейшие вычислительные алгоритмы вы знаете?

2. Что такое простые числа?

3. Что такое числа Фибоначчи?

121. Лабораторная работа №11. Алгоритмы шифрования

     1. Цель работы

Приобретение навыков реализации простейших алгоритмов шифрования

1. Содержание работы

1. 11.1 Шифрование на основе операции XOR.

Как известно из булевой алгебры, операция логического сложения «⊕» по модулю 2 (или логического исключаещего ИЛИ — XOR) имеет следующую семантику:

x	y	x ⊕ y
0	0	0
0	1	1
1	0	1
1	1	0

То есть, операция z = x ⊕ y по сути поразрядная (побитовая — результат не зависит от соседних битов). Если только один из соответствующих битов равен 1, то результат 1. А если оба 0 или оба 1, то результат 0. Если внимательно посмотреть на результат применения XOR к двум двоичным числам, то можно заметить, что мы можем восстановить одно из слагаемых при помощи второго: x = z ⊕ y или y = z ⊕ x.

Отсюда можно сделать следующие выводы: зная число y и применяя XOR к x, мы получим z. Затем, мы, опять же используя y, получим из z обратно число x. Таким образом мы можем преобразовать последовательность чисел (x)_i в последовательность (z)_i. Теперь мы можем назвать число y кодирующим (или шифрующим) ключом. Если человек не знает ключа, то он не сможет восстановить исходную последовательность чисел (x)_i. Но если (x)_i являются байтовым представлением букв текста, то опытный пользователь сможет вскрыть зашифрованный текст. Поскольку каждая буква будет представлена в шифротексте одним и тем же кодом z, то воспользуясь частотным словарем взломщик сможет вычислить шифрующий ключ y, если у него будет в распряжениии достаточно длинный шифротекст.

В свете последних рассуждений приходим к мысли, что напрямую кодировать простой текст нельзя. Во-первых, число, представляющее пробел, будет по-прежнему разделять слова и в шифротекте. Выделив это часто встречающееся одно и то же число, пользователь догадается, что это закодированный пробел. Во-вторых, короткие часто встречающиеся предлоги и союзы также помогут взломщику в определении ключа. Поэтому самым эффективным способом является использование длинного ключа, покрывающего несколько букв, а лучше равного по длине самому сообщению. Так, если мы кодируем достаточно длинное сообщение (не менее 5-10 предложений) с помощью случайного ключа такой же длины, то такое сообщение очень сложно расшифровать. Еще более высоких результатов по надежности можно достичь, если перед шифрованием произвести, например, сжатие текста каким-либо архиватором. Плюс к тому же, если сообщение имеет малую длину, можно добавить в начало и конец сообщения случайные последовательности символов. Проиллюстрируем вышеупомянутые умозаключения на примере на языке Си. Итак, сначала генерируем ключ в файл, который надо будет скрытно передать своему товарищу, с которым мы собираемся обмениваться секретными сообщениями: