Перечень тем курсовых работ по предмету

Перечень тем курсовых работ по предмету

«Теория алгоритмов и математические основы представления знаний»

На 2015-2016 уч. год

На баллы от 4 до 6

Вариант 1.

Тема: «Исследование алгоритма для нахождения простых чисел».

Задание: Реализовать алгоритм решета Эратосфена для нахождения простых чисел в массиве из N элементов. С помощью разработанной программы определить количество простых чисел, меньших N, для N = 1 000, 10 000, 100 000, 1 000 000. Построить график зависимости N от количества простых чисел, меньших N, для значений N от 1 до 1000.

Вариант 2.

Тема: «Исследование алгоритма решения задачи Иосифа».

Задание: Реализовать алгоритм решения задачи Иосифа (Флавия). С помощью разработанной программы определить значение функции Иосифа для М = 2, 3, 5, 10 и N = 1 000, 10 000, 100 000, 1 000 000. Построить график зависимости функции Иосифа от N для М = 10 и N от 2 до 1000.

Вариант 3.

Тема: «Исследование алгоритма Эвклида».

Задание: Реализовать алгоритм Эвклида для отыскания наибольшего общего делителя для двух целых чисел. Сравнить рекурсивную и нерекурсивную реализацию. Привести рисунок для результата выполнения алгоритма Эвклида применительно к числам 89 и 55. Указать глубину рекурсии алгоритма Эвклида при вводе двух последовательных чисел Фибоначчи.

Вариант 4.

Тема: «Исследование рекурсивного алгоритма нахождения максимального значения методом «разделяй и властвуй».

Задание: Реализовать рекурсивный алгоритм нахождения максимального элемента в массиве с помощью алгоритма «разделяй и властвуй». Нарисовать дерево, которое соответствует рекурсивным вызовам, выполняемым программой при размере массива, равном 11. Как будет изменяться количество операций сравнения для упорядоченных и неупорядоченных исходных массивов? Привести примеры.

Вариант 5.

Тема: «Исследование алгоритма нахождения минимального значения методом «разделяй и властвуй».

Задание: Реализовать алгоритм «разделяй и властвуй» для поиска минимального элемента в массиве. Алгоритм должен делить массив на k частей, размер которых различается не более чем на 1, рекурсивно находить минимум в каждой части и возвращать минимальный из минимумов. Нарисовать 3-арные и 4-арные деревья, соответствующие использованию k = 3 и k = 4 в рекурсивной конструкции для массива, состоящего из 11 элементов.

Вариант 6.

Тема: «Исследование элементарных алгоритмов сортировки (выбором и вставками)».

Задание: Реализовать два элементарных алгоритма сортировки: выбором и вставками. Сравнить реализации для массивов разных размеров: 100, 1 000, 10 000, 100 000, 1 000 000. Показать, как будет отсортирован файл E A S Y Q U E S T I O N алгоритмом вставок и алгоритмом выбором. На какой итерации попадет в свою позицию максимальный элемент массива? минимальный элемент массива? (в каждом из алгоритмов). Какой из алгоритмов выполняется быстрее при обработке массивов, элементы которого снабжены идентичными ключами? элементы которого упорядочены в обратном порядке?

Вариант 7.

Тема: «Исследование алгоритма пузырьковой сортировки».

Задание: Реализовать алгоритм пузырьковой сортировки. Показать как будет отсортирован файл E A S Y Q U E S T I O Nданным методом. Дать пример файла, для которого пузырьковая сортировка выполняет максимально возможное количество перестановок элементов местами. Определить, сколько проходов файла с произвольной организацией из N элементов экономится в результате добавления в пузырьковую сортировку возможностей прекращения сортировки по результатам проверки: отсортирован файл или нет.

Вариант 8.

Тема: «Исследование алгоритма быстрой сортировки».

Задание: Реализовать алгоритм быстрой сортировки. Показать как быстрая сортировка сортирует файл E A S Y Q U E S T I O N. Каким является максимальное число перемещений наибольшего элемента файла, состоящего из N элементов, во время выполнения быстрой сортировки. Сколько примерно операций выполнит быстрая сортировка для упорядочения файла из N равных элементов? Построить 6 файлов из 10 элементов, при упорядочении которых метод быстрой сортировки выполняет то же количество операций сравнения, что и в самом худшем случае (когда все элементы файла упорядочены).

Вариант 9.

Тема: «Исследование алгоритма сортировки методом двухпутевого слияния».

