Тема-3_Лк-4_1
.pdf1 АЛГОРИТМЫ И АЛГОРИТМИЗАЦИЯ
1.1Понятие алгоритма
1.2Способы записи алгоритма
1.3Типовые структуры алгоритмов
2 Языки программирования
2.1Системы программирования
2.2Основные понятия и термины
2.3Технологии и языки программирования
2.4Объектно-ориентированное программирование
1.1 Понятие алг оритма (1)
Решение любой задачи предполагает выполнение исполнителем последовательности некоторых действий.
Определение действий и последовательности их выполнения широко используется при планировании. Примерами являются планы мероприятий, бизнес-планы и т.п.
Алгоритм является фундаментальным понятием информатики.
Алгоритм - это предписание исполнителю (человеку или автомату) выполнить точно определенную последовательность действий, направленных на достижение заданной цели.
Алгоритм - это сформулированная на некотором языке система правил, указывающих на действия, последовательное выполнение которых приводит от исходных данных к искомому результату. Значение слова алгоритм очень схоже со значением слов рецепт, процесс, метод, способ.
1.1 Понятие алгоритма (2)
СВОЙСТВА АЛГОРИТМА 1. Дискретность - разбиение алгоритма на ряд отдельных
законченных действий - шагов.
Выполнение алгоритма разбивается на последовательность законченных действий - шагов. Каждое действие должно быть закончено исполнителем алгоритма прежде, чем он приступит к исполнению следующего действия.
2. Точность - однозначные указания.
На каждом шаге однозначно определено преобразование объектов среды исполнителя, полученной на предыдущих шагах алгоритма.
Если алгоритм многократно применяется к одному и тому же набору исходных данных, то на выходе он получает каждый раз один и тот же результат. Запись алгоритма должна быть такой, чтобы на каждом шаге его выполнения было известно, какую команду надо выполнять следующей.
3. Понятность - однозначное понимание и исполнение каждого шага
алгоритма его исполнителем.
Алгоритм должен быть записан на понятном для исполнителя языке.
4. Результативность - обязательное получение результата за конечное
число шагов.
Каждый шаг (и алгоритм в целом) после своего завершения дает среду, в которой все объекты однозначно определены. Если это по каким-либо причинам невозможно, то алгоритм должен сообщать, что решение задачи не существует. Работа алгоритма должна быть завершена за конечное число шагов. Информатика оперирует только с конечными объектами и конечными процессами, поэтому вопрос о рассмотрении бесконечных алгоритмов остается за рамками теории алгоритмов.
5. Массовость - применение алгоритма к решению целого класса однотипных задач.
1.1 Понятие алгоритма (3)
АЛГОРИТМ И ИСПОЛНИТЕЛЬ
Любой алгоритм должен быть предназначен для определенного исполнителя.
В качестве исполнителя может выступать человек, автоматическое устройство.
Часто в качестве исполнителя выделяют язык программирования.
Система команд исполнителя - точно описанная обстановка, включающая:
●формулировку решаемой задачи,
●перечень объектов, вовлекаемых в условие задачи и в ее решение,
●возможности исполнителя: свойства объектов, которые он может узнать и действия, которые он может совершить.
Формальное исполнение алгоритма производит компилятор или интепретатор, проверяя семантику.
Пример. Алгоритм вычисления корней квадратного уравнения ax2 bx c=0 .
1.Вычислить дискриминант D=b2−4ac .
2.Если D 0 ,
то x1=(−b D)/2a, x2=(−b− D)/2a,
иначе
если D=0 , то x=−b/2a,
иначе «Нет корней».
1.2 Способы записи алг оритма (1 )
Словесная запись - описание на естественном языке последовательных этапов обработки данных. Такие описания строго не формализуемы, допускают неоднозначность толкования отдельных предписаний.
Графическая запись (блок-схемы) - изображение алгоритма в виде последовательности связанных между собой функциональных блоков, каждый из которых соответствует выполнению одного или нескольких действий.
Псевдокоды - полуформализованное описание на условном алгоритмическом языке, включающее как основные элементы языка программирования, так и фразы естественного языка, общепринятые математические обозначения и другие.
Языки программирования.
1.2 Способы записи алг оритма (2 )
Основные функциональные элементы блок-схем алгоритмов
Начало
/конец
алгоритма
Процесс <Действие>
Ввод/вывод с неопределенного носителя
Ввод с клавиатуры
Вывод на монитор
Вывод на печать
Нет |
Да |
Проверка |
|
|
|
|
|
условия |
Цикл с параметром
<Тело цикла>
Цикл с
<Тело цикла> предусловием Цикл с
постусловием
А |
2 |
Соединитель- |
ные блоки |
Структурный подход к разработке алгоритмов определяет использование только базовых алгоритмических структур (конструкций): следование, ветвление, повторение, которые обеспечивают выполнение базовых команд и должны быть оформлены стандартным образом.
1.3 Типовые структуры алгоритмов (1)
Блок имеет один вход и один выход. Из простых команд и проверки условий образуют составные команды, имеющие более сложную структуру и тоже один вход и один выход.
Команда повторения - это составная команда алгоритма, в которой в зависимости от условия Р возможно многократное выполнение действия S.
Команда повторения с предусловием.
Вначале проверяется условие, а уже затем выполняется действие.
На рисунке: действие выполняется до тех пор, пока условие соблюдается.
Команда следования состоит только из простых команд. На рисунке простые команды имеют условное обозначение S1 и S2. Из команд следования образуются линейные алгоритмы.
Команда повторения с постусловием: вначале выполняется действие S и лишь затем проверяется условие P.
На рисунке: действие повторяется до тех пор, пока условие не соблюдается.
Команда ветвления полной формы
- это составная команда алгоритма, в которой в зависимости от условия Р выполняется или одно S1, или другое S2 действие.
Из команд следования и команд ветвления составляются разветвляющиеся алгоритмы (алгоритмы ветвления).
Команда ветвления неполной формы. Неполная форма команды ветвления используется тогда, когда необходимо выполнять действие S только в случае соблюдения условия P. Если условие P не соблюдается, то команда ветвления завершает свою работу без выполнения действия.
k=1,10,2 |
S |
Команда повторения с параметром
- это составная команда алгоритма, в которой в зависимости от условия Р возможно многократное выполнение действия S. Используется в случае, когда количество повторений действия S известно наперед.
На схеме показан пример условия Р: переменная k принимает значения от 1 до 10 с шагом 2.
1.3Типовые структуры алгоритмов (2)
Спомощью соединения только элементарных конструкций (последовательно или вложением) можно собрать алгоритм любой степени
сложности.
2 .1 Системы программирования
Тексты программ создают разработчики.
Для выполнения программы на компьютере необходимо преобразовать
текст программы в машинный код.
Два различных варианта реализации такого преобразования:
1) Очередная команда программы преобразуется в машинный код и передается на исполнение в вычислительное устройство. Выполняет преобразование программа-
интерпретатор.
2) Программа-компилятор обрабатывает весь текст исходного кода, выявляет синтаксические ошибки, выполняет семантический анализ и затем генерирует объектный код. Объектный код обрабатывается редактором связей, формируется исполнимый код (файл с расширением .exe), который можно сохранить и использовать под управлением операционной системы на любых компьютерах с процессорами, поддерживающими соответствующий машинный код.
Совокупность программных средств, которые обеспечивают выполнение перечисленных действий, называют системой программирования. В состав системы программирования входят:
·текстовый редактор;
·компилятор;
·редактор связей;
·отладчик;
·библиотеки функций;
·справочная система.
2 .2 Основные понятия и термины
Программы можно писать непосредственно в машинных кодах. Однако это крайне нетехнологично. Для разработки программ используют специальные языки программирования.
Языки программирования можно разделить на два основных класса:
1. Машинно-зависимые (машинно-ориентированные) языки, которые можно использовать на одной ЭВМ или на некотором множестве ЭВМ с одинаковой архитектурой.
Команды этих языков позволяют распределять память, выполнять простейшие арифметические операции и простейшие операции обработки информации, при этом происходит непосредственноеобращение к адресам оперативного запоминающего устройства (ОЗУ). Программы, написанные на машинно-зависимом языке довольно громоздки, но достаточно эффективны.
2. Машинно-независимые языки, к которым относятся языки высокого уровня, такие как Pascal, С/C++, Visual Basic(VB) и др. В этих языках алгоритмы записываются в форме, близкой к математике.
Программы, написанные на машинно-независимом языке, обязательно должны быть переведены самой ЭВМ на машинный язык (язык, “понятный” ЭВМ) с помощью специальных систем – трансляторов.
Язык программирования - язык, используемый для формальной записи алгоритмов.
Большинство языков программирования относятся к алгоритмическим языкам.
Программа - это запись алгоритма на языке программирования.
Язык, используемый для формальной записи алгоритмов, называется алгоритмическим языком. При описании любого языка (в том числе естественного, например, русского, английского и т.д.) используются следующие понятия: алфавит, синтаксис и семантика.
Алфавит языка - это множество простейших знаков, которые могут быть использованы в текстах этого языка.
Последовательность символов алфавита называют словом. Правила, согласно которым образуются слова из алфавита, называются грамматикой. Сам же язык - это множество всех слов, записываемых в данном алфавите согласно данной грамматике.
Синтаксис - это набор правил, определяющих возможные сочетания (конструкции) из букв алфавита.
Для описания синтаксиса языка, как правило, используют другой язык (метаязык) или синтаксические диаграммы.
Семантика - набор правил, определяющих значение (смысл) отдельных конструкций языка.