Лекция № 3 Основы алгоритмизации и программирования Основные понятия

1. Лекция № 3 Алгоритм. Языки программирования. Основные алгоритмические конструкции

2. Алгоритм

точно определенная система
предписаний исполнителю, формальное
выполнение которых позволяет получить
решение задачи для любого допустимого
набора исходных данных за конечное
число шагов

3. Свойства алгоритма

Дискретность
Детерминированность
Свойства
алгоритма
Понятность
Результативность
Конечность
Массовость

4. Дискретность

◦ Выполнение алгоритма разбивается
на отдельные действия (шаги).
◦ Выполнение очередного действия
возможно только после завершения
предыдущего.
◦ При этом набор промежуточных
данных конечен и получается по
определенным правилам из данных
предыдущего действия.

5. Детерминированность

◦ Если алгоритм неоднократно применить
к одним и тем же исходным данных, то
каждый раз должны получаться одни и те
же промежуточные результаты, и один и
тот же выходной результат.
◦ Данное свойство означает, что результат
выполнения алгоритма определяется
только входными данными и командами
самого алгоритма и не зависит от
исполнителя алгоритма

6. Понятность

◦ Алгоритм не должен содержать
команд, смысл которых исполнитель
может воспринимать неоднозначно.
◦ Запись алгоритма должна быть
четкой, полной и понятной.
◦ У исполнителя не должна возникать
необходимость в принятии какихлибо самостоятельный решений.

7. Результативность

◦ При точном выполнении команд
алгоритма в результате должен быть
получен ответ на вопрос задачи.
◦ Если способ получения последующих
величин из каких-либо исходных не
приводит к результату, то должно быть
указано, что следует считать результатом
исполнения алгоритма.
◦ В качестве одного из возможных ответов
может быть установление того факта, что
задача не имеет решения.

8. Конечность

◦ Реализуемый по заданному
алгоритму процесс должен
остановиться через конечное число
шагов и выдать искомый результат.
◦ Это свойство тесно связано со
свойством результативности.

9. Массовость

Алгоритм пригоден для решения любой
задачи из некоторого класса задач, т.е.
начальная система величин может
выбираться из некоторого множества
исходных данных, которое называется
областью применимости алгоритма

10. Формы записи алгоритма

◦ текстовое описание
◦ блок-схема
◦ запись в виде программы на
языке программирования
◦ др.

11. Базовые алгоритмические конструкции

Команда 1
I=1..N
Команда 2
Команда(ы)
Базовые
алгоритмические
конструкции
◦ Следование
◦ Цикл
◦ Ветвление
Да
Команда(ы) 1
Условие
Нет
Команда(ы) 2
Да
Команда(ы)
Условие
Нет

12. Основные алгоритмические структуры

МК
Основные алгоритмические структуры
Вне зависимости от выбранной формы записи элементарные шаги
алгоритма объединяются в алгоритмические конструкции (структуры):
ПОСЛЕДОВАТЕЛЬНЫЕ
ВЕТВЯЩИЕСЯ
АЛГОРИТМИЧЕСКИЕ
СТРУКТУРЫ
ЦИКЛИЧЕСКИЕ
РЕКУРСИВНЫЕ
Для записи любого алгоритма достаточно трёх основных алгоритмических
структур: последовательной, ветвящейся, циклической.

13. Последовательная алгоритмическая конструкция

МК
Последовательная алгоритмическая конструкция
!
Алгоритм реализован через последовательную алгоритмическую
конструкцию, если все команды алгоритма выполняются один раз,
причём в том порядке, в котором они записаны в тексте
программы.
Пример 1. Алгоритм представлен блок-схемой.
Выясните, какую задачу решает этот алгоритм.
Чему равен результат работы алгоритма при х = 2.
X
REZ := X * X
Решение:
Ответ:Решение
512
Начало
№
REZ
1
X2
2
X4
3
X8
4
X9
REZ := REZ * REZ
REZ := REZ * REZ
REZ := REZ * X
REZ
Конец

14. Ветвящаяся алгоритмическая конструкция

МК
Ветвящаяся алгоритмическая конструкция
!
Алгоритм реализован через ветвящуюся алгоритмическую
конструкцию, если от входных данных зависит, какие команды
алгоритма будут выполняться.
Пример 2. Алгоритм представлен блоксхемой. Выясните, какую задачу решает
этот алгоритм. Найдите значение
переменной Y при: 1) х = –10;
2) х = 2;
3) х = 10.
Начало
X
Да
X<1
Y := –X
Да
Y := –1
X<4
Нет
Y := X – 5
Y
Конец
Ответ: 1) 10; 2)–1; 3) 5
Ответ

15. Циклическая алгоритмическая конструкция

МК
Циклическая алгоритмическая конструкция
!
Алгоритм
реализован
с
использованием
циклической
алгоритмической конструкции, если некая группа подряд идущих
шагов алгоритма может выполняться многократно в зависимости
от входных данных.
Цикл с предусловием
(цикл-пока)
Условие
Да
Тело цикла
Цикл с постусловием
(цикл-до)
Нет
Тело цикла
Нет
Цикл с параметром
Параметр =
НЗ, КЗ
Тело цикла
Условие
Да
Последовательность команд, повторяющуюся при выполнении цикла,
называют телом цикла.

