Skip to content

Latest commit

 

History

History
231 lines (165 loc) · 13 KB

README.md

File metadata and controls

231 lines (165 loc) · 13 KB

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


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

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

Файл узлов

<id> <lat> <lon>

Файл рёбер

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

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

<длина найденного пути с относительной погрешностью не более 1e-6>
<длина пути в вершинах [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" (без кавычек).