Тема: Понятие и свойства алгоритма
1. Понятие алгоритма. Свойства алгоритма.
Алгоритм - это понятное и точное указание исполнителю совершить последовательность действий, направленных на решение поставленной задачи.
Исполнителем может являться как техническое устройство, так и человек.
С помощью алгоритма может быть описана работа любого технического устройства, в частности компьютера.
С точки зрения информатики алгоритм - это конечная последовательность операций или правил, преобразующих исходную входную информацию в выходную.
Все алгоритмы обладают некоторыми общими свойствами:
1. Дискретность -Процесс решения задачи должен быть разбит на последовательность отдельных шагов, каждый из которых называется командой. Наиболее существенным здесь является тот факт, что алгоритм есть последовательность четко выделенных пунктов,- такие объекты принято называть дискретными. Таким образом, разделение информационного процесса в алгоритме на отдельные команды является важным свойством алгоритма и называется дискретностью.
2.Понятность - Чтобы исполнитель мог выполнить преобразование объекта согласно алгоритму, он должен быть в состоянии понять и выполнить каждую команду. Поэтому каждый алгоритм должен составлять в расчете на конкретного исполнителя с учетом его возможностей. Это свойство алгоритмов называется понятностью.
У каждого исполнителя имеется перечень команд, которые он может исполнить. Такой перечень (список) называется системой команд исполнителя (СКИ). Понятными исполнителю будут являться только те команды, которые попадают в этот список.
|
|
|
3. Определенность - Команды, образующие алгоритм должны быть предельно четкими и однозначными. Их результат не может зависеть от какой-либо дополнительной информации извне алгоритма. Сколько бы раз вы не запускали программу, для одних и тех же исходных данных всегда будет получаться один и тот же результат. Такое свойство называется определенностью(детерминированностью). При наличии ошибок в алгоритме это свойство может иногда нарушаться.
4. Результативность - результат выполнения алгоритма должен быть обязательно получен, т.е. правильный алгоритм не может обрываться безрезультатно из-за какого-либо непреодолимого препятствия в ходе выполнения. Кроме того, любой алгоритм должен завершиться за конечное число шагов. Такое свойство алгоритма называется результативностью (конечностью). Большинство алгоритмов данным требованиям удовлетворяют, но при наличии ошибок возможны нарушения результативности.
5. Корректность - Любой алгоритм создан для решения той или иной задачи, поэтому необходима уверенность, что это решение будет правильным для любых допустимых исходных данных. Указанное свойство алгоритма приято называть его корректностью. В связи с этим большое значение имеет тщательное тестирование алгоритма перед его использованием. Грамотная и всесторонняя отладка для сложных алгоритмов часто требует значительно больших усилий, чем собственно разработка этих алгоритмов. Именно результатом недостаточной тщательности тестирования чаще всего объясняются многочисленные сюрпризы, преподносимые современным программным обеспечением в процессе эксплуатации.
|
|
|
6.Массовость - Алгоритм имеет смысл разрабатывать только в том случае, когда он будет применяться многократно для различных наборов исходных данных. Массовость алгоритма в отдельных случаях может нарушаться: к числу подобных исключений можно отнести алгоритмы пользования некоторыми простыми автоматами (для них входными данными служит единственный тип монет).
Разработанный алгоритм можно записать несколькими способами: на естественном языке, на языке программирования, в виде блок-схемы.
При решении ряда комбинаторных задач точное оптимальное решение может быть найдено только при полном переборе всех возможных вариантов. Время поиска оптимального таких задач пропорционально факториалу размерности задачи. Поэтому для задач больших размерностей применяют эвристические алгоритмы, которые не дают гарантии получения оптимального решения, но находят приемлемые решения за относительно небольшое время. Примером эвристического алгоритма может служить генетический алгоритм, который используется для решения задач оптимизации и моделирования путем последовательного подбора искомых параметров с применением механизмов, напоминающих биологическую эволюцию.
|
|
|
2. Основные понятия алгоритмического программирования.
Данные - величины, обрабатываемые программой.
Переменные - данные, значение которых может меняться в процессе выполнения программы.
Константы - данные, значение которых не изменяется в процессе выполнения программы.
Имена (идентификаторы) - используются для обозначения объектов в программе (переменных, массивов, функций и др.) . Каждая переменная имеет свое уникальное имя.
Операции :
- арифметические операции;- логические операции и, или, не;- операции отношения <, >, <=, >=, =, <>;- операции сцепки ("присоединения", "конкатенации") символьных значений друг с другом с образованием одной длиной строки; изображается знаком "+";
|
|
|
Выражения - Предназначаются для выполнения необходимых вычислений, состоят из констант, переменных, указателей функций, объединенных знаками операций.
Выражения записываются в виде линейных последовательностей символов (без подстрочных и надстрочных символов, "многоэтажных" дробей и т.д.), что позволяет вводить их в компьютер, последовательно нажимая на соответствующие клавиши клавиатуры.
Операторы (команды) - Текст любой программы состоит из отдельных предложений. Обычно они называются операторами. Оператор содержит имя и данные и указывает, какую операцию и над какими величинами следует выполнить. Одна строка программы может содержать один или несколько операторов. В состав операторов входят:
- ключевые слова,-данные,- выражения и т.д.
Функции - Для наиболее употребительных функций программы их вычисления записаны в память компьютера , в библиотеки программ, а сами функции включены в состав языков программирования. Такие функции называются встроенными (или стандартными). Для вычисления таких функций в программе достаточно указать имя функции и значение ее аргумента
3. Условные обозначения в блок-схемах алгоритмов.
Схема алгоритма представляет собой систему связанных геометрических фигур, каждая из которых обозначает один этап процесса решения задачи и называется блоком.
Порядок выполнения блоков указывается стрелками, соединяющими блоки. В схеме блоки размещаются сверху вниз в порядке их выполнения.
| Наименование | Обозначение | Комментарии |
| Процесс | 
| Выполнение операций над данными |
| Решение | 
| Разветвление в алгоритме, проверка условия |
| Данные | 
| Ввод/вывод данных в общем виде |
| Пуск-останов | 
| Начало или конец алгоритма, вход/выход в подпрограмму |
| Документ | 
| Данные, представленные на носителе |
| Типовой процесс | 
| Процесс, сформированный в другом месте (обработка данных в подпрограмме) |
| Дисплей | 
| Вывод данных на дисплей |
4. Этапы решения задач на компьютерах.
Разработка программного комплекса состоит из нескольких этапов:
- постановка задачи;
-проектирование;
- программирование;
-отладка и тестирование;
-создание документации;
-сопровождение.
На этапе постановки задачи формулируются общие требования к программному комплексу. Определяется состав входных и выходных данных а также форма выдачи результатов.
На этапе проектирования осуществляется выбор метода решения задачи, строится математическая модель, производится выбор языка программирования, определяются структуры данных и разрабатываются алгоритмы решения задач.
На этапе программирования (кодирования) пишутся программы. В процессе программирования проводится поэтапная отладка программы, при которой разработчик последовательно исправляет ошибки программного кода.
После того как программа написана, проводится проверка правильности и надежностиработы программы в различных условиях. Этот процесс называется тестированием.
Используются несколько специальных терминов, описывающих различные способы тестирования . Если разработчик теста имеет доступ к исходному тесту программы, то такое тестирование называется тестированием "белого ящика", если не имеет, то тестирование называется тестированием "черного ящика".
"Альфа" - и "Бета"- тестированиепроводятся в реальных производственных условиях. Сначала проводится "Альфа"- тестирование.
Этим тестированием занимаются разработчики. Затем программный комплекс сдается в опытную эксплуатацию и тестированием начинают заниматься реальные пользователи ("Бета"-тестирование).
В ходе опытной, а затем и промышленной эксплуатации выявляются не только ошибки программы, но и ошибки в описании общих требований к системе. Программисты исправляют ошибки и дорабатывают программный комплекс. Этот процесс называется сопровождением.
Тестирование, при котором проверяется, как внесенные изменения повлияли на функциональность предыдущей версии программы, называетсярегрессионным тестированием.
5. Принципы проектирования комплексов программ.
Имеются два способа проектирования комплексов программ.
1 способ. - проектирование сверху-вниз. Этот способ основан на принципах системного подхода, при котором одна большая задача разбиваются на составляющие подзадачи, каждая из которых в свою очередь также может быть разбита на подзадачи. Связи между подзадачами устанавливаются на уровне данных. Такой подход к созданию программных комплексов носит название структурного программирования, при котором имеется возможность организации совместной работы коллектива программистов.
2 способ. - проектированиеснизу-вверх.Этот способ предназначендля индивидуальной работы программиста. В этом случае постепенно, шаг за шагом, разрабатываются отдельные модули программного комплекса и наращиваются его функции.
6. Интегрированные среды программирования.
Интегрированные среды программирования предназначены для написания и отладки программ. Создание программы включает несколько этапов: написание текста, трансляция и компоновка.
Текстовый редактор.Программы, написанные на языке высокого уровня, представляют собой обычный текст, поэтому они могут быть набраны в любом текстовом редакторе. Однако , системы программирования часто содержат собственный текстовый редактор, содержащий ряд дополнительных функциональных возможностей. Например, редактор имеет систему встроенных подсказок для написания ключевых слов.
Трансляция.Способ преобразования исходного текста программы,написанного на языке высокого уровня, в язык машинных кодов (объектный код). В процессе трансляции проводится лексический, синтаксический и семантический анализ текста программы. Если в программе имеются ошибки, то система программирования выдает соответствующие сообщения.
На этапе лексического анализа производится выделение из исходного текста отдельных слов и символов языка и их проверка. Определяются ключевые слова, имена объектов и данных, удаляются лишние пробелы и комментарии.
На этапе синтаксического анализа проверяется возможность получения правильной грамматической фразы исходного языка.
На этапе семантического анализа производится проверка типов данных.
Существуют два способа трансляции: с помощью компиляторов и с помощью интерпретаторов.
Интерпретация. Отдельные операторы программы последовательно переводятся в язык машинных кодов, после чего они сразу же выполняются. При интерпретации легче проводить отладку программы.
Компиляция. Сначала осуществляется перевод всего исходного текста программы в язык машинных кодов, а затем начинается процесс выполнения программы. результатом работы компилятора является загрузочный модуль.
Компоновка. Для создания сложных программных комплексов, состоящих из нескольких модулей, объектные модули объединяются в загрузочный модуль с помощью компоновщика (редактора связей или линковщика).
7. Структурное программирования.
Структурный подход заключается в возможности разбиения основной программы на отдельные фрагменты (подпрограммы) и организации совместного использования данных.
Подпрограммой называется фрагмент программы, имеющий имя и предназначенный для решения определенной задачи.
В программах и подпрограммах применяются базовые управляющие конструкции алгоритмического языка, имеющие одну точку входа и одну точку выхода (следование, ветвление, цикл).
Основная программа в зависимости от сложности может состоять из одной и более подпрограмм. Одна подпрограмма может вызывать другую. Для обращения к подпрограмме достаточно указать ее имя и список аргументов.
Программы и подпрограммы хранятся в модулях. В один модуль помещается несколько программ и подпрограмм, которые имеют относительную независимость от программ, хранящихся в других модулях, и реализуют какую-либо задачу. Каждый модуль транслируются отдельно, а затем используется при формировании общего исполняемого модуля.
Основным преимуществом использования модульного принципа программирования является возможность отладки и тестирования модуля независимо от других модулей.
Взаимодействие подпрограмм происходит с помощью обмена данными.
Существуют два способа обмена данными между подпрограммами: с помощью глобальных переменных и с помощью передачи параметров.
Переменные, объявленные в подпрограмме , являются локальными. Это значит, что использовать значения этих переменных можно только внутри этой подпрограммы.
Переменные, объявленные в разделе общего описания модуля, являются глобальными.Доступ к глобальным переменным имеется во всехподпрограммах модуля.
При обмене данными между подпрограммами выделяются два момента:
описание подпрограмм и обращение к ним (вызов).
При обмене данными с помощью передачи параметров необходимо при вызове подпрограммы, кроме ее имени указать перечень передаваемых параметров, которые называются фактическими параметрами, а при описании подпрограммы указать перечень принимаемых параметров, которые называются формальными параметрами.
Фактические параметры должны соответствовать формальным параметрам по количеству, порядку перечисления и типу.
Функции являются расширением подпрограмм. Функции могут делать все, что могут делать подпрограммы, и вдобавок они возвращают какое-то значение. Подпрограммы и функции могут вызывать сами себя. В этом случае они называются рекурсивными функциями, или подпрограммами.
8. Объектно-ориентированное программирование.
Объектный подход является следующей ступенью в развитии структурного программирования. В основе его лежит идея объединения в одной структуре, называемой объектом, данных и программ, которые обрабатывают эти данные.
Понятие объекта включает в себя параметры объекта (свойства) и программные средства для работы с ним (методы). По существу каждый объект представляет собой программный комплекс. Данные этой программы называются свойствами, а отдельные подпрограммы обработки данных называются методами.
В объектно-ориентированном программировании используется определенная форма записи при работе с объектами. Объекты одного и того же типа объединяются в классы.Классы, участвующие в определении нового класса, называются базовыми или родительскими, а создаваемые классы - производными. В общем виде совокупность классов может представлять собой иерархическую структуру.
События- сигналы, формируемые пользователем или программой, для которых объект имеет свои методы обработки.
В основе объектно-ориентированного программирования лежат три важных понятия: инкапсуляция, наследование и полиморфизм.
Инкапсуляция - позволяет объединить данные и код в один объект и при этом скрыть реализацию объекта от пользователя. Пользователю предоставляется возможность взаимодействовать с объектом только через его интерфейс.
Наследование - способность описать новый класс на основе уже существующего (родительского). При этом свойства и функциональность родительского класса заимствуются новым классом.
Полиморфизм - возможность по разному трактовать одноименные объекты, их свойства и методы в зависимости от каких-то внешних обстоятельств. Полиморфизм позволяет писать более абстрактные программы и повысить коэффициент повторного использования кода.
Дата добавления: 2018-08-06; просмотров: 341; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!