Математика \ Дискретная математика для программистов

Список тем курсовых работ по дисциплине "Дискретная математика" (Двумерные целочисленные множества. Статистические параметры 2-D потока модельных частиц), страница 2

Постановка задачи

1

Тема: Двумерные целочисленные множества.

Исходные данные.

Задан файл записей, содержащих два поля. В каждом поле-целое число в пределах от -100 до 100.

Требуется:

Составить программу для решения задач: а) каково общее число несовпадающих записей? б) какие из записей имеют наибольшую частоту и какие встречаются наиболее редко? И т.п.

Рекомендуемая литература

[1], [2], [18]

2

Тема: Многомерные целочисленные множества.

Исходные данные.

Заданы несколько файлов записей, содержащих n полей. В каждом поле - целое число в пределах от -100 до 100.

Требуется:

Составить программу для решения задач: а) нахождение объединения и пересечения множеств, представленных в файлах; б) каково общее число несовпадающих записей? в) какие из записей имеют наибольшую частоту и какие встречаются наиболее редко? И т.п.

Рекомендуемая литература

 [1], [2] , [18]

3

Тема: Многопутевое упорядочивание целочисленных массивов

Исходные данные.

Заданы несколько целочисленных массивов, упорядоченных по возрастанию

Требуется:

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

Рекомендуемая литература

 [1], [13] , [18]

4

Тема: Упорядочение многомерных множеств по указанным полям

Исходные данные.

Задано множество записей.

Требуется:

Составить программу для упорядочения исходного множества по указанному пользователем полю. Рассмотреть также иные виды запросов.

Рекомендуемая литература

 [1] , [18]

5

Тема: Реализация запросов при наличии файла записей

Исходные данные:

Имеется файл записей сложной структуры.

Требуется реализовать запросы. Например: а).составить список записей, имеющих одинаковое третье поле и упорядочить их по первому полю; б) найти количество записей, имеющих одинаковые второе или третье поля, для которых первое поле превышает некоторое значение; и т.д. Использовать индексные множества

Рекомендуемая литература

 [1] , [18]

6

Тема: Сортировка с использованием троичного дерева

Исходные данные: массив.

Требуется:

а) составить программу пирамидной сортировки с использованием двоичного дерева;

б) составить программу пирамидной сортировки с использованием троичного дерева;

в) для больших массивов сравнить оба метода по затраченному времени работы ЭВМ.

Рекомендуемая литература

 [1], [10], [11], [12], [13] , [18]

7

Тема: Кратчайший путь на графе.

Исходные данные:

Имеется n пунктов. Между некоторыми из них существует связь (дорога).

Требуется:

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

Рекомендуемая литература

 [1], [4], [5], [6], [8], [12], [13] , [18]

8

Тема: Кратчайший путь на ориентированном графе

Исходные данные:

Имеется n пунктов. Между некоторыми из них существует односторонняя связь.

Требуется:

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

Рекомендуемая литература

 [1], [4], [5], [6], [8], [12], [13] , [18]

9

Тема: Перевод из одной системы счисления в другую

Исходные данные: массив цифр от 0 до 4, представляющий число в пятеричной системе счисления.

Требуется найти представление того же числа в семеричной системе счисления.

Рассмотреть также произвольные основания.

Длины массивов для иллюстрации – не более шести; в окончательном варианте – порядка нескольких сотен.

Рекомендуемая литература

 [1] , [18]

10

Тема: Деление длинных чисел

Исходные данные: два длинных числа в некоторой системе счисления.

Требуется:

Найти наибольший общий множитель. Найти результат деления первого числа на второе и остаток от этого деления. Остаток , если возможно, сократить. Поделить второе на первое.

Рекомендуемая литература

 [1], [12], [13] , [18]

11

Тема: Разложение подстановки на циклы

Исходные данные: произвольная подстановка длины 100 – 1000.

Требуется :

Выписать циклы в отдельный файл. Найти наименьшую степень исходной подстановки, обращающую ее в единичную.

Рекомендуемая литература

 [1] , [18]

12

Тема: Представление выражений в виде польской записи.

Исходные данные: строка символов, представляющая арифметическое выражение.

Требуется: 1) Определить наличие синтаксических ошибок. 2) Представить выражение в виде польской записи и обратной польской записи. 3) Привести примеры вычисления выражений

Рекомендуемая литература

www, [18]

13

Тема: Двоичное равномерное кодирование – декодирование

Исходные данные: тестовый текст (не более страницы)

Требуется: 1) Закодировать с помощью стандартной таблицы кодов, занести в файл

2) Прочитать из файла, декодировать

Рекомендуемая литература

 [2], [8], [9] , [18]

14

Тема: Троичное равномерное кодирование-декодирование

Исходные данные: тестовый текст (не более страницы)

Требуется: 1) Перевести с помощью стандартной таблицы кодов символы текста из двоичного представления в троичные, занести в файл 2) Прочитать из файла, декодировать

Рекомендуемая литература

 [2], [8], [9] , [18]

15

Тема: Восстановление равномерной двоичной таблицы кодов по частотам

Исходные данные: Текст, закодированный двоичным равномерным кодом длины 8 (не менее одной страницы). Таблица кодов является некоторой подстановкой над стандартной таблицей двоичных кодов.

Требуется: 1) Составить таблицу частот по тексту большого объема; 2) Составить таблицу частот в предъявленном тексте;.3) Проделать несколько попыток по восстановлению исходной таблицы. 4) Дешифровать исходный текст.

Рекомендуемая литература

 [2], [8], [9] , [18]

16

