Алгоритмы и основы программирования

1. Алгоритмы

АЛГОРИТМЫ
Лекция №1

2. Содержание курса

СОДЕРЖАНИЕ КУРСА
Название курса – ОСНОВЫ ПРОГРАММИРОВАНИЯ
❖Лекции – 34 ч (каждую неделю)
❖Практики – 34 ч (каждую неделю)
❖Лабораторные – 34 ч (каждую неделю)
❖РГР – 1 (самостоятельная работа студента, ее защита)
❖Экзамен

3. Цели и задачи дисциплины

ЦЕЛИ И ЗАДАЧИ
ДИСЦИПЛИНЫ
Знакомство с основными методами алгоритмизации,
Получить навыки программирования,
Формирование алгоритмического мышления,
Научиться использовать готовые алгоритмы для решения задач и
самостоятельно разрабатывать новые алгоритмы.
Знакомство со внутренним
Алгоритмическое мышление – это
представлением данных;
•Искусство размышлять,
Изучение основных структур данных;
•Умение планировать свои действия,
Изучение стандартных алгоритмов
•Использовать и разрабатывать
обработки данных;
алгоритмы,
•Способность предусматривать
Изучение принципов структурного
различные обстоятельства и поступать
программирования.
соответственно с ними.

4. Зачем изучать алгоритмы?

ЗАЧЕМ ИЗУЧАТЬ
АЛГОРИТМЫ?
Стандартный набор
алгоритмов,
разработка новых
алгоритмов,
анализ эффективности
алгоритмов
Основы информатики

5. Дональд Кнут- преподаватель и идеолог программирования говорил:

ДОНАЛЬД КНУТ- ПРЕПОДАВАТЕЛЬ И ИДЕОЛОГ
ПРОГРАММИРОВАНИЯ ГОВОРИЛ:
«Хорошо обученный в области информатики специалист обязан
знать, как работать с алгоритмами: как их создавать, изменять,
понимать и анализировать. Эти знания позволят не только писать
хорошие компьютерные программы, но и станут основой
универсального мыслительного аппарата, который окажет
неоценимую помощь при постижении других наук, будь то химия,
лингвистика, музыка и т.д. Причину этого можно объяснить
следующим образом: часто говорят, что человек ничего не понимает,
пока не объяснит это кому-либо другому. Я бы перефразировал это
так: человек глубоко не понимает предмет до тех пор, пока не научит
этому компьютер, т.е. выразит что-либо в виде алгоритма… Попытка
формализовать нечто в виде набора алгоритмов приводит к более
глубокому пониманию сути вещей, чем при их осмыслении
традиционным способом». /Дональд Кнут
Дональд Эрвин Кнут — американский учёный в области информатики, преподаватель и
идеолог программирования, автор 19 монографий (в том числе ряда классических книг по
программированию) и более 160 статей, разработчик нескольких известных программных
технологий. Автор всемирно известной серии книг, посвящённой основным алгоритмам и
методам вычислительной математики.

6. Понятие алгоритма

ПОНЯТИЕ АЛГОРИТМА
Слово "Алгоритм" происходит от algorithmi - латинского
написания имени аль-Хорезми, под которым в средневековой
Европе знали величайшего математика из Хорезма (город в
современном Узбекистане) Мухаммеда бен Мусу, жившего в
783-850 гг. В своей книге "Об индийском счете" он
сформулировал правила записи натуральных чисел с помощью
арабских цифр и правила действий над ними столбиком.
Алгоритм
точное
предписание,
определяющее
последовательность действий, обеспечивающую получение
требуемого результата из исходных данных.

7. Понятие алгоритма

ПОНЯТИЕ АЛГОРИТМА
В программировании
Алгоритм - точное предписание, определяющее
последовательность действий, обеспечивающую
получение требуемого результата из исходных
данных.

8. Исполнитель алгоритма

