Файл: Основные структуры алгоритмов: сравнительный анализ и примеры их использования (Блок схемы).pdf
Добавлен: 30.03.2023
Просмотров: 72
Скачиваний: 2
Введение
Понятие алгоритма относится к основным, базисным понятиям математики. Вычислительные процедуры алгоритмического вида (арифметические действия над числами, нахождение наибольшего общего делителя двух чисел и т. д.) известны человечеству с глубокой древности. Но в явном виде понятие алгоритма образовалось только в начале 20-го века.
Разобраться в основных структурах алгоритмов, сравнительном анализе.
Ознакомится с основными задачами, решаемыми базовыми алгоритмами программирования. Рассмотреть примеры их использования.
Узнать где используются алгоритмы программирования. Изучить:
История языков программирования,
– Слиянием,
вставками.
Матрица – Двумерный массив (Многомерный ) .
Алгоритм Евклида.
Алгоритм поиска статистики.
Способы и методики сравнительного анализа.
Глава 1.
Блок схемы:
Графическое изображение алгоритма широко используется перед программированием задачи вследствие его наглядности, т.к. зрительное восприятие обычно облегчает процесс написания программы, ее корректировки при возможных ошибках, осмысливание процесса обработки информации.[1]
В блок-схемах используются геометрические фигуры, каждая из которых изображает какую-либо операцию или действие, а также этап процесса решения задачи. Каждая фигура называется блоком. Порядок выполнения этапов показывается стрелками, соединяющими блоки. Блоки необходимо размещать сверху вниз или слева направо в порядке их выполнения.[2]
Блок-схемы алгоритмов удобно использовать для объяснения работы уже готового алгоритма, при этом в качестве блоков берутся действительно блоки алгоритма, работа которых не требует пояснений.[3]
Элементы блок схем:
Терминатор - Начало или конец алгоритма:
Процесс: последовательность вычислительных действий.
Решение: Проверка условия.
Границы цикла: Верхняя и нижняя границы.
Подготовка:
Отображает модификацию команды или группы команд с целью воздействия на последующую функцию.
Предопределённый процесс: Отображает процесс состоящий из одной, нескольких операций или шагов программы которые определены в подпрограмме, модуле.
Документ:Отображает данные представленные на носителе в читабелной форме.
Карта:Считывает данные представленные на носителе в виде карты.
Данные: Используется для вывода\ввода данных.
Соединитель: Отображает вход\выход в части схемы, используется для обрыва линии и продолжения её в другом месте.
Комментарий: Используется для добавления комментариев с описанием или пояснительных записей, примечаний.
Линии: Горизонтальные\вертикальные потоки, служат для связи между символами.
Слияние: Слияние Линий Потоков
Межстраничный соединитель:
Алгоритмизация - разработка формального (алгоритмического) метода (или алгоритма) решения практической задачи; причем разработанный алгоритм должен обладать свойствами реализации в виде программы для ЭВМ. Задачи, требующие для решения применения ЭВМ, вначале ставятся в неформальной (конструктивной) форме, в терминах специалиста в заданной предметной области (заказчика). Для разработки алгоритма и программы требуется формализовать задачу, т.е. представить в виде математических формул; точных, однозначно понимаемых определений.[10]
Основные виды алгоритмов:
Линейный алгоритм программирования:
Линейный алгоритм - это алгоритм, в котором действия выполняются только один раз и строго в том порядке, в котором они записаны. [12]
Разветвляющийся алгоритм – это алгоритм, в котором то или иное действие выполняется после анализа условия. Процесс анализа условия и выбора одной из ветвей на блок-схеме показывают с помощью логического блока. [13]
Процесс анализа условия и выбора одной из ветвей на блок-схеме показывают с помощью логического блока. Логический блок имеет один вход и два выхода (ветвь «да» и ветвь «нет»). В блок-схемах разветвляющихся алгоритмов всегда есть логический блок.[14]
Циклический алгоритм программирования:
Это алгоритм, в котором группа операторов выполняется несколько раз подряд.[16]
Часто при решении задач приходится повторять выполнение операций по одним и тем же зависимостям при различных значениях входящих в них переменных и производить многократный проход по одним и тем же участкам алгоритма. Такие участки называются циклами. Алгоритмы, содержащие циклы, называется циклическими. Использование циклов существенно сокращает объем алгоритма.[17]
Глава 2.
Первый язык программирования. Появился в 1943-м году.
Plankalkül - это язык императивного программирования высокого уровня.[19]Конрад Цузе разработал язык программирования высокого уровня Plankalkül (исчисление программ) в 1945 году после переезда из Берлина в конце Второй мировой войны. Любой, кто имел возможность изучить первоначальное определение Планкалкула, поражен его современным вкусом и мощными конструкциями - кажется, что он был создан гораздо позже 1945 года. Однако самым удивительным является тот факт, что в то время, когда Конрад Цузе писал свой документ Plankalkül, единственными двумя работающими компьютерами в мире были ENIAC и Harvard Mark I. Ни один из них не использовал компилятор или переводчик формул - ENIAC даже пришлось перепрограммировать для каждой отдельной проблемы.[20] Хотя Цузе подал заявку на патент на логическую машину, он так и не закончил ее разработку. Логический компьютер был действительно минимален и похож на машину Тьюринга: он состоял из памяти с однобитовыми словами и процессора, способного выполнять только логические операции И, ИЛИ и НЕ над однобитными операндами. Машина была бы способна решить любую числовую или логическую задачу, и, хотя это не является широко известным, ее язык программирования будет Plankalkül.[21]
Другие языки программирования 20го века:
Ассемблер - Вспомогательная программа в операционной системе для автоматического перевода программы с автокода на машинный язык. [22]
Рабочая программа - это программа на машинном языке. Исходная программа может быть написана на языке ассемблера или на языке более высокого уровня (ЯВУ). С помощью программы - транслятора она переводится на машинный язык.[23]
Необходимы языки описания алгоритмов, понятные исполнителю алгоритмов, т.е. электронно-вычислительной машине (ЭВМ); это языки программирования низкого уровня (язык машинных команд, ассемблер и т.п.);[24]
Процедурный ЯВУ для численный методов. Последний стандарт Фортрана – Фортран-95.[25]
Средства, предоставляемые тем языком, на котором алгоритм будет запрограммирован. Например, в языке Паскаль допускаются рекурсивные процедуры, в то время как в Фортране их нет. Таким образом, при использовании различных языков имеется возможность разрабатывать различные алгоритмы.[26]
Для того чтобы человек и компьютер понимали друг друга, разработаны специальные языки для записей алгоритмов – алгоритмические языки. Самые известные алгоритмические языки – это Бейсик (Basic), Паскаль (Pascal), Фортран (Fortran).[27]
Алгоритмический язык. Один из языков программирования, применяемый для формализованной записи алгоритмов.[28]
Ориентированный в основном на вычислительные машины средней мощности. А. разработан в 1963—66 Группой по Автоматизации программирования для Машин Среднего типа (ГАМС), созданной комиссией многостороннего сотрудничества академий наук социалистических стран.[29]
Важными ограничениями являются: запрещение рекурсивного использования процедур, требование обязательной спецификации формальных параметров процедуры, описание идентификаторов (кроме меток) до их использования, упрощение конструкций именующих выражений.[30]
60е годы:
Язык моделирования сложных систем – первый объектно-ориентированный язык.[31]
Название двух алгоритмических языков, разработанных на основе алгола в Норвежском вычислительном центре и неофициально различаемых как симула 1 и симула-67.[32]
Спецификация модели сопоставляет компонентам системы (клиентам, станкам, материалам и т. ц.) процессы. Процесс имеет атрибуты (структуру данных) и программу действий (алгоритм). Модель работает но принципу квазипараллелизма : в каждый момент активен только один процесс; исполняя свою программу, он может использовать свои и чужие атрибуты, порождать новые процессы, планировать себе и другим процессам события — новые фазы активности (применяя встроенное в язык понятие дискретного времени), приостановить себя.[33]
70е годы:
Создан профессором Швейцарского федерального технического института Никлаусом Виртом.[34]
Паскаль, получивший широкое признание и известность, отражаются идеи структурного программирования правила аналитической проверки программ, инженерные аспекты программирования. Описание языка отражает фундаментальные и наиболее важные концепции алгоритмов в очевидной, естественной и легко воспринимаемой форме[35]
Алголоподобный язык паскаль имеет средства для описания структуры данных. Для работы с текстовой информацией предназначены языки лисп, снобол, амбит, сдл и др.[36]
Назван в честь французского математика и философа Блеза Паскаля (1623-1662 гг.).[37]
Шиккард и Паскаль создали независимо друг от друга вычислительные машины — прототипы современных арифмометров. Но широкое практическое применение счетные машины получили только в 19 в.[38]
В связи с этим актуальными становятся задачи отыскания алгоритмов, позволяющих выполнять арифметич. действия с наименьшим числом элементарных операций.[39]
Процедурный язык программирования, разработанный Деннисом Ритчи (Dennis Ritchie) в начале 70-х годов в Bell Laboratories.[40]
Язык Си, созданный в первой половине 1970-х годов, стал, как известно, подлинным прорывом в области программирования. Внезапно программисты обнаружили, что в некоторых
областях, считавшихся до той поры сугубо ассемблерными, таких как ядра операционных
систем, прошивки ЭВМ специального назначения и т. п., автокоды и языки ассемблеров вдруг
утратили монопольное положение, а сами операционные системы стало возможно создавать
переносимыми с одной аппаратной архитектуры на другую.[41]