Тема: Кодирование-декодирование по Хеммингу

Исходные данные. Текст, представленный стандартным двоичным кодом.

Требуется: 1) Перекодировать по Хеммингу исходный текст; 2) Для каждого закодированного символа заменить произвольно выбранный из 12 битов на противоположный; результат занести в файл; 3) Декодировать текст, занесенный в файл.

Рекомендуемая литература

 [2] , [18]

17

Тема: Кодирование – декодирование по Фано

Исходные данные: Текст большого объема; тестовый текст (не более одной страницы)

Требуется: 1) По большому тексту составить таблицу частот; 2) Составить таблицу кодов по Фано; определить минимальную теоретическую цену и цену для полученного кода;

3) Закодировать тестовый текст с помощью стандартного двоичного кода  и с помощью кода Фано; сравнить полученные длины кодов текста; занести в файл результат кодирования по Фано; 4) Декодировать текст из этого файла.

Рекомендуемая литература

 [2], [8] , [18]

18

Тема: Кодирование – декодирование по Хаффмену

Исходные данные: Текст большого объема; тестовый текст (не более одной страницы)

Требуется: 1) По большому тексту составить таблицу частот; 2) Составить таблицу кодов по Хаффмену; определить минимальную теоретическую цену и цену для полученного кода;

3) Закодировать тестовый текст с помощью стандартного двоичного кода  и с помощью кода Хаффмена; сравнить полученные длины кодов текста; занести в файл результат кодирования по Хаффмену; 4) Декодировать текст из этого файла.

Рекомендуемая литература

 [2], [8], [9] , [18]

19

Тема: Построение кода RSA

Исходные данные: тестовый текст (не более страницы)

Требуется: 1) Составить алгоритм нахождения простых чисел не более 104; 2) Найти открытую и закрытую части ключа; 3) Закодировать текст и занести результат кодирования в файл;

4) Прочитать файл и декодировать текст

Рекомендуемая литература

 [2], [12] , [18]

20

Тема: Дешифрование (взламывание) кода RSA

Исходные данные:  Открытая часть ключа RSA: число не более 109;  текст, закодированный с помощью RSA.

Требуется: 1) Восстановить секретную часть ключа; 2) Дешифровать текст

Рекомендуемая литература

 [2], [12] , [18]

21

Тема: Нахождение наименее удаленных друг от друга точек

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

Требуется: найти за кратчайшее время точки, расстояние между которыми является наименьшим.

Рекомендуемая литература

 [7], [12], , [18]Препарата

22

Тема: Нахождение выпуклой линейной оболочки 2D множества

Исходные данные: Множество точек на плоскости.

Требуется: 1) Найти точки множества, лежащие на границе выпуклой линейной оболочки;

2) Дать графическое отображение результата

Рекомендуемая литература

 [2], [12] , [18]

23

Тема: Пересечение двумерных множеств

Исходные данные: Несколько множеств точек на плоскости.

Требуется: 1) Составить оптимальный алгоритм нахождения построения линейной оболочки;

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

Рекомендуемая литература

 [2], [12] , [18]

24

Тема: Автоматное представление развития эпидемий

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

Требуется: 1) Организовать вычисления потактно; на каждом такте рассматривается произвольно выбранные два автомата. 2) Составить таблицу переходов с учетом заданного количества тактов, по прошествии которых из состояния «болен» происходит либо переход в состояние «иммунитет», либо (с некоторй вероятностью) в состояние «умер»; 3) Построить графики зависимости числа здоровых, больных и т.д. от количества тактов.

Рекомендуемая литература

 [3], [14] , [18]

25

Тема: Организация очереди с приоритетами

Исходные данные n различных типов задач; каждому типу сопоставляется целое число подзадач; процессор обрабатывает постоянное заданное количество подзадач; по окончании такта работы процессора оставшаяся часть подзадач решаемой задачи ставится в очередь; если задача решена, то появляется новая задача того же типа (которая также ставится в очередь). Рассмотреть два вида приоритетов:.а)приоритет той задачи (или ее части) выше, чем у другой, если количество ее подзадач меньше, чем у другой; б) противоположная дисциплина приоритетов.

Требуется: 1) Выбрать оптимальный алгоритм построения очереди с приоритетами;

2)  Построить алгоритм функционирования вычислительной системы; 3) Дать графическую интерпретацию.

Рекомендуемая литература

 [1], [12], [13] , [18]

26

Тема : Автомат для продажи кофе.

Исходные данные: Автомат продает кофе; чашечка кофе стоит 2 грн. 50 коп. Принимаются 1 грн, 2 грн, монеты в 5, 10, 25 и 50 коп. Кроме отверстий для приема монет и выдачи сдачи у автомата есть кнопки «наливай» и «сброс».

Требуется: 1) Построить табличное представление автомата; 2) Реализовать алгоритм работы автомата; 3) Дать графическое (на форме) представление работы автомата.

Рекомендуемая литература

 [3], [14] , [18]

27

Тема: Алгоритмы обхода графа-триангуляции.

Исходные данные: граф-триангуляция.

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

Рекомендуемая литература

 [4], [8], [12] , [18]

28

Тема: Статистические параметры 2-D потока модельных частиц

Исходные данные: количество модельных частиц. их радиусы, массы, цвет и т.п., размеры рабочей области

Требуется: 1) Реализовать алгоритм событийного моделирования потока модельных частиц; 2) Вывести значения статистических параметров потока: температура, скорость, число Маха по ячейкам и в виде линий уровня

Рекомендуемая литература

 [15], [16], [17] , [18]
Скачать файл