ИСПОЛНИТЕЛЬ АЛГОРИТМА
Создание алгоритма, пусть даже самого простого, - процесс
творческий. Он доступен исключительно живым существам, а долгое
время считалось, что только человеку.
Другое дело - реализация уже имеющегося алгоритма.
Каждый алгоритм создается в расчете на вполне конкретного
исполнителя.
ИСПОЛНИТЕЛИ
Формальный исполнитель — это
исполнитель, который одну и ту же
команду всегда выполняет
одинаково.
(стиральная машина-автомат,
конвеер на производстве,
различные автоматические
устройства, и компьютер в том
числе)
Неформальный исполнитель —
это исполнитель, который одну
и ту же команду может
выполнять по-разному.
(человек, животное)

9. Разработка алгоритма

РАЗРАБОТКА АЛГОРИТМА
1 шаг. выделяются фигурирующие в задаче объекты, устанавливаются
свойства объектов, отношения между объектами и возможные действия с
объектами;
2 шаг. определяются исходные данные и требуемый результат;
3 шаг. определяется последовательность действий исполнителя,
обеспечивающая переход от исходных данных к результату;
4 шаг. последовательность действий записывается с помощью
команд, входящих в систему команд исполнителя.
Алгоритм — это модель деятельности исполнителя
алгоритмов

10. Правила разработки алгоритма

ПРАВИЛА РАЗРАБОТКИ
АЛГОРИТМА
Первое правило
При построении алгоритма прежде всего необходимо задать
множество объектов, с которыми будет работать алгоритм.
Формализованное ( закодированное ) представление этих объектов
носит название данных.
Алгоритм приступает к работе с некоторым набором данных, которые
называются входными, и в результате своей работы выдает данные,
которые называются выходными.
Таким образом, алгоритм преобразует входные данные в выходные.
Информация
Входные
данные
Выходные
данные
Информация

11. Постановка задачи

ПОСТАНОВКА ЗАДАЧИ
Для того, чтобы составить алгоритм решения задачи, необходимо из
условия выделить те величины, которые будут входными данными и
четко сформулировать, какие именно величины требуется найти.
Другими словами, условие задачи требуется сформулировать в виде
“Дано ... Требуется” – это и есть постановка задачи.
Пример
Улитка ползет по вертикальному шесту высотой H метров,
поднимаясь за день на A метров, а за ночь спускаясь на B
метров. На какой день улитка доползет до вершины шеста?
Входные данные: ?
Выходные данные: ?

12. Правила разработки алгоритма

ПРАВИЛА РАЗРАБОТКИ
АЛГОРИТМА
Второе правило
Для работы алгоритма требуется память.
В памяти размещаются входные данные, с которыми алгоритм
начинает работать, промежуточные данные и выходные данные,
которые являются результатом работы алгоритма.
Память является дискретной, т.е. состоящей из отдельных ячеек.
Поименованная ячейка памяти носит название переменной

13. Правила разработки алгоритма

ПРАВИЛА РАЗРАБОТКИ
АЛГОРИТМА
Третье правило – дискретность. Алгоритм строится из
отдельных шагов (действий, операций, команд). Множество
шагов, из которых составлен алгоритм, конечно.
Четвертое правило – детерменированность.
После каждого шага необходимо указывать, какой шаг
выполняется следующим, либо давать команду остановки.

14. Правила разработки алгоритма

ПРАВИЛА РАЗРАБОТКИ
АЛГОРИТМА
Пятое правило – сходимость ( результативность ).
Алгоритм должен завершать работу после конечного числа
шагов. При этом необходимо указать, что считать
результатом работы алгоритма.

15. Способы описания алгоритмов

СПОСОБЫ ОПИСАНИЯ
АЛГОРИТМОВ
❑Словесное описание
❑Псевдокод
❑Графический способ
❑На алгоритмическом языке

16. Пошаговая запись алгоритма

