项目作者: vanyarock01

项目描述 :
discrete analysis
高级语言: C++
项目地址: git://github.com/vanyarock01/da.git
创建时间: 2019-02-12T07:59:39Z
项目社区:https://github.com/vanyarock01/da

开源协议:

下载


Дискретный анализ


Курсовая работа

Вариант: поиск на графе

  1. ./prog preprocess --nodes <nodes file> --edges <edges file> --output <preprocessed graph>
  2. ./prog search --graph <preprocessed graph> --input <input file> --output <output file> [--full-output]

Файл узлов

  1. <id> <lat> <lon>

Файл рёбер

  1. <длина пути в вершинах [n]> <id 1> <id 2><id n>

Выходной файл

  1. <длина найденного пути с относительной погрешностью не более 1e-6>
  2. <длина пути в вершинах [n]> <id 1> <id 2><id n>

Расстояние между точками следует вычислять как расстояние между точками на сфере с радиусом 6371км, если пути между точками нет, вывести -1 и длину пути в вершинах 0.

Индексируемый файл

Алгоритм: astar


Лабораторные работы


Алгоритм: поразрядная сортировка.

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

Ключи - даты в формате DD.MM.YYYY , например: 1.1.1 , 1.9.2009 , 01.09.2009 ,
31.12.2009, данные - числа от 0 до 2 64 - 1.


Структура данных - PATRICIA.

Необходимо создать программную библиотеку, реализующую
указанную структуру данных, на основе которой разработать
программу-словарь.

В словаре каждому ключу, представляющему из
себя регистронезависимую последовательность букв английского
алфавита длиной не более 256 символов, поставлен в соответствие
некоторый номер, от 0 до 2 64 - 1. Разным словам может быть
поставлен в соответствие один и тот же номер.

Программа должна обрабатывать строки входного файла до его
окончания. Каждая строка может иметь следующий формат:

+ word 34 — добавить слово «word» с номером 34 в словарь.
Программа должна вывести строку «OK», если операция прошла
успешно, «Exist», если слово уже находится в словаре.

- word — удалить слово «word» из словаря. Программа должна
вывести «OK», если слово существовало и было удалено,
«NoSuchWord», если слово в словаре не было найдено.

word — найти в словаре слово «word». Программа должна вывести
«OK: 34», если слово было найдено; число, которое следует за
«OK:» — номер, присвоенный слову при добавлении. В случае,
если слово в словаре не было обнаружено, нужно вывести строку
«NoSuchWord».

! Save /path/to/file — сохранить словарь в бинарном компактном
представлении на диск в файл, указанный параметром команды.
В случае успеха, программа должна вывести «OK», в случае
неудачи выполнения операции, программа должна вывести
описание ошибки (см. ниже).

! Load /path/to/file — загрузить словарь из файла. Предполагается,
что файл был ранее подготовлен при помощи команды Save. В
случае успеха, программа должна вывести строку «OК», а
загруженный словарь должен заменить текущий (с которым
происходит работа); в случае неуспеха, должна быть выведена
диагностика, а рабочий словарь должен остаться без изменений.
Кроме системных ошибок, программа должна корректно
обрабатывать случаи несовпадения формата указанного файла и
представления данных словаря во внешнем файле.


Вариант задания: поиск большого количества образцов при помощи алгоритма Ахо-Корасик.

Формат входных данных

Искомый образец задается на первой строке входного файла.

В случае, если в задании требуется найти несколько образцов, они задаются по одному на
строку вплоть до пустой строки.

Затем следует текст, состоящий из слов или чисел, в котором нужно найти заданные
образцы.

Никаких ограничений на длину строк, равно как на количество слов или числ в них, не
накладывается.


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

Алфавит строк: строчные буквы латинского алфавита (т.е., от a до z).

Вариант задания: поиск в известном тексте неизвестных заранее образцов

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

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


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

Список арифметических операций:

  • Сложение (+).
  • Вычитание (-).
  • Умножение (*).
  • Возведение в степень (^).
  • Деление (/).

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

Список условий:

  • Больше (>).
  • Меньше (<).
  • Равно (=).

В случае выполнения условия, программа должна вывести на экран
строку true, в противном случае — false.


При помощи метода динамического программирования разработать алгоритм решения задачи, определяемой
своим вариантом; оценить время выполнения алгоритма и объем затрачиваемой оперативной памяти. Перед
выполнением задания необходимо обосновать применимость метода динамического программирования.

Вариант задания: игра с числом.

Имеется натуральное число n. За один ход с ним можно произвести следующие действия:

  • Вычесть единицу
  • Разделить на два
  • Разделить на три

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


Разрабтать жадный алгоритм решения задачи, определяемой своим
вариантом. Доказать его корректность, оценить скорость и объём
затрачиваемой оперативной памяти.

Вариант задания: оптимальная сортировка чисел

Дана последовательность длины N из целых чисел 1, 2, 3. Необходимо
найти минимальное количество обменов элементов последовательности,
в результате которых последовательность стала бы отсортированной.

Входные данные: число N на первой строке и N чисел на второй строке.

Выходные данные: минимальное количество обменов.


Вариант задания: алгоритм Дейкстры

Задан взвешенный неориентированный граф, состоящий из n вершин и m
ребер. Вершины пронумерованы целыми числами от 1 до n. Необходимо
найти длину кратчайшего пути из вершины с номером start в вершину с
номером finish при помощи алгоритма Дейкстры. Длина пути равна
сумме весов ребер на этом пути. Граф не содержит петель и кратных
ребер.

Входные данные:

В первой строке заданы 1 ≤ n ≤ 105, 1 ≤ m ≤ 105, 1 ≤ start ≤ n и 1 ≤
finish ≤ n. В следующих m строках записаны ребра. Каждая строка
содержит три числа – номера вершин, соединенных ребром, и вес
данного ребра. Вес ребра – целое число от 0 до 109.

Выходные данные:

Необходимо вывести одно число – длину кратчайшего пути между
указанными вершинами. Если пути между указанными вершинами не
существует, следует вывести строку “No solution” (без кавычек).