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