ПОШАГОВАЯ ЗАПИСЬ
АЛГОРИТМА
Пример
Вход: два натуральных числа, a и b.
Шаг 1. Если a < b, перейти к шагу 4.
Шаг 2. Уменьшить a на величину b.
Шаг 3. Перейти к шагу 1.
Шаг 4. Стоп.
Результат: значение a.
Обратите внимание, что ясно определено, что служит исходными
данными для работы этого алгоритма (см. первую строчку — Вход) и
что будет считаться результатом его работы (строчка Результат).
Подумайте, что вычисляет этот алгоритм и что будет, если
применить его к таким исходным данным: a = 19, b = 5.

17. Псевдокод

ПСЕВДОКОД
Пример
// входные данные: два натуральных числа, a и b.
Пока
a > b
а ← а – b
Return а

18. Графическое описание алгоритма

ГРАФИЧЕСКОЕ ОПИСАНИЕ
АЛГОРИТМА
начало
a, b
a>b
нет
да
a←a-b
a
конец

19. Задание

ЗАДАНИЕ
1) Составьте алгоритм перехода через проезжую часть дороги.
2)

20. Эффективность алгоритма

ЭФФЕКТИВНОСТЬ
АЛГОРИТМА
Задача. Сложить числа 1+2+3++4+…+99+100.
1-ый алгоритм:
2-ой алгоритм:
Последовательным
сложением:
Разбить все числа на пары 1 +
1 + 2 + 3 + 4 + … + 99 +
100 = 5050
100, 2 + 99, … 50 + 51
и все суммы равны 101,
поэтому общий результат равен
50 × 101 = 5050.

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

ЯЗЫКИ ПРОГРАММИРОВАНИЯ
Для того чтобы робот (или другой исполнитель) мог выполнять
алгоритмы автоматически (без участия человека), он должен
уметь работать в программном режиме. Это означает, что
алгоритм нужно записать в память исполнителя на специальном
языке, который он “понимает”. Тогда алгоритм становится
программой.
Программа — это алгоритм, записанный на языке конкретного
исполнителя.

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

ЯЗЫКИ ПРОГРАММИРОВАНИЯ
Программы для компьютеров составляются на специальных языках,
которые называются языками программирования.
Все данные в компьютере хранятся в виде двоичных кодов. Программы
также хранятся в памяти компьютера как двоичные коды. Но это не
значит, что все программы обязательно составляются “на языке нулей и
единиц”. Действительно, любой компьютер (точнее, его процессор)
понимает и умеет выполнять только команды в двоичном коде. Но так
программы никто не пишет, потому что это очень утомительно, отнимает
много времени и приводит к многочисленным ошибкам.

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

ЯЗЫКИ ПРОГРАММИРОВАНИЯ
Ближе всего к родному языку процессора так называемые языки
низкого уровня , или языки ассемблера. В них каждая команда
может быть напрямую переведена в соответствующую команду
процессора.
Например, вот так выглядит программа на языке ассемблера для
самого обычного домашнего компьютера, которая складывает числа
5 и 6:
MOV AX, 5
1011 1000 0000 0101 000 000
MOV BX, 6
1011 1011 0000 0110 000 000
ADD AX, BX
0000 0011 1100 0011
Программу, которая переводит символьную запись команд в цепочки
битов, называют ассемблером (сборщиком). На языке ассемблера
обычно пишут программы, в которых нужно очень высокое
быстродействие и небольшой размер — ядро операционной
системы, драйверы устройств и т.п.

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

ЯЗЫКИ ПРОГРАММИРОВАНИЯ
К сожалению, у каждого семейства процессоров свой язык
ассемблера, поэтому программы, написанные для одного семейства,
не подходят для другого. Чтобы решить эту проблему, разработали
языки высокого уровня, которые приближены к естественному языку
(чаще всего — к английскому). Языки высокого уровня никак не
связаны с компьютером, на котором будут выполняться.
Тогда возникает вопрос — как же разные компьютеры будут
понимать программы на этих языках? Решение было найдено: для
каждого типа процессоров (и операционных систем) создается
транслятор (переводчик) — программа, которая переводит текст
программы, написанной на языке высокого уровня, в двоичные
команды нужного процессора.

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

