Цель работы
Целью работы является формирование следующих компетенций:
· ОПК-6: способностью выбирать и оценивать способ реализации информационных систем и устройств (программно, аппаратно или программно-аппаратно) для решения поставленной задачи.
· ПК-11: способностью к проектированию базовых и прикладных информационных технологий.
Компетенции формируются путем разработки программного обеспечения позволяющего производить распределенные вычисления с использованием грид-системы OurGrid. В части компетенции ПК-11 цель достигается за счет проектирования и реализации комплексной информационной среды включающей самостоятельно разработанные и сторонние подсистемы и непосредственно пригодной к использованию. В части компетенции ОПК-6 цель достигается за счет проектирования алгоритма разбиения поставленной задачи на программные подзадачи и оценки эффективности принятого решения.
Порядок выполнения работы
В результате выполнения работы необходимо разработать систему, которая будет пригодна для выполнения грид вычислений в системе OurGrid по задаче выбранной студентом из списка, приведённого в перечне заданий. Итоговая система должна состоять из следующих элементов:
1. Программа, выполняющая задачи на вычислительном узле.
2. Программа, формирующая задачи, отправляющая их в грид среду и формирующая итоговый ответ из результатов вычислительных узлов.
Программное обеспечение для формирования задачи и их выполнения может быть выполнено студентом с использованием любой технологии, однако оно должно обеспечивать возможность быть запущенным кроссплатформенно с использованием грид среды.
Программное обеспечения для формирования заданий должно уметь генерировать задания в формате принимаемом системой OurGrid, дожидаться конца выполнения работы (либо уметь остановить выполнение работы при необходимости), и формировать ответ. Данное ПО должно иметь пользовательский интерфейс в виде окна либо веб-интерфейса. Посредством данного интерфейса пользовать должен уметь выставить настройки выполняемой Работы и увидеть ответ в приемлемом для задачи виде.
Программное обеспечение для вычислительного узла выполняется в форме консольного приложения, параметры которого устанавливаются при старте программы посредством параметров командой строки.
Таким образом, работа выполняется в следующем порядке:
1. Выбрать задание из списка в соответствии с двумя последними цифрами номера зачетной книжки (студенческого билета)
2. Разработать программное обеспечение
3. Продемонстрировать процесс выполнения исходной задачи с эмуляцией грид среды
4. Отчитаться по программному обеспечению
Работа засчитывается в том случае, если она удовлетворяет всем описанным требованиям, а также сдан отчет, который выполняется путем устного опроса студента по принципам решения представленной задачи и исходному коду разработанного программного обеспечения.
Варианты работы
| № Задачи | номер зачетной книжки | |||||||||
Задания
1. Задача коммивояжёра. 5
2. Построение маршрута. 5
3. Расстановка ферзей. 5
4. Подбор пароля. 5
5. Таксисты и пассажиры.. 5
6. Задача о ранце. 6
7. Подматрица с наибольшей суммой. 6
8. Поиск текста в книге. 6
9. Совпадения текстов. 6
10. Латинский квадрат N-го порядка. 6
11. Поиск слов. 7
Задача коммивояжёра
В качестве исходных данных задается матрица смежности графа, описывающая узлы графа (города) и вес ребер (стоимость дорог между городами. Необходимо найти дорогу с наименьшей суммой ребер, при этом проходящую через все города и возвращающуюся к исходному городу. Задача заключается в поиске самого выгодного маршрута, проходящего Маршрут может проходить каждый город не один раз, стартовый город может быть выбран произвольно.
Построение маршрута
В качестве исходных данных задается матрица смежности графа, описывающая узлы графа (города) и вес ребер (стоимость дорог между городами), и число N определяющее длину маршрута. Необходимо подобрать наиболее дешевый маршрут, имеющий длину N и не проходящий через один и тот же город дважды.
Расстановка ферзей
Необходимо на шахматной доске, размером N×N, расставить максимально возможное количество ферзей так, что бы они били каждую свободную клетку и не били друг друга. Математически это можно выразить как N×N, заполненная нулями и единицами таким образом, чтобы сумма всех элементов матрицы была равна N, при этом сумма элементов ни в одном столбце, строке или диагональном ряде матрицы не превышала единицы.
Подбор пароля
В качестве исходных данных выступает файл зашифрованный паролем длиной не более чем 20 символов формата ASCII. Необходимо подобрать пароль к этому файлу.
Таксисты и пассажиры
Таксомоторная компания имеет X свободных такси в разных точках города, и Y пассажиров. Необходимо подобрать такую комбинацию таксистов и пассажиров, что бы суммарная стоимость пути оказалась минимальна для такси. В качестве исходных данных задается матрица смежности графа, описывающая узлы графа (города) и вес ребер (стоимость дорог между городами, позиции таксистов, а также позиции пассажиров и их точки назначения.
Задача о ранце
Из заданного множества предметов со свойствами «стоимость», «вес» и «количество» требуется отобрать подмножество с максимальной полной стоимостью, соблюдая при этом ограничение на суммарный вес не более N кг, где список и параметры предметов, а также N задается пользователем произвольно.
| Предмет | Вес | Цена | Кол-во |
| A | 1.5 | ||
| B | 1.5 | ||
| C | |||
| D | |||
| E | 6.5 | ||
| F | 8.5 | ||
| G | |||
| H |
Таблица 1. Пример характеристик предметов для ранца
Подматрица с наибольшей суммой
Дана матрица размером N×N, содержащая положительные и отрицательные числа. Необходимо найти квадратную подматрицу с максимально возможной суммой.
Поиск текста в книге
Пользователем задается два текста, необходимо посчитать сколько раз первый текст встречается внутри второго. Например, сколько раз “Болконский” встречается в романе “Война и мир”
Совпадения текстов
Дано два текста, необходимо выявить все отрывки первого текста встречающиеся во втором тексте. В расчёт принимаются только отрывки максимально возможно длины. Таким образом если в первом и втором тексте упоминается текст “мама мыла раму”, то слова “мама”, “мыла” и т.д. не учитываются.