16.

МК
Самое главное
Вне зависимости от выбранной формы записи элементарные шаги алгоритма объединяются в
алгоритмические конструкции (структуры): последовательные, ветвящиеся, циклические,
вспомогательные и рекурсивные. Для записи любого алгоритма достаточно трёх основных
алгоритмических структур: последовательной, ветвящейся, циклической.
Алгоритм реализован через последовательную алгоритмическую конструкцию, если все команды
алгоритма выполняется один раз, причём в том порядке, в котором они записаны в тексте
программы.
Алгоритм реализован через ветвящуюся алгоритмическую конструкцию, если от входных данных
зависит, какие команды алгоритма будут выполняться.
Алгоритм реализован с использованием циклической алгоритмической конструкции, если некая
группа подряд идущих шагов алгоритма может выполняться многократно в зависимости от входных
данных.

17. Алгоритм и язык программирования

◦ Любой алгоритм рассчитан на конкретного
исполнителя.
◦ Алгоритм для компьютера должен быть
записан с помощью элементарных команд,
которые компьютер может выполнять.
◦ Элементарными следует считать действия
процессора, которые называют машинными
командами, а их обозначения – машинными
кодами
◦ В языках программирования высокого уровня
используются команды, которые объединяют
последовательности машинных команд

18. Транслятор

◦ Для преобразования текста
программы, написанной на языке
высокого уровня, в элементарные
машинные команды используются
специальные программы –
трансляторы
◦ Различают следующие виды
трансляции: компиляция и
интерпретация

19. Настройки Компилятора

20. Парадигмы программирования

◦ Структурное программирование
◦ Процедурное программирование
◦ Объектно-ориентированное
программирование
◦ Функциональное программирование
◦ Логическое программирование
◦ Др.

21. Особенные языки программирования

Hexagony
Hexagony
—
первый
язык,
где
инструкции
расположены
внутри
шестиугольной
сетки.
Название
происходит
от
слов
«hexagon»
(шестиугольник) и «agony» (агония),
потому что программирование будет
сложным.
Особенные языки
программирования
◦ Мультипарадигменные
◦ Учебные
◦ Эзотерические
Hello, world!
◦ Псевдокод

22. Язык программирования

◦ Языки программирования высокого уровня
являются формальными языками – это
искусственные языки со строгим синтаксисом и
однозначным толкованием конструкций
◦ У каждого языка программирования можно
выделить две составляющие: синтаксис и
семантику

23. Структурные элементы языка программирования

Язык
программирования
◦ Алфавит
◦ Данные
◦ Операции и выражения
Алфавит
языка
Организация
действий
Данные
Ввод данных
Обработка
данных
Вывод
данных
◦ Операторы
◦ Подпрограммы
Операции и
выражения
Операторы
Подпрограммы

24. Типы данных

Знаковые
Целочисленные
Беззнаковые
Порядковые
Логические
Вещественные
Символьные
Типы данных
Простые
Строки
Структурированные
Массивы

25. Операторы

оператор присваивания
оператор условного
перехода (ветвления)
оператор цикла
Операторы
пустой оператор
составной оператор
оператор выбора

26. Операторы (оператор цикла)

PascalABC
for var i := 1 to n do
s := s + i * i;
Python
for i in range(n + 1):
s += i * i
C++
for (int i = 1; i <= n; i++)
s += i * i;
Операторы
(оператор
цикла)

27. Язык программирования

◦ Язык программирования – это инструмент
для решения конкретной задачи.
◦ Не существует единственного самого лучшего
языка программирования.
◦ Для решения задач разного рода и уровня
сложности требуется применять разные языки
и технологии программирования.
◦ В простейших случаях достаточно освоить
основы структурного написания программ,
например, на языке PascalABC.
◦ Для создания же сложных проектов требуется
не только свободно владеть каким-то языком
в полном объеме, но и иметь представление о
других языках и их возможностях.

28.

29. Инструментарий технологии программирования: для создания отдельных приложений (программ)

30.

31. Языки программирования

Язык программирования — это формализованный язык для
описания алгоритма решения задач на компьютере. Языки
программирования
можно
условно
разделить
на
следующие классы:

машинные языки — это языки, воспринимаемые
аппаратной частью компьютера (машинные коды);

машинно-ориентированные языки, отражающие
структуру конкретного типа компьютера (ассемблер);
• процедурно-ориентированные языки — это языки, в
которых имеется возможность описания программы как
совокупности процедур, или подпрограмм (Си, Паскаль
и др.);

проблемно-ориентированные
языки,
предназначенные для решения задач определенного
класса (ЛИСП, ПРОЛОГ).

32. Системы программирования

Системы программирования включают:
Компилятор (транслятор);
Интегрированную среду разработки программ (не
всегда);
Отладчик;
Средства оптимизации кода программ;
Набор библиотек;
Редактор связей;
Сервисные средства (утилиты) (для работы с
библиотеками, текстовыми и двоичными файлами);
Справочные системы;
Систему поддержки и управления продуктами
программного комплекса.

