Задачи семинарских занятий. 2005 год, ВМиК МГУ, группы 209 и 210

Задачи исследование, поиск информации, создание тестов

Среда разработки и работы программ- операционная система семейства Unix / Linux / Free BSD? etc, так как эти задачи расчитаны на работу с этой операционной системой

Обход дерева

Сортировка больших объемов данных

1. Генерация файла из 100 000 чисел типа int.
2. Сортировка этого массива с ограничением по памяти – одновременно в оперативную память должно быть загружено не более 1000 чисел. Требуется реализовать и использовать алгоритм быстрой сортировки (или сортировку Хоара) для каждых 1000 чисел, затем применить сортировку слиянием для слияния этих отсортированных массивов в один файл.
3. Реализовать ту же задачу, но ограничение в 1000 чисел в памяти накладывается не на программу целиком, а на каждый из процессов программы. Создадим, помимо главного процесса, 10 дочерних процессов сортировки и в каждом из них будет один входной поток(pipe) для получения новых чисел и один выходной – для возвращения в главный процесс отсортированных данных. Главный процесс, после создания дочерних, начинает считывать числа из файла, пересылая каждое считанное в один из дочерних процессов. Дочерние процессы действуют методом вставки. Когда главный процесс закрывает поток(pipe) передачи новых чисел, дочерний процесс, уже владея отсортированным массивом, передает его на выходной поток, главный процесс получает из каждого из дочерних отсортированные массивы и в процессе получения сортирует их слиянием, сразу записывая в файл.

Простейшая БД

1. Генерация действительно-большого-текстового-файла. Программе на вход в качестве параметра командной строки задается директория на диске, где лежит несколько файлов формата txt (скачать десяток больших книг с lib.ru, например). Программа выдает на stdout текстовый файл из склеенных в произвольной последовательности текстов в этой директории (то есть склеиваем несколько файлов в один).
2. Задача – написать программу, которая будет быстро отвечать на следующие вопросы
   • по введенному слову – сколько раз оно встретилось.
   • по начальной части слова и числу n выдать n самых частовстречаемых слов начинающихся на введенную последовательность (не менее одного символа в последовательности)

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

   • Пройдя весь текстовый файл от начала до конца создаем для каждой возможной начальной буквы слова массив соответствия <слово>-<сколько раз встретилось>. Реализуется, например, двумя массивами – массивом строк S и массивом чисел N и для слова S[i] храним в N[i] его встречаемость. Таким образом, в процессе чтения динамически формируются два двумерных массива. Отдельный массив будет отражать сопоставление символа- номеру массивов. К примеру, нам встретилось слово «арбуз». Ищем в массиве index номер элемента “a”, если такого нет- то добавляем его в конец массива. Если номер существовал и равен j, то в массиве indexS[j][] ищем слово «арбуз», если найдено под номером k,то увеличиваем значение indexN[j][k], иначе добавляем в indexS[j] элемент «арбуз» в конец, в конец же indexN[j] добавляем единицу.
   • Далее – сортируем каждую пару массивов по алфавитному порядку слов в S (сортируем S, одновременно меняя местами и элементы N, чтобы статистика не терялась). Заносим для каждого i массивы indexS[i][] и indexN[i][] в файлик <число>.dat – где число в названии файла – есть char-код первого символа в слове. Формат файла – информация о каждом новом слове – с новой строки, разделитель между словом и числом – табуляция.
   • поиск данных по введенному слову происходит следующим образом – смотрим на первую букву этого слова, открываем соответствующий ей файл базы данных, просматривая ее от начала до конца ищем строку с данным числом. Пользуемся тем, что слова в файлах отсортированы, поэтому если начались слова «большие» искомого, то прекращаем поиск и говорим, что данное слово не встречалось в тексте. Если нашли – выдаем статистику.
   • поиск частых слов начинающихся на заданную последовательность символов. Аналогично предыдущему пункту, берем нужный файл, пользуясь отсортированностью не требуется просмотреть файл до конца, так как нужные слова всегда будут стоять рядом. Выбираем их из базы, сортируем по частоте встречаемости и выдаем.

Полнотекстовый поиск без индексации

1. Генерация действительно-большого-текстового-файла. Программе на вход в качестве параметра командной строки задается директория на диске, где лежит несколько файлов формата txt (скачать десяток больших книг с lib.ru, например). Программа выдает на stdout текстовый файл из склеенных в произвольной последовательности текстов в этой директории (то есть склеиваем несколько файлов в один).
2. Написать программу, которой в stdin передается некий большой текстовый файл, в качестве парамера командной строки – некая строка, состоящая из любых символов, ограниченная кавычками (внутри текста и в поисковой строке кавычек нет). В результате программа выдает для первых десяти вхождений данной поисковой строки информацию -номер строки во входном файле, цитата из этого места файла – кусок текста файла начиная за пять слов до вхождения и заканчивая пяти строками после.
3. Используемые алгоритмы поиска – сначала реализовать простейший – алгоритм поискового окна. Если ищется совпадение длиною m, то берем каждый раз следующие m символов текста и сравниваем с поисковым образцом. Далее усовершенствуем (ускорим) используя алгоритм Рабина. Посчитаем сумму кодов символов в поисковом образце. Перед тем, как сравнивать очередные m символов из текста – посчитаем сумму их кодов и начнем сравнивать символы только тогда, когда эти суммы совпадают. Заметим, что при «сдвиге» окна на один символ нет надобности пересчитывать сумму полностью, достаточно вычесть из него код «ушедшего» символа и прибавить код нового символа окна.
4. Обратите внимание, что в тексте могут быть переносы строк, в поисковом образце они заменяются на пробелы. И при выдаче цитаты также требуется переносы строк заменять на пробелы.
5. Сделать выбор алгоритма- простой или Рабина – входным параметром алгоритма, сделать подсчет времени, занятого поиском. С этой помощью сравнить – дает ли прирост производительности алгоритм Рабина, если да, то какой.

Полнотекстовый поиск с индексацией

1. Найти десяток крупных текстовых файлов, например получить их на lib.ru и положить в одну директорию
2. Требуется написать программу, которая по введенному слову выдаст первые 5 употреблений этого слова в каждом из файлов (если есть), причем приведет цитаты из этих файлов, с участием этого слова(5 слов до него+слово+5 слов после него) и выдаст номер строки,где это слово встречается.
3. Сначала соберем в оперативной памяти массив поиска.

Поиск в двоичных деревьях

Задачи на графы

Упорядоченные деревья