Информатика / Тема-3_Лк-4_1

1 АЛГОРИТМЫ И АЛГОРИТМИЗАЦИЯ

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) и др. В этих языках алгоритмы записываются в форме, близкой к математике.

Программы, написанные на машинно-независимом языке, обязательно должны быть переведены самой ЭВМ на машинный язык (язык, “понятный” ЭВМ) с помощью специальных систем – трансляторов.

Язык программирования - язык, используемый для формальной записи алгоритмов.

Большинство языков программирования относятся к алгоритмическим языкам.

Программа - это запись алгоритма на языке программирования.

Язык, используемый для формальной записи алгоритмов, называется алгоритмическим языком. При описании любого языка (в том числе естественного, например, русского, английского и т.д.) используются следующие понятия: алфавит, синтаксис и семантика.

Алфавит языка - это множество простейших знаков, которые могут быть использованы в текстах этого языка.

Последовательность символов алфавита называют словом. Правила, согласно которым образуются слова из алфавита, называются грамматикой. Сам же язык - это множество всех слов, записываемых в данном алфавите согласно данной грамматике.

Синтаксис - это набор правил, определяющих возможные сочетания (конструкции) из букв алфавита.

Для описания синтаксиса языка, как правило, используют другой язык (метаязык) или синтаксические диаграммы.

Семантика - набор правил, определяющих значение (смысл) отдельных конструкций языка.