Задание: Реализовать алгоритм сортировки методом двухпутевого слияния. Верно ли утверждение, что данная сортировка работает правильно лишь когда оба входных подмассива уже отсортированы? Доказать правильность выводов или предоставить контрпример. Пусть дан упорядоченный файл размером N, который нужно объединить с неупорядоченным файлом размером М. При этом М намного меньше N. Что будет быстрее и насколько: упорядочить исходный файл М и потом начать слияние или же слить содержимое М в N и сделать сортировку полученного файла?

Вариант 10.

Тема: «Исследования алгоритма поиска с использованием индексации по ключам».

Задание: Реализовать таблицу символов, основывающуюся на индексированном по ключам массиве. Создайте функцию h(Key), которая будет преобразовывать ключи в неотрицательные целые числа меньшие М так, чтобы никакие два ключа не отображались одним и тем же целым числом. Покажите на примере ключей -322 764 382 -638 135 -387 -965 -872 468 980как они будут преобразованы в неотрицательные целые числа.

Вариант 11.

Тема: «Исследование алгоритма последовательного поиска».

Задание: Реализовать упорядоченную таблицу символов с использованием массива. Указать количество операций сравнения, необходимое для помещения ключей E A S Y Q U E S T I O Nв первоначально пустую таблицу символов. При этом учесть, что для каждого ключа выполняется поиск, а затем, в случае его отсутствия в таблице, выполняется вставка.

Вариант 12.

Тема: «Исследование алгоритма бинарного поиска».

Задание: Реализовать бинарный поиск в таблице символов, основанной на массиве. Нарисовать деревья для N = 17 и N = 24. Как изменится количество операций сравнения при бинарном поиске, если таблица символов будет содержать одинаковые значения ключей? 2 варианта значений ключей?

Перечень тем курсовых работ по предмету

«Теория алгоритмов и математические основы представления знаний»

На 2015-2016 уч. год

На баллы от 7 до 9

Вариант 13.

Тема: «Исследование алгоритмов восходящей и нисходящей сортировок слиянием».

Задание: Реализовать алгоритмы восходящей и нисходящей сортировок слиянием. Какая из них будет работать эффективнее? Показать, какие слияния выполняет каждая из рассматриваемых сортировок на ключах E A S Y Q U E S T I O N. Как изменится производительность данного алгоритма, если на вход поступит отсортированный массив, а не произвольно организованный? Нарисовать деревья, которые отображают слияния, выполняемые нисходящей сортировкой слияния для N = 16, 24, 31, 32, 33, 39.

Вариант 14.

Тема: «Исследование алгоритма восходящей сортировки слиянием».

Задание: Реализовать алгоритм восходящей сортировки слиянием. Показать, какие слияния выполняет рассматриваемая сортировка на ключах K E Y O P E R A T I O N. Реализовать восходящую сортировку слиянием, которая начинает с того, что сортирует блоки по М элементов каждый методом вставок. Определить эмпирическим путем значение М, для которого разработанная программа выполняется быстрее всего при сортировке файлов с произвольной организацией, содержащих N элементов при N = 1 000, 10 000, 100 000, 1 000 000. Нарисовать деревья, которые отображают слияния, выполняемые восходящей сортировкой слияния для N = 16, 24, 31, 32, 33, 39.

Вариант 15.

Тема: «Исследование алгоритма пирамидальной сортировки».

Задание: Реализовать алгоритм пирамидальной сортировки. Построить сортирующее дерево, которое получится после того как ключи E A S Y Q U E S T I O Nвставлены в первоначально пустое сортирующее дерево. Проверить, является ли полученное дерево пирамидально упорядоченным: если нет – упорядочить. Для N = 32 найти такое расположение ключей, которое требуетвыполнения минимального и максимального числа операций сравнения в рамках пирамидальной сортировки.

Вариант 16.

Тема: «Исследование алгоритма поразрядной сортировки MSD».

Задание: Реализовать алгоритм поразрядной сортировки MSD. Показать, как будет отсортирован файл 3722 8764 6382 6438 1635 3687 3965 1872 4768 9860 с помощью данного алгоритма. Сгенерировать произвольные ключи, после чего отсортировать их методом поразрядной сортировки MSD для N = 1 000, 10 000, 100 000, 1 000 000. Какое общее количество байтов проверяется в процессе каждой сортировки?

Вариант 17.

Тема: «Исследование алгоритма обменной сортировки».

Задание: Реализовать алгоритм обменной сортировки. Показать, как будет отсортирован файл E A S Y Q U E S T I O Nданным методом. Описать перестановку размера N (набор значений для массива а), в которой условие a[i] != i в процессе работы программы выполняется максимальное число раз. Доказать, что в процессе перемещения ключей и появления в программе пустых мест, обязательно произойдет возврат к ключу, с которого начинали.

