Раздел «Образование».FIVTThirdTerm2008:

Программа 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);

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

  int n = strlen(text);
  char ** suffix_array = (char**)malloc(n);
  char *p; char **a = suffix_array;
  for(p = text; *p; p++, a++ ) *a = p;
   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);

Семинар 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-сложные, слабо формализованные, многопараметрические, подразумевающее параллельное использование большого количества сложной техники и обработку большого количества данных. И в конечном итоге необходимо выработать навыки преодоления различных типов сложности. Сознавая эту глобальную цель, на практике при решении отдельной задачи необходимо преследовать более осязаемые цели, как то:

  1. Чёткое понимание поставленной задачи и контекста, в котором она возникает.
  2. Разбор множества вариантов решения задачи. Разумный выбор одного из них и реализация.
  3. Проведение прототипирования и тестирования.
  4. Анализ результата.
  5. Анализ идей, которые, привели к решению задачи.

Не надо забывать и про цель-минимум – это хорошее владение по крайней мере одним языком программирования и знакомство с классическими примерами модуляризации программного кода. К сожалению, изучение языка программирования требует много времени и индивидуального подхода. Рекомендуется на занятиях больше времени уделять чтению готового чужого исходного кода – эталонных примеров модульного кода, реализующего, например, алгоритмы на графах. Задания же должны в значительной степени звучать так “На основе данных программных компонент, создать новую компоненту, которая реализует …”. Преподаватель должен предоставить столько подсказок и вспомогательных готовых функций, чтобы к концу каждого семинара (или каждого второго семинара) можно было увидеть работающий код и провести совместный его анализ. Это не значит, что студенты не должны самостоятельно думать. Но мне кажется в наших условиях для самостоятельного решения эффективнее давать теоретические задачи или задачи на понимание и только когда понимание достигнуто, переходить к кодированию на довольно сложном языке C++.

Да, рекомендуется в первую очередь использовать язык C++, в качестве дополнительных опциональных языков могут выступать Ruby или Python.

При проведении совместных практических занятий полезно распараллеливать задания – например, одним студентам поручить задачу написания программы, которая генерирует тесты, а другим – математический анализ алгоритма и поиск более эффективных решений (в виде псевдокода).

Взаимодействие и обмен результатами исследования и программирования является важнейшим аспектом в современной IT-индустрии. Поэтому при приёме задания следует учитывать умение правильно оформлять результаты своей работы и осуществлять продуктивное сотрудничество во время семинара при решении задач.

Attachment sort Action Size Date Who Comment
FIVT-semestr3.doc manage 88.0 K 30 Aug 2008 - 16:45 ArtemVoroztsov Программа
FIVT-test.doc manage 28.5 K 14 May 2009 - 08:25 ArtemVoroztsov Контрольная работа. 3-й семестр