Programming Taskbook

Электронный задачник по программированию

©  М. Э. Абрамян (Южный федеральный университет, Университет МГУ-ППИ в Шэньчжэне), 1998–2024

Скачать дистрибутив электронного задачника Programming Taskbook for Bioinformatics (русская версия 1.1)

Скачать дистрибутив электронного задачника Programming Taskbook/PascalABC for Bioinformatics (русская версия 1.0 для системы PascalABC.NET)

Общее описание

Программный комплекс «Электронный задачник по строковым алгоритмам биоинформатики Programming Taskbook for Bioinformatics» (PT for Bio) содержит дополнительные компоненты электронного задачника Programming Taskbook, которые позволяют выполнять задания, связанные с алгоритмами строкового поиска и неточного сопоставления строк. Имеется вариант данного комплекса, предназначенный для использования совместно с задачником Programming Taskbook, интегрированным в среду PascalABC.NET.

Для возможности использования данного комплекса его следует установить в системный каталог базового варианта электронного задачника Programming Taskbook версии не ниже 4.10 (обычно системным каталогом задачника является каталог C:\Program Files\PT4). Вариант комплекса, предназначенный для использования в среде PascalABC.NET, должен устанавливаться в подкаталог PT4 системного каталога среды PascalABC.NET (обычно это каталог C:\Program Files\PascalABC.NET).

Версия 1.1 комплекса PT for Bio дополнительно содержит 64-разрядные варианты библиотек с группами заданий, что позволяет использовать ее для 64-разрядных сред программирования (при наличии базового варианта задачника Programming Taskbook версии 4.21 или выше).

Комплекс PT for Bio является свободно распространяемым программным продуктом (freeware); он может использоваться как с полным вариантом задачника PT4Complete–1100, так и со свободно распространяемым мини-вариантом PT4Mini–270.

В состав задачника PT for Bio входят группы Match (80 заданий, посвященных базовым алгоритмам поиска вхождений образца в текст) и Align (80 заданий, связанных с различными алгоритмами неточного сопоставления строк).

Группа Match содержит следующие подгруппы (в скобках указывается количество заданий в подгруппе):

• поиск подстрок: базовые понятия и наивный алгоритм (8),
• основной препроцессинг: базовые понятия и быстрый алгоритм (8),
• поиск с использованием основного препроцессинга (4),
• метод Кнута–Морриса–Пратта (5),
• препроцессинг для метода Кнута–Морриса–Пратта (9),
• метод реального времени (4),
• правила сдвига по плохому символу и по хорошему суффиксу (14),
• метод Бойера–Мура (8),
• битовый метод поиска точных и неточных вхождений (9),
• метод дактилограмм Карпа–Рабина (11).

Группа Align содержит следующие подгруппы:

• редакционное расстояние и оптимальное редакционное предписание (11),
• модификации редакционного расстояния (12),
• глобальное выравнивание строк (14),
• модификации глобального выравнивания (15),
• приближенные вхождения строк и локальное выравнивание (13),
• нахождение наибольшей общей подпоследовательности (15).

Задания могут выполняться на любых языках и в любых программных средах, поддерживаемых базовым вариантом электронного задачника Programming Taskbook.

Задачник PT for Bio предоставляет при выполнении заданий те же возможности, что и базовый задачник Programming Taskbook; в частности, он передает программе учащегося исходные данные, проверяет правильность результатов, полученных программой, и сохраняет сведения о каждом тестовом испытании программы в специальном файле. Кроме того, в задачнике PT for Bio предусмотрены дополнительные возможности, связанные со спецификой изучаемой предметной области (строковые алгоритмы поиска и сопоставления):

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

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

Многие задания посвящены изучению новых строковых характеристик, используемых в том или ином алгоритме. Подобные задания знакомят с алгоритмами вычисления этих характеристик; кроме того, анализ полученных значений характеристик дает возможность более глубоко понять идеи, лежащие в основе соответствующих алгоритмов.

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

Последовательность изучаемых алгоритмов соответствует, в основном, порядку их изложения в книге Д. Гасфилда «Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология» (СПб.: БХВ-Петербург, 2003), которая является одним из наиболее полных руководств на русском языке по изучению строковых алгоритмов биоинформатики. Группа Match охватывает большинство алгоритмов, описанных в части I данной книги («Точное совпадение строк: основная задача»); в группе Align рассматриваются алгоритмы, приведенные в первых двух главах части III («Неточное сопоставление, выстраивание последовательностей и динамическое программирование»).

Программный комплекс «Электронный задачник по строковым алгоритмам биоинформатики Programming Taskbook for Bioinformatics» зарегистрирован в Реестре программ для ЭВМ 28 февраля 2013 г. (свидетельство о государственной регистрации программы для ЭВМ номер 2013612450).

Разработка сайта:
М. Э. Абрамян, В. Н. Брагилевский

Последнее обновление:
01.01.2024