Вариант 18.

Тема: «Исследование алгоритма сортировки методом распределенного подсчета».

Задание: Реализовать алгоритм сортировки методом распределенного подсчета. Показать, как файл E A S Y Q U E S T I O Nбудет отсортирован данным методом. Продемонстрировать, как будет работать сортировка распределенным подсчетом с элементами, которые представляют собой потенциально большие записи с целочисленными ключами, принимающие значения в небольшом диапазоне?

Вариант 19.

Тема: «Исследование алгоритма сортировки методом разделения с вычислением медианы из трех элементов».

Задание: Реализовать алгоритм сортировки методом разделения с вычислением медианы из трех элементов (улучшенная быстрая сортировка). Выполнить программу на крупных файлах со специальной организацией – отсортированные файлы; файлы, упорядоченные в обратном порядке; файлы с одинаковыми ключами элементов. Насколько ее эффективность при сортировке указанных файлов отличается от эффективности, полученной для файлов с произвольной организацией?

Вариант 20.

Тема: «Исследование алгоритма быстрой сортировки с разделением на три части».

Задание: Реализовать алгоритм быстрой сортировки с разделением на три части. Добавить в программу условие: если все ключи в подфайле одинаковы, то выполнить процедуру return. Сравнить эффективность исходной программы с программой с добавленным условием на больших файлах с произвольной организацией; на файлах с ключами, принимающими t различных значений при t = 2, 5, 10.

Вариант 21.

Тема: «Исследование алгоритма двоичной быстрой сортировки».

Задание: Реализовать алгоритм двоичной быстрой сортировки. Показать, как будет отсортирован файл E A S Y Q U E S T I O Nс помощью данного алгоритма. Построить дерево разделения для данного файла.

Вариант 22.

Тема: «Исследование алгоритма трехпутевой поразрядной быстрой сортировки».

Задание: реализовать алгоритм трехпутевой поразрядной быстрой сортировки. Сгенерировать произвольные ключи, после чего отсортировать их методом предложенной сортировки для N = 1 000, 10 000, 100 000, 1 000 000. Эмпирически определить размер байта, для которого время выполнения трехпутевой сортировки 64-разрядных ключей минимально, при N = 1 000, 10 000, 100 000, 1 000 000.

Вариант 23.

Тема: «Исследование алгоритма поразрядной сортировки LSD».

Задание: Реализовать алгоритм поразрядной сортировки LSD. Показать результат использования данной сортировки для упорядочения по двум первым сисмволам совокупности ключей now is the time for all good people to come the aid of their party. Сгенерировать произвольные ключи, после чего отсортировать их методом поразрядной сортировки LSD для N = 1 000, 10 000, 100 000, 1 000 000. Какое общее количество байтов проверяется в процессе каждой сортировки?

Вариант 24.

Тема: «Исследование алгоритма хеширования с использованием раздельного связывания».

Задание: Реализовать алгоритм хеширования с использованием метода раздельного связывания. Каким будет содержимое хеш-таблицы, обрахованной при вставке элементов с ключами E A S Y Q U E S T I O Nв первоначально пустую таблицу, состоящую из N = 5 списков при использовании раздельного связывания с неупорядоченными списками. Для преобразования k-той буквы алфавита в индекс таблицы использовать хеш-функцию: 11k mod M.

Вариант 25.

Тема: «Исследование алгоритма хеширования с использованием линейного зондирования».

Задание: Реализовать алгоритм хеширования с использованием метода линейного зондирования. Каким будет содержимое хеш-таблицы, обрахованной при вставке элементов с ключами E A S Y Q U E S T I O Nв первоначально пустую таблицу размером М = 16 при использовании линейного зондирования. Для преобразования k-той буквы алфавита в индекс таблицы использовать хеш-функцию: 11k mod M.

Вариант 26.

Тема: «Исследование алгоритмов на базе дерева бинарного поиска».

Задание: Реализовать таблицу символов на базе дерева бинарного поиска с функциями поиска, вставки, сортировки. Нарисовать BST-дерево, образующееся при вставке элементов с ключами E A S Y Q U E S T I O Nв первоначально пустое дерево. Привести пример с максимальным количеством сравнений, требуемых для любого поиска в BST-дереве из 10 элементов. Определить среднее количество попаданий м промахов при поиске в BST-дереве, созданном в результате вставки N произвольных ключей в первоначально пустое дерево, для N = 1 000, 10 000, 100 000, 1 000 000.