33. Инструментальная среда пользователя

Инструментальная среда пользователя — это специальные
средства, встроенные в пакеты прикладных программ, такие
как:
Библиотека
обработки;
функций,
процедур,
объектов
Макрокоманды;
Клавишные макросы;
Языковые макросы;
Конструкторы экранных форм и объектов;
Генераторы приложений;
Языки запросов высокого уровня;
Конструкторы меню и др.
и
методов

34. CASE-технология

Интегрированные среды разработки программ объединяют набор
средств для их комплексного применения на технологических
этапах создания программы.
Средства для создания информационных систем (ИС) и технологий
поддерживают
полный
цикл
проектирования
сложной
информационной системы или технологии от исследования
объекта автоматизации до оформления проектной и прочей
документации на информационную систему или технологию. Они
позволяют вести коллективную работу над проектом за счет
возможности работы в локальной сети, экспорта-импорта любых
фрагментов проекта, организации управления проектом.
Одним из современных средств разработки ИС является CASEтехнология (CASE — Computer-Aided System Engineering) —
программный комплекс, автоматизирующий весь технологический
процесс анализа, проектирования, разработки и сопровождения
сложных программных систем.

35. Средства CASE-технологий делятся:

На встроенные в систему реализации — все решения по
проектированию и реализации привязки к выбранной СУБД;
Независимые от системы реализации — все решения по
проектированию ориентированы на унификацию
(определение) начальных этапов жизненного цикла
программы и средств их документирования, обеспечивают
большую гибкость в выборе средств реализации.

36. Вопросы и задания

МК
Вопросы и задания
Задание 1-А. У исполнителя Вычислитель три команды:
прибавь 1 – увеличивает число на экране на 1;
умножь на 2 – удваивает число;
умножь на 3 – утраивает число.
Сколько существует различных программ, которые число 1 преобразуют в
число 12?
Решение (один из способов оформления):
1
2
3
4
5
6
7
8
9
10
11
12
+1
1
2
3
5
5
10
10
15
18
23
23
×2
1
×3
Всего
Ответ: 38
2
3
1
1
2
3
5
2
5
5
10
5
10
3
10
Решение
15
18
5
23
23
Ответ
38

37. Вопросы и задания

МК
Вопросы и задания
Задание 1-Б. У исполнителя Вычислитель три команды:
прибавь 1 – увеличивает число на экране на 1;
умножь на 2 – удваивает число;
умножь на 3 – утраивает число.
Сколько существует различных программ, которые число 1 преобразуют в
число 12 и при этом траектория вычислений содержит число 6?
Решение (основа – решение задачи 1-А):
1
2
3
4
5
6
7
8
9
10
11
12
+1
1
2
3
5
5
10
10
10
10
10
10
×2
1
×3
Всего
Ответ: 20
2
3
1
1
2
3
–
2
5
5
10
–
10
–
10
10
10
–
10
10
20

38. Вопросы и задания

МК
Вопросы и задания
Задание 1-В. У исполнителя Вычислитель три команды:
прибавь 1 – увеличивает число на экране на 1;
умножь на 2 – удваивает число;
умножь на 3 – утраивает число.
Сколько существует различных программ, которые число 1 преобразуют в
число 12 и при этом траектория вычислений НЕ содержит число 4?
Решение (основа – решение задачи 1-А):
1
2
3
+1
1
2
×2
1
×3
Всего
Ответ: 13
4
5
6
7
8
9
10
11
12
0
0
5
5
5
8
8
8
3
1
1
2
3
0
2
0
0
5
0
5
3
5
5
8
0
8
8
13

39. Вопросы и задания

МК
Вопросы и задания
Задание 2. Исполнитель Редактор получает на вход строку цифр и
преобразует её. Редактор может выполнять две команды:
• нашлось (v) – проверяет, встречается ли цепочка v в строке;
• заменить (v, w) – заменяет в строке первое слева вхождение цепочки
v на цепочку w.
Какая строка получится в реДана программа для исполнителя:
зультате применения программы
НАЧАЛО
к строке, состоящей из:
ПОКА нашлось (444) ИЛИ нашлось (22)
ЕСЛИ нашлось (444)
А) 303 идущих подряд цифр 2;
ТО заменить (444, 2)
Решение
ИНАЧЕ заменить (22, 4)
КОНЕЦ ЕСЛИ
Б) 303 идущих подряд цифр 4.
КОНЕЦ ПОКА
Решение
КОНЕЦ

40. Вопросы и задания

МК
Вопросы и задания
Задание 3. Автомат по
продаже
напитков
имеет
только две кнопки (A и B), но
должен продавать 4 напитка:
горячий кофе, горячий чай,
яблочный сок и лимонад.
Исследуйте работу автомата.
Представьте в форме блоксхемы алгоритм его работы.
A
B
Начало
Да
Да
Лимонад
А
А
Нет
Нет
Да
Сок
Чай
А
Нет
Кофе
Ответ
Конец