Kodomo

Пользователь

Учебная страница курса биоинформатики,
год поступления 2011

Алгоритмы на строках.

  1. (0.5) Продемонстрировать работу алгоритма Рабина-Карпа для поиска образца abbabcac в тексте abbcbcbcbabcbcbabbabcacbc

  2. (1) Продемонстрировать работу алгоритма Кнутта-Мориса-Прата для поиска образца abcababcacbbabcabc в тексте abcababcacababcaccabcababcacbbabcabcabcacbbabcabc

  3. (1) Написать программу, реализующую алгоритм Рабина-Карпа для нуклеотидных последовательностей. Продемонстрировать зависимость времени работы от длины исходного образца и текста.

  4. (1.5) Написать программу, реализующую алгоритм Кнутта-Мориса-Прата. Продемонстрировать зависимость времени работы от длины исходного образца и текста.

  5. (3) Модифицировать алгоритм Рабина-Карпа для поиска образца с заданным числом замен в нуклеотидной последовательности, реализовать в виде компьютерной программы.

  6. (4) Решить задачу отсюда: http://acm.timus.ru/problem.aspx?space=1&num=1590 Зарегистрироваться на сайте (описано в хэлпе), отправить решение, убедиться, что оно верное, показать это преподавателям. Задание без строгого дэдлайна, на интерес.

Про работу с двоичными числами

Эпиграф

  • 0 программистов ругал сердитый шеф,
  • 1 из них уволился, и стало их 0xff

— Песенка про 10 маленьких программистов

  1. С практической точки зрения здесь должна быть такая оговорка: эти операции выполняются за константное время покуда числа, которыми они оперируют, меньше размера регистра процессора. Для современных (64-битных) машин это 2**64, т.е. примерно 10 ** 20. (1)

  2. В некоторых версиях питона имеется и родное двоичное представление чисел, но так как это не распространяется на все версии питона, то мы об этом умолчим (2)