ЯЗЫКИ
ПРОГРАММИРОВАНИЯ

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

ЯЗЫКИ ПРОГРАММИРОВАНИЯ
1.
Первый язык программирования высокого уровня — Фортран
(1957 год, Джон Бэкус).
2.
Си (в середине 1970-х гг, Деннис Ритчи). На нем написаны
практически все операционные системы (в том числе UNIX,
Windows, Linux). На основе языка Си разработано множество
современных языков С++, C# , Java, Javascript и др.
3.
Python ( 1991 г). Он широко используется в таких известных
компаниях, как Google и Яндекс, применяется для обработки
больших данных и программирования игр.
4.
PHP и Javascript используются для написания
сайтов в Интернете.
5.
Языки Prolog и LISP (1970 гг) - языки для решения задач
искусственного интеллекта.
6.
Языки Basic и Pascal разработаны специально для обучения
программированию.
современных

27. Программа. Этапы разработки программы

ПРОГРАММА. ЭТАПЫ
РАЗРАБОТКИ ПРОГРАММЫ
Работа по решению любой задачи с использованием компьютера
делится на следующие этапы:
1. Определение требований к программе (постановка
задания)
2. Разработка алгоритма
3. Написание команд (кода)
4. Отладка
5. Тестирование.

28. 1. Определение требований к программе

1. ОПРЕДЕЛЕНИЕ ТРЕБОВАНИЙ К
ПРОГРАММЕ
❑Подробно описывается исходная информация и
формулируются требования к результату. Т.е. выполняется
постановка задачи.
❑Кроме того, описывается поведение программы в
особых случаях.
❑Если программа будет работать в Windows, то нужно
разработать диалоговые окна, обеспечивающие
взаимодействие пользователя и программы.

29. 2. Разработка алгоритма

2. РАЗРАБОТКА АЛГОРИТМА
На этапе разработки алгоритма необходимо определить
последовательность действий, которые надо выполнить
для получения результата.
Если задача может быть решена несколькими способами и,
следовательно, возможны различные варианты алгоритма
решения, то программист, определяет эффективность
каждого алгоритма.
Результатом этапа разработки алгоритма является
подробное словесное описание алгоритма или его блоксхема.

30. 3. Кодирование

3. КОДИРОВАНИЕ
После того как определены требования к программе и составлен
алгоритм решения, алгоритм записывается на выбранном языке
программирования.
В результате получается исходная программа.

31. 4. Отладка

4. ОТЛАДКА
Отладка - это процесс поиска и устранения ошибок.
Синтаксические ошибки – нарушение формальных правил
записи на языке программирования. Диагностируются
транслятором.
Семантические ошибки – нарушение правил
интерпретации смыслового значения программы и ее
практической полезности. Выявляются в процессе
тестирования.
Этап отладки можно считать законченным, если
программа работает на одном-двух наборах входных
данных.

32. 5. Тестирование

5. ТЕСТИРОВАНИЕ
На этом этапе следует проверить, как ведет себя программа на как
можно большем количестве входных наборов данных, в том числе и
на заведомо неверных.
Тест – просчитанный вручную или другим способом пример,
результаты которого используются для выявления ошибок и контроля
правильности работы программы.
Комплект тестов должен быть таким, чтобы подвергнуть проверке:
• все ветви алгоритма,
•Все циклические и рекурсивные структуры,
•Все вырожденные и предельные случаи решения.

33. Задание

ЗАДАНИЕ

34. Система тестов для задачи нахождения корней квадратного уравнения ax2 + bx + c = 0.

Тестирование
Система тестов для задачи нахождения корней квадратного
уравнения ax 2 + bx + c = 0.