Список заданий

Задания, баллы за которые помечены плюсами («+1 балл» и т.д.), являются дополнительными и их можно сдавать до конца семестра. Все остальное — обязательная программа.

[0] Хэш-таблицы. В первой строке входного файла input.txt записано число N, 1≤N≤1000000. В следующих N строках записаны слова длиной до 5 символов, по одному слову в строке, без пробелов. Количество различных слов не превышает 5000, количество вхождений каждого слова не превышает 60000. Подсчитать количество вхождений каждого слова, вывести результат в файл output.txt.
- 3 балла: определена хэш-функция, реализована хэш-таблица (добавление элементов и разрешение коллизий).
- +1 балл: вывод списка слов, отсортированного по количеству вхождений.
- +1 балл: вывод списка слов, отсортированного по алфавиту.
[1] Построение упорядоченных односвязных списков. В первой строке входного файла input.txt записано число N, 1≤N≤1000. В следующих N строках записаны числа (тип int). Вывести эти числа в отсортированном порядке, используя динамический список.
- 2 балла: чтение чисел из файла, запись в список, вывод в отсортированном порядке. Очистка памяти перед завершением работы обязательна.
- +1 балл: работа с двусвязным списком.
- +1 балл: если прочитано число, которое уже есть в списке, оно удаляется из списка. Т.е. выводятся числа, встретившиеся нечетное количество раз;
- +1 балл: реализация базовой функциональности на паскале.
[2] Вычисления на стеке. Перевод выражения из инфиксной формы в обратную польскую запись.
- 3 балла: перевод арифметического выражения в обратную польскую запись, вычисление.
- +2 балла: интерпретация BASIC'оподобного кода из операторов присваивания и операторов PRINT.
[3] Словарь. Реализация деревьев двоичного поиска.
- 4 балла: базовая функциональность (добавление слов и поиск)
- +4 балла: балансировка дерева
[4] Топологическая сортировка.
1. 2 балла: реализация с помощью матрицы смежности;
2. 3 балла: реализация на иерархических списках;
3. +2 балла: вывод всех возможных вариантов.
[5] Основные алгоритмы на графах — 1.
1. 2 балла: Транзитивное замыкание;
2. 2 балла: Алгоритм Флойда;
3. 3 балла: Алгоритм Дейкстры;
4. +2 балла: вывод кратчайшего пути в алгоритме Дейкстры.
[6] Построение минимального каркаса графа.
1. 3 балла: Реализация алгоритма Краскала;
2. 3 балла: Реализация алгоритма Прима.
[7] Основные алгоритмы на графах — 2.
1. 3 балла: Метод поиска в глубину;
2. 3 балла: Нахождение двусвязных компонент и точек сочленения в графе.
[8] Поиск кратчайшего пути в лабиринте.
1. 3 балла: Поиск в ширину (метод волны).
[9] Индивидуальное задание. 4 балла.

Список дополнительных заданий

Задания, сдача которых не является обязательной, но приветствуется и будет поощряться (+3 балла за каждое задание).

Список заданий

Список лабораторных работ

Список дополнительных заданий