Лабораторная работа № Задачи линейного программирования. Математическая модель задачи, экономический анализ. Поиск в ширину

def MergeSort(A):
if len(A) <= 1:
return A
else:
L = A[:len(A) // 2]
R = A[len(A) // 2:]
return merge(MergeSort(L), MergeSort(R))

Оценим сложность этого алгоритма. Пусть массив содержит элементов. Тогда за его можно разделить на две части и после сортировки слить их вместе. Каждая из этих двух частей имеет размер , и за шагов каждую из них можно поделить на две части размером и затем после сортировки слить их вместе. Аналогично, четыре части размером за суммарное шагов делятся на части размером и сливаются вместе. Этот процесс «в глубину» продолжается столько раз, сколько раз можно число делить на 2, до тех пор, пока размер части не станет равен 1, то есть . Итого, общая сложность этого алгоритма равна .

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


3. Задание на лабораторную работу

3. 
   Создать массив на 30 элементов, заполнить её случайными значениями в диапазоне от 0 до 500. Отсортировать массив сортировкой слиянием.
   

4. Содержание отчета

В отчете следует указать:

• 
  Название работы.
  
• 
  Цель работы.
  
• 
  Теоретическая часть.
  
• 
  Выполненное задание.
  
• 
  Заключение (выводы).
  
• 
  Литература.
  

Лабораторная работа № 10. Алгоритм и программа симплекс метода в решении задач линейного программирования. Быстрая сортировка

1. Цель работы
Изучить алгоритм быстрой сортировки
2. Теоретический материал
Быстрая сортировка (quick sort) является одним из наиболее эффективных алгоритмов сортировки. В основе его лежит идея декомпозиции, т.е. поэтапного сведения исходной задачи к набору аналогичных, но более простых, вплоть до тривиальных, а затем объединения результатов. Подход можно описать в виде трех этапов:
Разделение. Массив A[p,r] разбивается на два подмассива A[p,q] и A[q+1,r] (возможно, пустые) так, чтобы все элементы первого были меньше элементов второго. С этой целью в исходном массиве выбирается «опорный» элемент M, определяющий границу разбиения: все элементы со значениями меньшими M, перемещаются в первый подмассив, а элементы со значениями большими либо равными M, размещаются во втором.