|
Информационный менеджмент. Вариант №03
|
|
| engineerklub | Дата: Вторник, 15.02.2022, 18:58 | Сообщение # 1 |
 Генералиссимус
Группа: Администраторы
Сообщений: 28578
Статус: Offline
| Информационный менеджмент. Вариант №03
Тип работы: Работа Контрольная
Форматы файлов: Microsoft Word
Сдано в учебном заведении: СибГУТИ
Описание:
Задание
Написать программу, которая оптимальным образом расставляет скобки при перемножении матриц M1M2M3M4M5M6M7M8M9M10M11M12. Матрицы имеют следующие размерности:
M1[r0xr1], M2[r1xr2], M3[r2xr3], M4[r3xr4], M5[r4xr5], M6[r5xr6], M7[r6xr7], M8[r7xr8], M9[r8xr9], M10[r0xr10], M11[r10xr11], M12[r11xr12].
Размерности матриц считать из файла.
Вывести промежуточные вычисления, результат расстановки скобок и трудоемкость полученной расстановки.
Номер варианта выбирается по последней цифре пароля.
r0 r1 r2 r3 r4 r5 r6 r7 r8 r9 r10 r11 r12
3 4 6 6 9 7 5 6 4 2 9 3 7 5
Описание алгоритма
Задача решается с помощью следующего алгоритма:
1) Заполняем трудоемкости матриц:
Трудоемкости на главной диагонали равны 0:
for i:=1 to n do f(i,i):=0;
2) Внешний цикл по t – длине перемножаемого блока;
Средний цикл по k – местоположению блока;
Внутренний – поиск минимума по j.
for t:=1 to n–1 do
for k:=1 to n–t do
СКАЧАТЬ
|
| |
| |
| engineerklub | Дата: Вторник, 15.02.2022, 18:58 | Сообщение # 2 |
|
Генералиссимус
Группа: Администраторы
Сообщений: 28578
Статус: Offline
| Тип работы: Работа Лабораторная
Форматы файлов: Microsoft Word
Сдано в учебном заведении: СибГУТИ
Описание:
Задание
Написать программу, которая оптимальным образом расставляет скобки при перемножении матриц M1M2M3M4M5M6M7M8M9M10M11M12. Матрицы имеют следующие размерности:
M1[r0xr1], M2[r1xr2], M3[r2xr3], M4[r3xr4], M5[r4xr5], M6[r5xr6], M7[r6xr7], M8[r7xr8], M9[r8xr9], M10[r0xr10], M11[r10xr11], M12[r11xr12].
Размерности матриц считать из файла.
Вывести промежуточные вычисления, результат расстановки скобок и трудоемкость полученной расстановки.
Номер варианта выбирается по последней цифре пароля.
r0 r1 r2 r3 r4 r5 r6 r7 r8 r9 r10 r11 r12
3 4 6 6 9 7 5 6 4 2 9 3 7 5
Описание алгоритма
Задача решается с помощью следующего алгоритма:
1) Заполняем трудоемкости матриц:
Трудоемкости на главной диагонали равны 0:
for i:=1 to n do f(i,i):=0;
2) Внешний цикл по t – длине перемножаемого блока;
Средний цикл по k – местоположению блока;
Внутренний – поиск минимума по j.
for t:=1 to n–1 do
for k:=1 to n–t do
.
ЛАБОРАТОРНАЯ РАБОТА №1
по дисциплине
«Теория сложности вычислительных процессов и структур»
Задание
Написать программу, которая по алгоритму Краскала находит остов минимального веса для связного взвешенного неориентированного графа, имеющего 10 вершин. Граф задан матрицей смежности (0 означает, что соответствующей дуги нет). Данные считать из файла.
Вывести ребра остова минимального веса в порядке их присоединения и вес остова.
Номер варианта выбирается по последней цифре пароля.
Вариант 3
0 5 0 9 10 13 18 16 20 21
5 0 20 12 5 4 17 20 10 17
0 20 0 7 18 0 19 6 17 19
9 12 7 0 5 12 14 5 21 25
10 5 18 5 0 19 19 0 20 8
13 4 0 12 19 0 5 21 0 21
18 17 19 14 19 5 0 13 5 0
16 20 6 5 0 21 13 0 11 22
20 10 17 21 20 0 5 11 0 16
21 17 19 25 8 21 0 22 16 0
Описание алгоритма Краскала
Задача: Дан граф G=(V,E) – связный, неориентированный, взвешенный. Нам нужно выделить в нем минимальный (по суммарному весу ребер) связный граф с теми же вершинами – остов (остовное дерево), т.е. исключить из графа часть ребер таким образом, чтобы сумма весов оставшихся была минимальна, и получившийся граф по- прежнему был связным.
ЛАБОРАТОРНАЯ РАБОТА №2
по дисциплине
«Теория сложности вычислительных процессов и структур»
Задание
Написать программу, которая по алгоритму Дейкстры (если Ваша фамилия начинается с гласной буквы) или Форда-Беллмана (если Ваша фамилия начинается с согласной буквы) находит кратчайшее расстояние от вершины с номером Вашего варианта до всех остальных вершин связного взвешенного неориентированного графа, имеющего 10 вершин (нумерация вершин начинается с 0).
Граф задан матрицей смежности (0 означает, что соответствующей дуги нет). Данные считать из файла.
Вывести все найденные кратчайшие расстояния и соответствующие им пути (в виде последовательности ребер).
Номер варианта выбирается по последней цифре пароля.
Вариант 3
0 9 8 0 7 4 10 6 6 4
9 0 1 7 8 6 4 8 7 2
8 1 0 8 6 4 0 9 2 4
0 7 8 0 2 0 0 7 3 0
7 8 6 2 0 0 10 7 5 0
4 6 4 0 0 0 6 3 10 0
10 4 0 0 10 6 0 10 2 10
6 8 9 7 7 3 10 0 9 6
6 7 2 3 5 10 2 9 0 11
4 2 4 0 0 0 10 6 11 0
Описание алгоритма Дейкстры
Ищем расстояние от нулевой вершины.
S = {o}
D = C(0,i) i = 0……n
While S ≠ V do
1. выбираем вершину w, которая принадлежит множеству вершин V\\S (V без S) с минимальной стоимостью D(w)
2. S:=S+ w (добавляем вершину w к множеству S )
3. для всех вершин v
V\\S do D(v):=min( D(v), D(w)+С(w, v) ) пересчитываем стоимости всех остальных вершин.
СКАЧАТЬ
|
| |
| |
| engineerklub | Дата: Вторник, 15.02.2022, 18:59 | Сообщение # 3 |
|
Генералиссимус
Группа: Администраторы
Сообщений: 28578
Статус: Offline
| ЛАБОРАТОРНАЯ РАБОТА №3
по дисциплине
«Теория сложности вычислительных процессов и структур»
Задание
Имеется склад, на котором присутствует некоторый ассортимент товаров. Запас каждого товара неограничен. У каждого товара своя стоимость сi и масса mi. Написать программу, которая методом динамического программирования формирует набор товаров максимальной стоимости таким образом, чтобы его суммарная масса не превышала заданную грузоподъемность М.
Вывести промежуточные вычисления, сформированный набор, его стоимость и массу.
Номер варианта выбирается по последней цифре пароля.
Вариант 3
Номер товара, i mi сi M
1 7 15 95
2 14 48
3 13 33 52
4 15 50
Описание алгоритма
Задача: Имеется склад, на котором есть некоторый ассортимент товаров. Запас каждого товара считается неограниченным. Товары имеют две характеристики: mi – масса, ci – стоимость; .
Необходимо выбрать набор товаров так, чтобы его суммарная масса не превосходила заранее фиксированную массу М (т.е. ), и стоимость набора была как можно больше ( ).
СКАЧАТЬ
|
| |
| |
