ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 11.05.2021
Просмотров: 510
Скачиваний: 1
ЛЕКЦИЯ. АЛГОРИТМЫ
1. ОБЩЕЕ ПОНЯТИЕ АЛГОРИТМА
Для решения задач существуют определенные правила, например, правила сложения и вычитания дробей, порядок выполнения математических действий, правила и процедуры разрешения юридических вопросов, т.е. имеются соответствующие алгоритмы.
С изобретением ЭВМ и началом их широкого использования в самых различных областях деятельности понятия "алгоритм" и производное от него –"алгоритмизация" приобрели статус общенаучных. Во многом этому способствовало и то, что к тому времени сформировалась теория алгоритмов, которая из ветви математической логики развилась в самостоятельное научное направление, ныне тесно связанное с кибернетикой, информатикой и вычислительной математикой.
В соответствии с данной теорией понятие алгоритма может рассматриваться (и применяться) на трех уровнях: интуитивно-содержательном, формальных уточнений и так называемом прикладном уровне.
Сферой приложения первого и второго уровней являются математика и общая кибернетика. Здесь понятием "алгоритм" обычно обозначают точное предписание, задающее вычислительный процесс, ведущий от начальных данных, которые могут варьироваться, к искомому результату, или всякую систему вычислений, выполняемых по строго определенным правилам, которая после какого-либо числа шагов (операций) приводит к решению поставленной задачи.
Алгоритм – это последовательность действий со строго определенными правилами выполнения.
Алгоритмы делятся на вычислительные и невычислительные.
Например, правила решения уравнения, построение графика функций, вычисление / = (ах+ву) • d –это вычислительные алгоритмы. Расписание лекций, режим дня, процессуальный порядок ведения допроса – это невычислительные алгоритмы.
Алгоритм состоит из команд.
Команда – это отдельное указание исполнителю выполнить некоторое законченное действие.
Команды алгоритма выполняются одна за другой. Последовательное выполнение команд алгоритма приводит к решению задачи.
Основные свойства алгоритма – это детерминированность (определенность), дискретность, массовость, результативность и инвариантность по отношению к вычислителю.
1. Определенность – это однозначность предписываемой последовательности действий, не допускающая произвольного ее толкования. Именно в силу определенности предписания алгоритмический процесс является детерминированным: каждая стадия процесса однозначно определяет следующую стадию. Таким образом, алгоритм не должен содержать указаний, смысл которых может пониматься неоднозначно.
Необходимость такого требования вытекает из принципа формального исполнения алгоритма. Если предписание может пониматься двояко, то исполнить его формально не представляется возможным. Придется принимать самостоятельное решение, на что исполнитель права не имеет.
2. Дискретность – это деление алгоритма на отдельные действия (команды), которые выполняются только последовательно, причем каждое действие должно быть закончено исполнителем прежде, чем он прейдет к выполнению следующего. Запись алгоритма должна быть такова, чтобы, выполнив очередную команду, исполнитель точно знал, какую команду надо выполнять следующей (свойство точности алгоритма).
3. Массовость означает, что алгоритм можно применять для решения любых задач одного и того же типа, которые отличают только исходными данными.
4. Результативность означает, что при точном выполнении всех команд алгоритма процесс заканчивается получением определенного результата за конечное число шагов. Если задача решения не имеет, – это тоже результат.
5. Инвариантность по отношению к вычислителю – это независимость от конкретного типа вычислителя (исполнителя). Данное свойство не означает, что при разработке алгоритма можно полностью игнорировать характер вычислительных средств, с помощью которых он будет реализован. Однако это относится не к принципиальной возможности, а лишь к удобству реализации алгоритма тем или иным средством.
2. ПОНЯТИЕ АЛГОРИТМА ДЛЯ ПРИКЛАДНЫХ ЗАДАЧ
Сферой приложения "прикладного" уровня понятия "алгоритм" являются нематематические области знания и практической деятельности, в частности связанные с анализом человеческого поведения, способов переработки человеком воспринимаемой им информации.
Характерной особенностью этого уровня применения алгоритмического подхода является то, что "жесткие" алгоритмы, используемые в математике и вычислительных машинах, здесь тем или иным способом "ослабляются". Важность этой операции состоит в том, что в такого рода алгоритмическом процессе акты принятия решений могут осуществляться в ситуации выбора. В "жестких" (классических) алгоритмах ситуация выбора решения (действия) исключается, поскольку процесс решения задачи здесь детерминирован во всех деталях, вплоть до уровня элементарных операций.
Необходимость процедуры "ослабления" таких алгоритмов определяется тем, что далеко не все объекты, исследуемые в нематематических областях знания и практической деятельности (куда относится и юридическая деятельность), являются "жесткими", конструктивными, т.е. однозначно опознаваемыми (что обычно выдвигается как одно из условий построения и использования "жестких" алгоритмов). Отсюда и разные типы задач, решаемых в этих областях.
Типы задач, решаемых на прикладном уровне:
1. Одни из них по своей сути являются определенными, ибо вывод по ним однозначно обусловлен исходными данными.
2. В других такой однозначности нет. Здесь исходные данные и связь их с решением носят вероятностный характер. Решение зависит от вероятностно-статистической оценки результатов операций, проведенных над исходными данными. Вот почему эти задачи и алгоритмы их решения часто называют расплывчатыми, или стохастическими. Решение таких задач может содержать несколько значений, что определяется характером тех ограничений, которые задаются исходными данными (информацией).
Другим вариантом решения задач такого типа являются альтернативные заключения. Они имеют место в тех случаях, когда исходные данные фактически содержат ограничения, но они явно не заданы, их просто недостает в самой постановке задачи.
Если рассматривать юридическую деятельность как деятельность, сопряженную с решением правовых задач, то нельзя не заметить, что для нее характерны и определенные, и "расплывчатые" задачи. Например, решение процессуальных задач – это жесткие алгоритмы, а тактических задач – нет.
Это значит, что, решая проблему оптимизации юридической деятельности и повышения ее эффективности на базе алгоритмизации и автоматизации информационных процессов, надо ориентироваться на использование не одного какого-либо универсального алгоритма, а серии различных алгоритмов. При этом необходимо учитывать специфику как правовых задач в целом, так и специфику задач в рамках их конкретных классов, например, криминалистических задач.
Из сказанного вытекает вывод: принципиально невозможно разработать единый алгоритм, пригодный для решения задач любого класса. Отсюда – нельзя дать универсальное и достаточно строгое определение и самого понятия "алгоритм решения правовой задачи".
Несмотря на это, алгоритмы, которые могут быть использованы для решения правовых задач, должны обладать всеми свойствами, которые присущи классическим ("жестким") алгоритмам.
3. СПОСОБЫ ЗАДАНИЯ АЛГОРИТМОВ
Алгоритм задается в той форме, которая понятна человеку. Алгоритм можно задавать математической формулой, словесным описанием, графиком, логической схемой и т.п.
Наиболее распространенные способы задания алгоритмов следующие:
Словесный способ – отражает содержание выполняемых действий средствами естественного языка. К достоинствам этого способа описания следует отнести его общедоступность, а также возможность описывать алгоритм с любой степенью детализации. Однако словесное описание алгоритмов на любом естественном языке обладает некоторыми недостатками, а именно: возможность неоднозначного понимания предписаний и утверждений; громоздкость, связанная с избыточностью разговорных языков (наличие в предложениях слов, без которых можно обойтись); отсутствие наглядности логических связей между частями алгоритма.
Формально-словесный способ – основан на записи содержания выполняемых действий с использованием изобразительных возможностей языка математики, дополненного с целью указания необходимых пояснений средствами естественного языка. Данный способ, обладая всеми достоинствами словесного способа, вместе с тем более лаконичен, а значит, и более нагляден, имеет большую формализацию, однако также не является строго формальным.
Графический способ (в виде блок-схемы) – представляет собой изображение логико-математической структуры алгоритма, при котором все этапы процесса обработки данных представляются с помощью определенного набора геометрических фигур (блоков), имеющих строго определенную конфигурацию в соответствии с характером выполняемых действий. Таким образом, блок-схема – это графическое изображение структуры алгоритма в виде геометрических фигур или блоков.
4. Алгоритмические языки. Трансляторы.
Алгоритмический язык – это язык записи алгоритма.
Последовательность команд, записанных на алгоритмическом языке, называется программой. Соответственно, алгоритмические языки представляют собой средства описания данных и алгоритмов решения задач, и разработаны для составления программы пользователем. Они отличаются друг от друга различными свойствами и областью применения.
1. Класс машинно-зависимых языков. Центральный процессор ЭВМ предназначен для выполнения команд, которые представляются в виде групп двоичных цифр (битов), т.е. в виде последовательностей из нулей и единиц. Команды, представленные в таком виде, считаются записанными в машинном коде или на машинном языке.
Двоичный код очень удобен для использования в ЭВМ, но чрезвычайно не удобен для человека и поэтому в наши дни почти не применяется. Цифровая форма записи команд, необходимость разбивать алгоритм на мелкие операции делают программу ненаглядной и громоздкой, затрудняют ее отладку. "Индивидуальный характер" языков ЭВМ исключает прямой перенос программы с машины одного типа на машину другого типа. Процесс программирования на машинном языке сложен и трудоемок, требует тщательности, большого внимания, хорошего знания особенностей ЭВМ, на которых предстоит производить расчеты.
Переход от более абстрактной формы записи к машинному коду можно автоматизировать. Первые программы, которые выполняли такое преобразование, назывались ассемблерами. Главное преимущество ассемблеров в том, что они дают возможность пользователям оперировать символическими наименованиями, состоящими из букв и цифр, вместо того, чтобы запоминать их двоичные эквиваленты.
Язык ассемблера делает доступными все программно-управляемые компоненты компьютера, поэтому он применяется для написания программ, использующих специфику конкретной аппаратуры. Ассемблер – это наиболее трудоемкий язык программирования, и из-за его низкого уровня (уровень языка характеризует степень его близости к естественному, человеческому языку) не удается построить средства отладки, которые существенно снизили бы трудоемкость разработки программ. Команды Ассемблера очень примитивны, так как соответствуют операциям, которые центральный процессор может непосредственно выполнить, – например, команды сравнения двух символов или сложения двух чисел, поэтому программирование на ассемблере требует от программиста детальных знаний технических компонентов ПК. Ассемблер используется, в основном, для системного программирования (компоненты ОС, драйверы и др.).
2. Класс машинно-ориентированных языков. Данный класс представляют языки группы С, С++, Турбо С. Разработчики данных языков попытались объединить возможности ассемблера со встроенными структурами данных.
3. Класс универсальных языков. Важным шагом в развитии языков программирования было появление машинно-независимых языков. Разработчики этих языков стремились: во-первых, создать языки, воспринимаемые любым компьютером; во-вторых, максимально учесть специфику класса задач, для решения которых данный язык предполагалось использовать. Например, для многих научно-технических задач характерны большие расчеты по сложным формулам, поэтому в ориентированные на такие задачи языки вводят удобные средства для их записи. Использование понятий, терминов, символов, привычных для специалистов соответствующей области знаний, облегчает им изучение языка, упрощает процесс составления и отладки программ.
К настоящему времени разработано большое количество машинно-независимых языков программирования: Бейсик, Паскаль, Фортран и др. Машино-независимые языки обычно называют языками высокого уровня.
Каждая команда языка высокого уровня обычно соответствует сразу нескольким машинным командам. В связи с этим для различных ЭВМ можно использовать один абстрактный, т.е. не встроенный в определенный процессор, язык высокого уровня.
Важным преимуществом алгоритмических языков высокого уровня по сравнению с машинным языком является их универсальность, независимость от конкретного типа ЭВМ. Программа, написанная на таком языке, может выполняться на разных машинах, при переходе на другую ЭВМ не требуется никаких переработок.
Чтобы программы на языках высокого уровня работали, необходимы специальные программы-переводчики. Программа-переводчик называется транслятором. Транслятор переводит исходную программу (на языке высокого уровня) в объектную программу, т.е. программу на машинном языке. Трансляторы делятся на компиляторы и интерпретаторы.
Компилятор переводит исходную программу в объектную целиком. Интерпретатор транслирует и выполняет команды исходной программы по одной.
4. Класс проблемно-ориентированных языков представлен языками Лого, РПГ, системой программирования GPSS и др. Язык Лого был создан с целью обучения школьников основам алгоритмического мышления и программирования. Лого – диалоговый процедурный язык, реализованный на основе интерпретатора с возможностью работы со списками и на их основе с текстами, оснащенный развитыми графическими средствами.
РПГ, или генератор отчетов, представляет собой язык, включающий многие понятия и выражения, которые связаны с машинными методами составления отчетов и проектирования форм выходных документов. Язык используется главным образом для печати отчетов, записанных в одном или нескольких файлах баз данных.
Система программирования GPSS ориентирована на моделирование систем с помощью событий. В терминах этого языка легко описывается и исследуется класс моделей массового обслуживания и другие системы, работающие в реальном масштабе времени.