-
Notifications
You must be signed in to change notification settings - Fork 17
exam02 5
Выполнил: Давтян Артем
Проверил: Нуржасаров Корган
Алгори́тм — конечная совокупность точно заданных правил решения некоторого класса задач или набор инструкций, описывающих порядок действий исполнителя для решения определённой задачи. В старой трактовке вместо слова «порядок» использовалось слово «последовательность», но по мере развития параллельности в работе компьютеров слово «последовательность» стали заменять более общим словом «порядок». Независимые инструкции могут выполняться в произвольном порядке, параллельно, если это позволяют используемые исполнители.
Понятие алгоритма относится к первоначальным, основным, базисным понятиям математики. Вычислительные процессы алгоритмического характера (арифметические действия над целыми числами, нахождение наибольшего общего делителя двух чисел и т. д.) известны человечеству с глубокой древности. Однако в явном виде понятие алгоритма сформировалось лишь в начале XX века.
Частичная формализация понятия алгоритма началась с попыток решения проблемы разрешения (нем. Entscheidungsproblem), которую сформулировал Давид Гильберт в 1928 году. Следующие этапы формализации были необходимы для определения эффективных вычислений[2] или «эффективного метода»; среди таких формализаций — рекурсивные функции Геделя — Эрбрана — Клини 1930, 1934 и 1935 гг., λ-исчисление Алонзо Чёрча 1936 г., «Формулировка 1» Эмиля Поста 1936 года и машина Тьюринга.
- Дискретность — алгоритм должен представлять процесс решения задачи как упорядоченное выполнение некоторых простых шагов. При этом для выполнения каждого шага алгоритма требуется конечный отрезок времени, то есть преобразование исходных данных в результат осуществляется во времени дискретно.
- Детерминированность (определённость). В каждый момент времени следующий шаг работы однозначно определяется состоянием системы. Таким образом, алгоритм выдаёт один и тот же результат (ответ) для одних и тех же исходных данных. В современной трактовке у разных реализаций одного и того же алгоритма должен быть изоморфный граф. С другой стороны, существуют вероятностные алгоритмы, в которых следующий шаг работы зависит от текущего состояния системы и генерируемого случайного числа. Однако при включении метода генерации случайных чисел в список «исходных данных» вероятностный алгоритм становится подвидом обычного.
- Понятность — алгоритм должен включать только те команды, которые доступны исполнителю и входят в его систему команд.
- Завершаемость (конечность) — в более узком понимании алгоритма как математической функции, при правильно заданных начальных данных алгоритм должен завершать работу и выдавать результат за определённое число шагов. Дональд Кнут процедуру, которая удовлетворяет всем свойствам алгоритма, кроме, возможно, конечности, называет методом вычисления. Однако довольно часто определение алгоритма не включает завершаемость за конечное время. В этом случае алгоритм (метод вычисления) определяет частичную функцию. Для вероятностных алгоритмов завершаемость как правило означает, что алгоритм выдаёт результат с вероятностью 1 для любых правильно заданных начальных данных (то есть может в некоторых случаях не завершиться, но вероятность этого должна быть равна 0).
- Массовость (универсальность). Алгоритм должен быть применим к разным наборам начальных данных.
- Результативность — завершение алгоритма определёнными результатами.
Линейный алгоритм — это последовательное выполнение инструкций в строгой очередности их расположения (пример, «сделать бутерброд с сыром»). Последовательность действий: взять кусок хлеба; отрезать кусок сыра; положить его на хлеб.
Ветвления — последовательность действий в соответствии с определенными условиями (если одно условие, то выполняется действие 1, если другой условие, то выполняется действие 2); Пример: Если идет сильный дождь, тогда возьми зонт, а иначе брать зонт не нужно. В большинстве случаев слово «иначе» опускается, так как из контекста первой части фразы уже понятна дальнейшая логика. Пример: Если хотите сообщить что-то важное, позвоните по телефону (в данном случае, очевидно, что если сообщение неважное, то звонить не нужно).
Циклические алгоритмы — это последовательность действий, которую необходимо повторять несколько раз для достижения положительного результата («проверка груш на гнилые и не гнилые»). Пример: В одном ящике лежат груши, необходимо отобрать гнилые и хорошие. Для этого совершаем следующие действия: взять из ящика грушу; посмотреть, гнилая она или нет; если гнилая, то выбросить; если нет, положить в другой ящик; повторить операцию до перебора всех груш в ящике. Иногда случаются ситуации, когда цикл начинает бесконечно повторяться. Это называется зацикливанием или бесконечный цикл.
Программа — термин, в переводе означающий «предписание», то есть заданную последовательность действий. Данное понятие непосредственно связано с понятием алгоритм. Программа — это текст (код), написанный на одном из языков программирования, содержащий инструкции и операторы в логической последовательности, которые заставляют работать аппаратное обеспечение, выполняя необходимые пользователю функции.
Существует несколько видов программного обеспечения (ПО): системное ПО — к этой области относятся операционные системы (все знакомы с операционной системой Microsoft Windows), программы для обслуживания аппаратного обеспечения (жестких дисков, видеокарт и т.д.), а также системные утилиты, например, драйвера (что это?) для принтера, видеокарты и т.д.; прикладное ПО — класс этих программ обширен и разнообразен: текстовые редакторы (например, в пакете Microsoft office программа Word), программы для работы с графикой (пример, Paint), игры); вредоносное ПО — это программное обеспечение, нарушающее работу аппаратного и прикладного обеспечения, которое перестает корректно функционировать; для этого необходимо устанавливать антивирусные программы, чтобы защитить компьютер от «зловредов»; программы для создания программ — среды разработки (Eclipse, IDE Python, и т.д.). Некоторые виды программ удобно писать на определенном языке программирования, для других же используются несколько для написания разных модулей (например, приложение для стационарного компьютера, для телефона, для веб-сайта).
Большинство пользователей компьютеров используют программы, предназначенные для выполнения конкретных прикладных задач, таких, как подготовка и оформление документов, математические вычисления, обработка изображений и т. п. Соответствующие программные средства называют прикладными программами или прикладным программным обеспечением. Управление компонентами вычислительной системы и формирование среды для функционирования прикладных программ берёт на себя системное программное обеспечение, наиболее важной составляющей которого является операционная система.
Логический объект - объект, рассматриваемый в аспекте определения алгоритмом или программой безотносительно к реализации с помощью технических средств.
Причины, следствия, действия, условия, инъекции, промежуточные цели и препятствия – все они считаются логическими объектами. Логический объект должен быть выражен как законченное предложение; однако это предложение не должно быть сложносочиненным/сложноподчиненным и не должно содержать причинно-следственной связи.
Физический объект - объект, рассматриваемый в аспекте взаимодействия логического объекта с техническими средствами.
Томас Х. Кормен. Алгоритмы: вводный курс = Algorithms Unlocked. — М.: «Вильямс», 2014. — 208 с. — ISBN 978-5-8459-1868-0.