Файл: Основные структуры алгоритмов: сравнительный анализ и примеры их использования (Блок схемы).pdf

Сейчас язык СИ используется для создания широчайшего
спектра программ, от прошивок микроконтроллеров до офисных пакетов^[42]

Язык С++:

Создан на основе языка С для разработки ПО.

С++ - это идеальный инструмент для решения задач в поразительно широком многообразии прикладных областей.^[43]

Указатели позволяют применять язык С++ в самом широком диапазоне задач – от драйверов устройств на уровне аппаратного обеспечения до операционных систем и компиляторов, анимации и мультимедийных приложений.^[44]

Данный язык компилируемый, является быстрым и универсальным.

Указатель может указывать на любые объекты: переменные, массивы, классы, структуры, и даже на функции.^[45]

90е годы.

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

Что-бы решить проблему статичности страниц были разработаны серверные языки программирования, они решили эту проблему делая страницы динамичными.

Перечень серверных языков программирования:

Язык Perl:

Высокоуровневый динамический интерпретируемый язык общего назначения. Разработан в 1987м году. Создатель языка: Ларри Уолл(По образованию-лингвист).

Особенности языка:

Структура языка схожа с языком си, процедурный язык, имеет выражения присваивания и переменные, управляющие структуры и функции.

Изначально Perl задумывался как высокоуровневый кроссплатформенный язык системного программирования. Хотя с того времени Perl вышел далеко за пределы исходного предназначения, он продолжает широко использоваться в системном программировании в родных системах семейства UNIX и на других платформах.^[46]

Perl проектировался как язык, независимый от платформы.

^[47]Если вы ограничиваетесь базовыми операциями с переменными, шаблонами, подпрограммами и высокоуровневым вводом/выводом, ваша программа должна одинаково работать везде, где работает Perl, то есть практически

везде.^[48]

Perl может использоваться для системного программирования даже в системах, не соответствующих стандарту POSIX. Для этого вам понадобятся специализированные модули для этих систем.^[49]

Язык PHP:

Это скриптовый язык общего назначения, используется для создания веб приложений.

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

Более 80% сайтов работает на движках созданных на данном языке.

Синтаксис языка схож я языком Си, некоторые функции и объекты заимствованы у языка Перл.

Для работы языка на сервере используется Apache,

вряд ли в ближайшее время кто-либо будет серьезно использовать PHP под управлением какого-то другого сервера.^[50] Т.к. это лучший сервер для данного языка среди конкурентов.

Сервер — любой отдельно взятый компьютер в Интернете, который позволяет другим машинам использовать себя в качестве "посредника" при передаче данных.^[51]

Сервер — это именно машина ("железо"), а не логическая часть Сети, он может иметь несколько различных IP-адресов (не говоря уже о доменных именах), так что вполне может выглядеть из Интернета как несколько независимых систем.^[52]

Глава 3:

Алгоритмы и алгоритмизация на практике:

Алгоритм сортировки слиянием.

Сортировка слиянием (merge sort) – это рекурсивный алгоритм сортировки, основанный на методе декомпозиции (decomposition) или, как его еще называют, «разделяй и властвуй» (divide and conquer).^[53]

Подразумевается, что первоначальный вызов этой функции имеет вид MERGESORT(????[1..????], 1, ????). ^[54]При каждом вызове функции MERGESORT массив ????[????????????..ℎ????????ℎ], содержащий ℎ????????ℎ − ???????????? + 1 элементов,разделяется (partition) на две максимально равные по длине части.^[55]

Плюсы: Работает на структурах данных с последовательным доступом, Хорошо сочетается с кешированием и подкачкой памяти, Не имеет трудных входных данных, Легко разбивает задачи между процессорами, Устойчив - сохраняет порядок равных элементов. Минусы:

Требуется дополнительная память по размеру исходного массива, На сортированных ранее массивах работает так же долго как и на хаотичных.

Алгоритм сортировки вставками.

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

Первая часть содержит ⌈????/2⌉ элементов, а вторая ⌊????/2⌋. Выражение ⌈????⌉ обозначает наименьшее целое число, которое больше или равно ???? (ближайшее целое сверху, ceil), а ⌊????⌋ – наибольшее целое число, которое меньше или равно ???? (ближайшее целое снизу, floor).^[56] Границей разбиения служит переменная ????????????, в которую записывается номер центрального элемента отрезка [????????????..ℎ????????ℎ].^[57] Полученные подмассивы ????[????????????..????????????] и ????[????????????+1..ℎ????????ℎ] рекурсивно сортируются с использованием сортировки слиянием.^[58]

