Понятие алгоритма
Алгоритм – это точное предписание, которое определяет процесс, ведущий от исходных данных к требуемому конечному результату. Применительно к ЭВМ алгоритм определяет вычислительный процесс, начинающийся с отработки некоторой совокупности возможных исходных данных. Если вычислительный процесс заканчивается получением результатов, то говорят, что соответствующий алгоритм применим к рассматриваемой совокупности исходных данных. Любой применимый алгоритм обладает свойствами: 1) результативностью 2) определенностью 3) массовостью Результативность означает возможность получения результатов после исполнения конечного количества операций. Определенность состоит в совпадении полученных данных независимо от пользователя и применяемых технических средств. Массовость заключается в возможности применения алгоритма к целому классу однотипных задач, различающихся конкретными значениями исходных данных. Для задания алгоритма необходимо описать следующие его элементы: 1) набор объектов, составляющих совокупность возможных исходных данных, промежуточных и конечных результатов. 2) правило начала 3) правило непосредственной переработки информации (описание последовательности действий) 4) правило окончания 5) правило извлечения результатов Программа для ЭВМ представляет собой описание алгоритма и данных на некотором языке программирования. На практике наиболее распространены следующие формы описания алгоритмов: 1) словесная (запись на естественном языке) 2) графическая (изображение из графических символов) 3) псевдокоды на условном алгоритмическом языке, включающие в себя как элементы программирования, так и фразы естественного языка. 4) программная (тексты на языках программирования) Словесный способ записи алгоритма представляет собой описание последовательных этапов обработки данных. А задается в произвольном изложении на естественном языке. Графический способ описания алгоритмов явл-ся более компактным и наглядным по сравнению с словесным. При графич. представлении алгоритм представляется в виде последовательности функций, связанных между собой блоком, каждый из которых соответствует выполнению 1 или нескольких действий. Такое графическое представление А назыв-ся схемой или блок-схемой. Блок-схема к каждому действию соответствует геометрической фигуре, представленной в виде блочного символа. Блочные символы соединены линиями перехода. Псевдокод представляет собой систему обозначения правил, предназначенных для единообразной записи алгоритма. Он занимает промежуточное место между естественным и формальным языком. Алгоритмы, в которых команды выполняются последовательно одна за другой, называются линейными. Для того чтобы сделать алгоритм более наглядным, часто используют блок-схемы. Различные элементы алгоритма изображаются с помощью различных геометрических фигур: 1) ПРОЦЕСС (прямоугольник): применяется для обозначения действия или последовательности действий, изменяющих значение, форму представления или размещения данных. 2) ВХОД_ВЫХОД (параллелограмм): преобразование данных в форму пригодную для обработки или отображения результатов обработки 3) РЕШЕНИЕ (ромб): вопрос, условие или сравнение 4) ПУСК_ОСТАНОВКА (овал): начало, конец или прерывание процесса обработки данных. Вычислительный процесс называется ветвящимся, если для его реализации предусмотрено несколько направлений или ветвей. Каждое отдельное направление обработки данных является отдельной ветвью вычислений. Выбор направления зависит от заранее выбранного признака, который может относиться к исходным данным, к промежуточным или к конечным результатам. 2 ветви ветвящегося процесса: простой. Направление ветвления выбирается логической проверкой. В результате которой возможны 2 ответа: - да, если условие выполнено - нет Следует иметь в виду, что на схеме алгоритма должны быть показаны все направления вычислений, в зависимости от определенного условия. При однократном прохождении программы процесс реализуется только по одной ветви, а остальные исключаются. Любая ветвь, осуществляющая вычисления, должна приводить к завершению вычислительного процесса. Цикл – это многократно повторяющийся участок программы. В организации цикла можно выделить следующие этапы: 1) подготовка или инициализация цикла 2) вычисление цикла или тела цикла 3) модификация параметров 4) проверка условия окончания цикла Порядок выполнения этих этапов может меняться. В зависимости от проверки условия окончания цикла, различают циклы с нижним и верхним окончаниями. Цикл называется детерминированным если число повторений цикла заранее известно. Цикл называется итерационным если число повторений заранее неизвестно. В итерационных алгоритмах необходимо обеспечить обязательное условие выхода из цикла. В процессе подготовки решения задач можно выделить следующие этапы: 1) постановка задачи 2) математическое описание 3) выбор и основание метода решения 4) алгоритмизация вычислительного процесса 5) составление программы 6) отладка программы 7) решение задачи и анализ результатов. Все этапы связаны друг с другом. Математическое описание характеризуется математической формализацией задачи, при которой существующее отношение между величинами, определяющими результат, выражается посредством математических формул. Математическая модель должна удовлетворять 2-ум требованиям: 1) реалистичности – правильное отражение моделью наиболее существенных черт исследуемого явления 2) реализуемости – достигается отличием от второстепенных деталей, чтобы свести задачу к проблеме с известным решением. Компоненты, образующие алгоритмический язык: 1) алфавит 2) синтаксис 3) семантика Алфавит – основной набор символов. Синтаксис – правила построения фраз, позволяющие определять правильно или нет написана та или иная фраза. Семантика – определяет смысловое значение предложений языка. Понятие языка определяется во взаимодействии синтаксических и семантических правил. Синтаксическое правила показывают как образуется данное понятие из других понятий и букв алфавита. Типы операций: 1) арифметические (+,-,/,*,^) 2) логические (и, или, не) 3) конкатенация (&) Различают выражения арифметические, логические и строковые. Арифметические – для определения числового значения. Все функции (стандартные) работают с аргументами. Аргументы записываются в скобках. В качестве аргументов используются константы, аргументы или выражения. Операции выполняются по приоритету.
44.Таблица истинности — это таблица, описывающая логическую функцию. Под «логической функцией» в данном случае понимается функция, у которой значения переменных (параметров функции) и значение самой функции выражают логическую истинность. Например, в двузначной логике они могут принимать значения «истина» либо «ложь» ( либо , либо ). Табличное задание функций встречается не только в логике, но для логических функций таблицы оказались особенно удобными, и с начала XX века за ними закрепилось это специальное название. Особенно часто таблицы истинности применяются в булевой алгебре и в аналогичных системах многозначной логики.
|