Хорошие задачи для подготовки по курсу Алгоритмы и структуры данных

Программирование Технология и методы программирования Алгоритмы и структуры данных Хорошие задачи для подготовки по курсу Алгоритмы и структуры данных

Помечено: 

В этой теме 0 ответов, 1 участник, последнее обновление  Васильев Владимир Сергеевич 6 мес. назад.

  • Автор
    Сообщения
  • #5402
    @admin

    Материал не мой. Автора найти не удалось. Тем не менее, крайне полезный. Собственно ниже приведен список очень хороших, на мой взгляд, задач по алгоритмам и структурам данных, а также требования какого-то (видимо очень крутого) ВУЗа к их оформлению.

    Зачем это тут?
    — С одной стороны это может быть интересно адекватным студентам, мечтающим стать хорошими программистами, а не быдлом. Задачи такого типа дают на собеседованиях, в приличных конторах. Потому что если вы хотя бы предложите подход к их решению — можно с уверенностью сказать, что вы читали какие-то полезные книжки, а не кололись.

    — С другой — преподавателям. Не только чтобы в конец охренеть от того, что в этой стране еще где-то пытаются учить нормально, но и чтобы что-то утащить в свои курсы.

    Если вдруг тут найдутся желающие решать эти задачи — буду рад помочь в рамках форума.

    Дальше материал какого-то хорошего преподавателя и человека:

    Общие условия

    Программа должна быть реализована на одном из языков: C/C++, Python, Kotlin, Java, Haskell, Scala. Прочие — по договоренности с преподавателем. Программа должна быть платформонезависимой, не иметь зависимостей от нестандартных библиотек и выполнена в виде консольного приложения.

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

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

    Программа должна быть покрыта тестами. Тесты должны содержать проверку корректности всех основных реализованных алгоритмов. Каждый тест представляет собой два текстовых файла с одинаковым именем, но разным расширением (например, 001.dat и 001.ans) в формате входных и выходных данных соответственно. Приветствуется предоставление отчета о покрытии разработанной программы тестами.

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

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

    Домашнее задание, включающее исходный код программы, тесты и отчет, должно быть отправлено на e-mail преподавателя до 12 декабря. После проверки преподавателем домашнее задание подлежит защите, после которой выставляется итоговая оценка.

    Студент может размещать результаты работы в публично доступном репозитории с веб-интерфейсом (например, GitHub). В таком случае допускается оформление отчета в виде одного или нескольких файлов формата Markdown, а на почту преподавателю можно присылать только ссылку на репозиторий.

    Если студента не устраивают предложенные варианты, то не позднее, чем до 1 октября, он может предложить свой вариант домашнего задания, позволяющий, на его взгляд, продемонстрировать его навыки использования алгоритмов и структур данных (в том числе на основе предлагаемых задач).

    Структуры данных

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

    Входной файл содержит последовательность команд, т. е. представляет набор строк вида

    command [key] [data]

    , где command — add, delete, search, min, max, print или спец. команда;
    key — ключ, целое число;
    data — данные, целое число.

    Примеры:

    add 10 20
    search 15
    print
    min

    Команда print должна отражать внутреннее строение структуры данных, а ее формат вывода должен быть описан в отчете.

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

    Тесты для каждой из структур предоставляются отдельно.

    В практической части для всех сценариев должна быть предоставлена информация о скорости работы сравниваемых структур данных и сделаны выводы о результатах сравнения.
    1. Сравнить список с пропусками и АВЛ-дерево.
    2. Сравнить структуру данных Rope (веревка) и обычную строку.
    3. Сравнить хэш-таблицу, отсортированный массив и любое из самобалансирующихся деревьев поиска.
    4. Сравнить LSM-дерево и любое из самобалансирующихся деревьев поиска.
    5. Сравнить vEB-дерево и любое из самобалансирующихся деревьев поиска.

    Алгоритмы

    Формат входного(ых) файла студент выбирает самостоятельно. Выходной файл содержит результат работы алгоритма. Реализация алгоритма должна быть инкапсулирована. В отчете необходимо описать используемые структуры данных и обосновать их выбор.

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

    Если студент доказывает, что его задача является NP-полной (или NP- трудной), то допускается использование приближенных и/или эвристических алгоритмов для ее решения. При этом необходимо предоставить оценку точности решения.

    6. Построить абстрактное синтаксическое дерево программы. Вход — исходный код программы на выбранном студентом языке общего назначения.
    7. Написать программу для решения судоку произвольного размера.
    8. Некое заведение общепита очень любит акции. Акции заключаются либо в назначении сниженной цены за комбинацию продуктов, либо в предоставлении бесплатного продукта при покупке определенной комбинации продуктов. Напишите алгоритмы для определения набора акций такого, чтобы:
    a. купить желаемый набор продуктов максимально выгодно.
    b. максимально сытно поесть на фиксированную сумму.

    Вход — меню (с ценами и калорийностью), акции, набор продуктов или сумма. Подсказка: Задача a может быть решена с помощью алгоритма для решения задачи b.

    9. Пусть есть некоторое закольцованное игровое поле и набор правил для перемещения по нему (перемещение на несколько клеток вперед или назад, перемещение на клетку с определенным номером). Примеры правил: «переместиться на такую-то клетку», «отойти на три клетки назад». Начальное перемещение задается броском двух кубиков, при выпадении дубля можно ходить еще раз, но три дубля подряд завершают ход. Определите условия, при которых игрок пройдет максимальное количество клеток за один ход. В качестве примера можно взять игру «Монополия».

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

    11.Реализуйте алгоритм, который по входному недерминированному конечному автомату строит детерминированный и эмулирует его.

    12.Сравните производительность алгоритмов разбиения графов на компоненты связности, основанные на различных алгоритмах поиска (например, BFS), и алгоритма использующего систему непересекающихся множеств (DSU).

    13.Напишите программу, эмулирующую простой процессор (можно взять за основу, например, MSP430).

    14.У преподавателя есть список заданий, каждое из который имеет тип (теория/практика/блиц/прочие), тематику и уровень сложности. Постройте алгоритм для генерации списка билетов, такой, чтобы одновременно выполнялись условия:
    1) в зависимости от внешних условий состав билетов меняется;
    2) билет содержит одинаковое количество вопросов из разных тем, и одинаковое соотношение заданий разных типов (например, 2 теории и одна практика);
    3) уровень сложности всех билетов приблизительно одинаковый.

    15.Преподавателю надо печатать билеты и при этом потратить как можно меньше бумаги. Упорядочите билеты так, чтобы они занимали наименьшее число листов A4, между ними было место для разреза, у листа были поля сверху и снизу и ни один билет не оказался «разорван» между листами.

    16.Постройте программу для решения головоломки «Пятнашки» произвольного размера.

    17.Напишите программу для получения минимальной ДНФ булевой функции.

    18.Реальные схемотехнические элементы имеют задержку при переключении состояния, и с повышением частоты это довольно серьезная проблема. Напишите алгоритм, который принимает на вход схему из булевых элементов и времена задержек и обнаруживает потенциальные сбои.

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

    20.Постройте алгоритм для игры в шашки, который предлагает лучший ход для позиции, переданной во входных данных.

    21.Реализуйте алгоритм для игры в «Наборщика» (составить все возможные слова из входного слова).

    22.Реализуйте алгоритм проверки орфографии с помощью BK-дерева.

    23.Напишите алгоритм для вывода всех неприводимых многочленов в заданном конечном поле.

    24.Реализуйте алгоритм для поиска похожих изображений.

    25.Напишите алгоритм, который принимает на вход набор целых неотрицательных чисел и переупорядочивает их так, чтобы сумма любых двух соседних чисел была полным квадратом (или выводит ответ, что это невозможно).

    26.Реализуйте алгоритм для игры в «быки и коровы».

    Приложение

    Список абстракций, задач, методов, алгоритмов и структур данных, которые могут пригодиться при выполнении домашнего задания.
    • Алгоритм A*
    • Алгоритм Дейсктры
    • Алгоритм LZW
    • Алгоритм Барроуза-Уилера
    • Задача об упаковке в контейнеры (и ее вариант offline-2DSP)
    • Задача о покрытии множества
    • Диаграммы Вороного
    • Метод ветвей и границ
    • Задача о рюкзаке
    • Задача коммивояжёра
    • Интервальное дерево
    • Задача ЦЛП
    • Алгоритм Прима
    • Алгоритм Крускала
    • Задача Штейнера
    • BSP-дерево
    • Конечный автомат
    • Генетические алгоритмы
    • Латинский квадрат
    • Полимино
    • Граф Кэли
    • Система непересекающихся множеств

Для ответа в этой теме необходимо авторизоваться.