Программа 3 семестр ФИВТ
План семинаров
Задачи, приведённые после программы, примерно соответствуют семинарам — по одной задаче на семинар или два семинара.
Первые два семинара — повторение структур данных, изученных в прошлом году.
По сути, вспоминаем STL, а именно, контейнер
map.
На первом же занятии всем студентам дать задание зарегистрироваться на
http://acm.mipt.ru/judge.
Для этого нужен доступ к почтовому ящику.
Семинар 1. Повторение материала прошлого года. Различные реализации интерфейса (абстрактного типа данных, АТД) "ассоциативный массив": дерево поиска, сбалансированное дерево поиска (АВЛ или красно-чёрное), хэш-таблица с открытой и закрытой адресацией. Оценка времени. Напишите реализации абстрактных структур данных "ассоциативный массив" и "очередь с приоритетом" либо используйте существующие контейнеры в библиотеке STL. Решите задачу "Радио"
PROBLEM:130. Поясните, как при решении этой задачи ограничиться только контейнером
map. Поскольку это повторение, то необходимо к концу семинара получить (совместным трудом) работающий код для задачи "Радио". Теория, связанная с этой задачей, будет рассказана на лекции.
Семинар 2. Изучаем STL. Чем тличаются контейнеры vector, set, map? Как можно использовать set как очередь с приоритетом? Читаем
CS WIKI и начинаем коллективно писать учебные материалы по STL. Повторяем задачу
10 самых частых слов (решение с использованием STL). Что такое iterator и reverse_iterator? Что такое begin, end и rbegin, rend? Рассмотреть шаблон pair (не лекции про него не было рассказано).
Семинар 3. Обсудить способы хранения графа в памяти. Рассказать про жадные алгоритмы. Обсудить это на примере задачи "Стабильный коллектив" (
PROBLEM:106). В конце семинара обсудить код
Algorithms.HarmoniousGroup. Разобрать встретившиеся непонятные моменты в коде.
Семинары 4,5. Напишите библиотеку, которая позволяет после препроцессинга теста быстро находить все места, где встречается заданная строка. Если успеете, реализуйте суффиксный массив согласно описанию, данному на
Algorithms.SuffixArray (переведите с языка Ruby на язык Си++) или структуру данных "Суффиксное дерево". Интерфейс библиотеки может быть таким:
// создает индекс для заданного текста
index* create_index(const char *text);
// возвращает массив ссылок на места, где встречается слово;
// за освобождение этого массива отвечает вызывающая сторона
char** lookup(index *idx, const char *word);
Вы можете дополнить этот интерфейс и сделать его объектно-ориентированным. Протестируйте свою библиотеку. Напишите к ней документацию. Выполнять задачу следует пошагово:
- Начать с создания массива суффиксов, то есть просто указателей типа char*:
int n = strlen(text);
char ** suffix_array = (char**)malloc(n);
char *p; char **a = suffix_array;
for(p = text; *p; p++, a++ ) *a = p;
- Отсортировать их с помощью
qsort:
int cmp_suffix(char **a, char **a) {
return strcmp(*a, *b);
}
int main() {
...
// препроцессинг — сортировка массива суффиксов
qsort(suffix_array, n, sizeof(char*), cmp_suffix);
...
} int l = 0, r = n;
char *search_word = "искомая строка";
int search_word_len = strlen(search_word);
while ( r - l > 1) {
c = (l + r) / 2;
if ( strncmp(search_word, suffix_array[c], search_word_len) >= 0 ) {
l = c;
} else {
r = c;
}
}
// нашли место l
int count = 0;
char str[256];
for( ;strncmp(search_word, suffix_array[l], search_word_len) == 0; l++, count++) {
// копируем 20-буквенную окрестность найденного слова в str
strncpy(str, max(text, suffix_array[l] - 20), search_word_len + 40);
printf("Case %4d: ... %s ...\n", count, str);
}
printf("Итого найдено %d мест\n", count);
- Далее нужно проверить код на работоспособность
- на длинном тексте из случайных букв
- на длинном тексте, где используются только 2 буквы или только 3 буквы.
- на длинном тексте, состоящим из одной повторяющейся буквы
- на тексте, состоящем из большого количества одинаковых 10 буквенных слов
- на тексте "Тихий дон"
- Убедившись в его неработоспособности (время препроцессинга в некоторых случаях растёт квадратично — объясните почему) приступить к оптимизации
- Написать объектно-ориентированный причёсанный код библиотеки для индксирования текстов.
- В качестве серьёзной задачи для второго задания можно выбрать задачу написания полноценной библиотеки с
- документацией
- многоплановым и автоматизированным тестированием
- и хорошими показателями эффективности алгоритмов
- Можно ли "Суффиксный массив" как-то использовать для ускорения полнотекстового поиска по текстовому полю таблицы в базе данных? Почему "Суффиксный массив" не используется для построения индексов в базах данных?
- Рассказать, как устроено "Суффиксное дерево" и обсудить детали реализации. Возможно, даже написать черновой вариант.
Семинар 6. Задача “Стабильный коллектив” (EJ-106).
http://acm.mipt.ru/twiki/bin/view/Algorithms/HarmoniousGroup
Семинар 7. Задачи о выборе заявок: максимизация числа заявок, минимизация числа аудиторий.
Семинар 8. Кодирование Хаффмана и арифметическое кодирование.
Семинар 9. Наибольшая возрастающая подпоследовательность и дуальная к ней задача о разбиении последовательности на минимальное число убывающих (EJ-118).
Семинар 10. Поиск максимальной общей подпоследовательности двух строк (EJ-042).
Семинар 11. Задача “Minimal Range Query” (EJ-105). Связь с задачей “LCA” (EJ-123).
Семинар 12. Топологическая сортировка вершин графа. Сильно связные компоненты.
Семинар 13. Построение остовного дерева. Структура для непересекающихся множеств. Техника сжатия путей.
Семинар 14,15. Поиск кратчайшего пути в графе. Поиск кратчайших путей для всех пар вершин графа.
Семинар 16. Нахождение максимального потока в сети.
Рекомендации к проведению практических занятий
Цель курса – освоение ряда методов, которые позволяют решать алгоритмические задачи, знакомство с идеями и терминами, которые являются инструментарием при разработке технологических и программных решений. Современные задачи в информатике – это в основном сложные задачи – NP-сложные, слабо формализованные, многопараметрические, подразумевающее параллельное использование большого количества сложной техники и обработку большого количества данных. И в конечном итоге необходимо выработать навыки преодоления различных типов сложности. Сознавая эту глобальную цель, на практике при решении отдельной задачи необходимо преследовать более осязаемые цели, как то:
- Чёткое понимание поставленной задачи и контекста, в котором она возникает.
- Разбор множества вариантов решения задачи. Разумный выбор одного из них и реализация.
- Проведение прототипирования и тестирования.
- Анализ результата.
- Анализ идей, которые, привели к решению задачи.
Не надо забывать и про цель-минимум – это хорошее владение по крайней мере одним языком программирования и знакомство с классическими примерами модуляризации программного кода. К сожалению, изучение языка программирования требует много времени и индивидуального подхода. Рекомендуется на занятиях больше времени уделять чтению готового чужого исходного кода – эталонных примеров модульного кода, реализующего, например, алгоритмы на графах.
Задания же должны в значительной степени звучать так “На основе данных программных компонент, создать новую компоненту, которая реализует …”. Преподаватель должен предоставить столько подсказок и вспомогательных готовых функций, чтобы к концу каждого семинара (или каждого второго семинара) можно было увидеть работающий код и провести совместный его анализ. Это не значит, что студенты не должны самостоятельно думать. Но мне кажется в наших условиях для самостоятельного решения эффективнее давать теоретические задачи или задачи на понимание и только когда понимание достигнуто, переходить к кодированию на довольно сложном языке C++.
Да, рекомендуется в первую очередь
использовать язык C++, в качестве дополнительных опциональных языков могут выступать Ruby или Python.
При проведении совместных практических занятий полезно распараллеливать задания – например, одним студентам поручить задачу написания программы, которая генерирует тесты, а другим – математический анализ алгоритма и поиск более эффективных решений (в виде псевдокода).
Взаимодействие и обмен результатами исследования и программирования является важнейшим аспектом в современной IT-индустрии. Поэтому при приёме задания следует учитывать умение правильно оформлять результаты своей работы и осуществлять продуктивное сотрудничество во время семинара при решении задач.
FIVT-semestr3.doc