Файл: Основные структуры алгоритмов: сравнительный анализ и примеры их использования (Блок схемы).pdf
Добавлен: 30.03.2023
Просмотров: 77
Скачиваний: 2
Сейчас язык СИ используется для создания широчайшего
спектра программ, от прошивок микроконтроллеров до офисных пакетов[42]
Создан на основе языка С для разработки ПО.
С++ - это идеальный инструмент для решения задач в поразительно широком многообразии прикладных областей.[43]
Указатели позволяют применять язык С++ в самом широком диапазоне задач – от драйверов устройств на уровне аппаратного обеспечения до операционных систем и компиляторов, анимации и мультимедийных приложений.[44]
Данный язык компилируемый, является быстрым и универсальным.
Указатель может указывать на любые объекты: переменные, массивы, классы, структуры, и даже на функции.[45]
Интернет получил своё распространение, но страницы сайтов не были активными, это значит что администратору сайта вручную требовалось редактировать код страницы для изменения содержимого.
Что-бы решить проблему статичности страниц были разработаны серверные языки программирования, они решили эту проблему делая страницы динамичными.
Перечень серверных языков программирования:
Высокоуровневый динамический интерпретируемый язык общего назначения. Разработан в 1987м году. Создатель языка: Ларри Уолл(По образованию-лингвист).
Особенности языка:
Структура языка схожа с языком си, процедурный язык, имеет выражения присваивания и переменные, управляющие структуры и функции.
Изначально Perl задумывался как высокоуровневый кроссплатформенный язык системного программирования. Хотя с того времени Perl вышел далеко за пределы исходного предназначения, он продолжает широко использоваться в системном программировании в родных системах семейства UNIX и на других платформах.[46]
Perl проектировался как язык, независимый от платформы.
[47]Если вы ограничиваетесь базовыми операциями с переменными, шаблонами, подпрограммами и высокоуровневым вводом/выводом, ваша программа должна одинаково работать везде, где работает Perl, то есть практически
везде.[48]
Perl может использоваться для системного программирования даже в системах, не соответствующих стандарту POSIX. Для этого вам понадобятся специализированные модули для этих систем.[49]
Это скриптовый язык общего назначения, используется для создания веб приложений.
В 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]
В начале сортировки последовательность будет пустой. После каждого шага алгоритма выбирается один элемент входных данных, помещается на правильную позицию в отсортированную последовательность, это будет происходить пока набор входных данных не будет исчерпан. А при использовании бинарного поиска для нахождения места для элемента в отсортированной части - алгоритм будет работать быстрее. Проблема сдвига массива вправо устраняется с помощью смены указателей.
Матрица:
Массивы могут иметь вид списка(одномерный массив), матрицы(двумерный массив), и т.д. (трех- , четырех- , n- мерный); при этом должны использоваться 1, 2 и т.д. индексов.[62]
Массив - это группа данных одинакового типа, имеющих одно имя. Для работы с отдельным элементом массива нужно указывать индекс.[64]
Визуализированный классический массив -
Индекс - обозначение порядкового номера элемента. Индекс должен иметь порядковый тип (логический, целый, интервальный, перечисляемый).[65]
Модель двумерного массива:
Каждый элемент массива (индексированная переменная) обозначается именем массива с индексами, которые заключаются в квадратные скобки.[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]Недостаток: Неспособность управлять истинно независимыми переменными исследуемого объекта.
Заключение
По окончанию написания курсовой работы я получил знания о основных структурах алгоритмов и сравнительном анализе.
Узнал для каких задач используются базовые алгоритмы программирования, разобрался с блок схемами, и узнал где применяются алгоритмы сделанные на их основе. Изучил популярные и нужные алгоритмы такие как: алгоритмы сортировки, статистические алгоритмы и алгоритмы сравнительного анализа.
А также, мною была изучена история языков программирования и алгоритмизации в целом.