2023
2022
2021
2020
2019
2018
2017
2016
Алгоритмы на строках.
максимальный балл 4
(0.5) Продемонстрировать работу алгоритма Рабина-Карпа для поиска образца abbabcac в тексте abbcbcbcbabcbcbabbabcacbc
(1) Продемонстрировать работу алгоритма Кнутта-Мориса-Прата для поиска образца abcababcacbbabcabc в тексте abcababcacababcaccabcababcacbbabcabcabcacbbabcabc
(1) Написать программу, реализующую алгоритм Рабина-Карпа для нуклеотидных последовательностей. Продемонстрировать зависимость времени работы от длины исходного образца и текста.
(1.5) Написать программу, реализующую алгоритм Кнутта-Мориса-Прата. Продемонстрировать зависимость времени работы от длины исходного образца и текста.
(3) Модифицировать алгоритм Рабина-Карпа для поиска образца с заданным числом замен в нуклеотидной последовательности, реализовать в виде компьютерной программы.
(4) Решить задачу отсюда: http://acm.timus.ru/problem.aspx?space=1&num=1590 Зарегистрироваться на сайте (описано в хэлпе), отправить решение, убедиться, что оно верное, показать это преподавателям. Задание без строгого дэдлайна, на интерес.
Про работу с двоичными числами
Эпиграф
- 0 программистов ругал сердитый шеф,
- 1 из них уволился, и стало их 0xff
— Песенка про 10 маленьких программистов
- Из недостающих у вас знаний питона: В питоне возможно работать с целыми числами в двоичном представлении. Для этого в питоне есть операции:
1 z = x | yОперация "побитовое ИЛИ" для двух чисел. Т.е. мы представляем два числа в двоичной форме, выписываем их друг под другом так, чтобы младшие разряды совпали и дописываем сверху недостающих нулей, и после этого проходим по разрядам и каждую пару двоичных цифр числа рассматриваем как логические значения – 1 значит истина, 0 значит ложь.
Поэтому, например, 7 | 130 = 00000111 | 10000010 = 10000111 = 135
1 z = x & yОперация "побитовое И" для двух чисел. Пример: 7 & 130 = 00000111 & 10000010 = 00000010 = 2
1 z = x ^ yОперация "побитовое XOR (исключающее ИЛИ)". a XOR b истинно тогда и только тогда, когда истинно РОВНО ОДНО из двух значений: a или b. Поэтому: 7 ^ 130 = 00000111 ^ 10000010 = 10000101 = 133.
1 z = x << nОперация побитового сдвига влево сдвигает на n разрядов налево двоичное представление числа x и заполняет вновь появившиеся разряды нулями. Вдумчивый читатель может заметить, что `x << n == x * 2 ** n'.
1 z = x >> nОперация побитового сдвига направо действует аналогичным образом. При этом разряды, оказавшиеся правее десятичной точки, просто стираются. Таким образом, x >> n == x / 2 ** n.
Все перечисленные выше операции можно считать выполняемыми за константное время и 5-е задание должно к ним сводиться.1
Также для работы с бинарными числами удобно пользоваться шестнадцатеричным представлением числа2. Для задания в питоне числовой константы в шестнадцатеричной системе исчисления нужно написать перед ней префикс 0x. Шестнадцатеричное представление чисел удобно тем, что для получения из него двоичной записи нужно каждую цифру в нём заменить на её двоичный эквивалент.
Например, если мы хотим от числа x взять биты от 3 до 7, то мы можем сделать это так:
1 z = (x >> 2) & 0xF
- Или так:
1 z = (x & 0x3C) >> 2
С практической точки зрения здесь должна быть такая оговорка: эти операции выполняются за константное время покуда числа, которыми они оперируют, меньше размера регистра процессора. Для современных (64-битных) машин это 2**64, т.е. примерно 10 ** 20. (1)
В некоторых версиях питона имеется и родное двоичное представление чисел, но так как это не распространяется на все версии питона, то мы об этом умолчим (2)