Разбиение и рекурсивные вызовы осуществляются до тех пор, пока в подмассивах не останется по одному элементу.^[59] После чего осуществляются подъем по дереву рекурсивных вызовов и слияние (merge) отсортированных подмассивов.^[60]

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

^[61]

Матрица:

Массивы могут иметь вид списка(одномерный массив), матрицы(двумерный массив), и т.д. (трех- , четырех- , n- мерный); при этом должны использоваться 1, 2 и т.д. индексов.^[62]

^[63]

Массив - это группа данных одинакового типа, имеющих одно имя. Для работы с отдельным элементом массива нужно указывать индекс.^[64]

Визуализированный классический массив -

Индекс - обозначение порядкового номера элемента. Индекс должен иметь порядковый тип (логический, целый, интервальный, перечисляемый).^[65]

Модель двумерного массива:

^[66]

Каждый элемент массива (индексированная переменная) обозначается именем массива с индексами, которые заключаются в квадратные скобки.^[67]

Вычислительный алгоритм Евклида:

Алгоритм Евклида - эффективный алгоритм для нахождения наибольшего общего делителя двух целых чисел.Для этого алгоритма существует множество практических и теоретических применений. Примеры работы алгоритма:

Алгоритм Евклида, служащий для нахождения общего наибольшего делителя двух целых чисел, сразу же приводит к очень важному методу представления отношения двух целых чисел в виде некоторой сложной дроби особого вида. Например, в применении к числам 840 и 611 алгоритм Евклида дает ряд равенств 840 = 1 · 611 + 229, 611 = 2 · 229 + 153, 229 = 1 · 153 + 76, 153 = 2 · 76 + 1.^[68] Алгоритм Евклида дает метод для представления всякого рационального числа в виде такой непрерывной дроби.^[69] Формула алгоритма Евклида: a = b · q + r.^[70]

Данный алгоритм стал основой криптографического алгоритма RSA. Ещё алгоритм Евклида используется для решения диофантовых линейных уравнений и для построения непрерывных дробей.

Алгоритм Евклида является основным инструментом доказательства теорем(в современной теории чисел).Изображения алгоритма:

Алгоритм поиска статистики:

Поиск статистики - поиск наименьшего или наибольшего значения элемента в массиве. Пусть F — некоторое распределение на действительной прямой. Выборкой объёма n из распределения F называется последовательность независимых случайных величин X1, . . . , Xn с общим распределением F. Статистикой называется любая измеримая функция выборки, т. е. любая случайная величина вида S(X1, . . . , Xn), где S — измеримая по Борелю функция из Rn в R.^[71]

Важными примерами статистик являются выборочные моменты. Для выборочного среднего значения используется обозначение ^[72]. А для выборочного момента порядка k — .^[73]

Способы и методики сравнительного анализа:

Сравнение – это логический прием, необходимый во всякой познавательной деятельности: на различных ее этапах и уровнях, вне зависимости от ее объекта. Сравнительный метод – более узкое понятие.^[74]

Сравнительный анализ - метод анализа объектов, где производится сравнение старого и нового состояния объекта, или сравнение с другим аналогичным объектом - если это уместно. Методика сравнения относится к общенаучным методам исследования. Ф. Энгельс рассматривает использование сравнительного метода в качестве одной из важнейших предпосылок формирования эволюционной теории в биологии и диалектического взгляда на природу в целом.^[75]Методы сравнительного анализа: сравнительно-сопоставительный, сравнительно-историко-генетический, сравнительно-историко-типологический. В прикладных исследованиях сравнительный метод является основным при: оценке, классификации, типологии, генерализации. Используется для разделения общих и отличительных свойств изучаемых объектов. Опыт сравнительного правоведения показывает, что на основе сравнительного метода могут решаться не только научно-познавательные, но и важные прикладные задачи.^[76]Недостаток: Неспособность управлять истинно независимыми переменными исследуемого объекта.

Заключение

По окончанию написания курсовой работы я получил знания о основных структурах алгоритмов и сравнительном анализе.

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

А также, мною была изучена история языков программирования и алгоритмизации в целом.