Лекция 1. Введение в программирования. Алгоритм, виды алгоритмов и их свойства. Ст. преп. А. А. Абдурахманов abba1963 - презентация

1 Лекция 1. Введение в программирования. Алгоритм, виды алгоритмов и их свойства. Ст. преп. А. А. Абдурахманов

2 План лекции 1. Алгоритм и его свойства. Виды алгоритмов. 2. Алгоритмические языки программирования и их классификация. 3. Основные этапы решения задачи на ПЭВМ. Понятия транслятора.

3 Литература 1. Бизли Д. Python. Подробный справочник. – Пер. с англ.-СПб: Символ-Плюс, Сузи Р.А. Язык программирования Python. – Самиздат, Лутц М. Программирование на Python. – Пер. с англ.-СПб: Символ-Плюс, Россум Г. и др. Язык программирования Python. – Самиздат, Чаплыгин А.Н. Учимся программировать вместе с Питоном. - Самиздат (Revision: 170).

4 Алгоритм и ее свойства. Виды алгоритмов Алгоритм – система точных и понятных предписаний (команд, инструкций, директив) о содержании и последовательности выполнения конечного числа действий, необходимых для решения любой задачи данного типа. Понятие алгоритма в информатике является фундаментальным, т. е. таким, которое не определяется через другие, более простые понятия.

5 История термина Современное формальное определение алгоритма было дано в 3050-е годы XX века в работах Тьюринга, Поста, Чёрча (тезис Чёрча Тьюринга), Н. Винера, А. А. Маркова. Само слово «алгоритм» происходит от имени персидского учёного Абу Абдуллах Мухаммеда ибн Муса аль-Хорезми (алгоритм аль-Хорезми). (Аль-Хорезми [имя] + Аритмос [число] алгоритм)

6 История термина Абу Абдулла Мухаммед ибн аль-Хорезми(отец Абдуллы, Мухаммед, сын Мусы, уроженец Хорезма) – арабский математик, астроном и географ IX века.

7 Его труды по арифметике, изложенные в «Книге об индийском счете» привели к грандиозным последствиям в науке вообще и древней математике в частности. Перевод манускрипта начинается словами: «Dixit Algorizmi» - «Сказал Алгорезми», однако, очень скоро имя автора становится нарицательным, а слово «Algorizm», сначала обозначает арифметику, а потом и любую систему вычислений, подчиненную определенному правилу. Так в нашу жизнь пришел «алгоритм», в последствие незаметно перебравшийся из математики в кибернетику.

8 ПРИМЕРЫ АЛГОРИТМОВ: 1. Вычисление периметра многоугольника. Измерить длину всех сторон многоугольника. Найти сумму длин всех сторон многоугольника. 2. Вычисление площади прямоугольника. Измерить длины сторон a и b. Найти произведение длин сторон прямоугольника. Что такое алгоритм?

9 Для одной задачи можно составить несколько вариантов решения (алгоритмов действий). Задача. Саша купил 3 альбома по 30 рублей и 3 набора карандашей за 20 рублей. Сколько стоит вся покупка? Вариант 1. 1)Найти отдельно стоимость альбомов и стоимость карандашей. 2)Найти стоимость всей покупки. Вариант Найти сумму одного альбома и карандаша. 2. Умножить сумму на количество Что такое алгоритм?

10 Задача. Саша купил 3 альбома по 30 рублей и 3 набора карандашей за 20 рублей. Сколько стоит вся покупка? Вариант Умножить стоимость одного набора карандашей на количество наборов. 2. Умножить цену 1 альбома на количество альбомов. 3. Найти сумму полученных произведений. Несущественные отличия: цвет, размер символов, количество действий. Существенные отличия: во втором и в третьем варианте инструкции четкие и конкретные. Что такое алгоритм?

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

12 Дискретностьуказывает, что любой алгоритм должен состоять из конкретных действий, следующих в определенном порядке. Образованная структура алгоритма оказывается дискретной: только выполнив одну команду, исполнитель сможет приступить к выполнению следующей. Детерминированностьуказывает, что любое действие алгоритма должно быть строго и недвусмысленно определено в каждом случае. Конечностьопределяет, что каждое действие в отдельности и алгоритм в целом должны иметь возможность завершения. Процесс решения задачи должен прекратиться за конечное число шагов

13 Свойства алгоритмов Результативностьтребует, чтобы в алгоритме не было ошибок, т.е. при точном исполнении всех команд должен быть получен определенный постановкой задачи результат (ответ). Массовость Это свойство показывает, что один и тот же алгоритм можно использовать с разными исходными данными, т.е. применять при решении всего класса задач данного типа, отвечающих общей постановке задачи.

14 Формы записи алгоритмов Существуют различные способы записи алгоритмов: на естественном языке; на специальном (формальном) языке; с помощью формул, рисунков, таблиц; с помощью стандартных графических объектов (геометрических фигур) – блок-схемы.

15 Формы записи алгоритмов на специальном (формальном) языке на специальном (формальном) языке на специальном (формальном) языке на специальном (формальном) языке СЛОВЕСНАЯ (на естественном языке) СЛОВЕСНАЯ (на естественном языке) СЛОВЕСНАЯ (на естественном языке) СЛОВЕСНАЯ (на естественном языке) БЛОК-СХЕМА с помощью формул, рисунков, таблиц с помощью формул, рисунков, таблиц с помощью формул, рисунков, таблиц с помощью формул, рисунков, таблиц

16 Словесная форма записи алгоритмов Последовательность шагов, которые выполняются исполнителем, записывается в форме нумерованного списка. Фонетический разбор слова. 1. Записать слово, разделив его на фонетические слоги. 2. Указать количество слогов, выделив ударный. 3. Дать характеристику звуков (гласных, согласных). 4. Указать количество звуков и букв. Алгоритм нахождения площади квадрата. 1. Измерить длину стороны квадрата a. 2. Найти площадь квадрата по формуле: S=a*a*a*a (или S=a^4).

17 Блок - схема. Для обозначения шагов алгоритма в блок-схемах используются геометрические фигуры: ОВАЛ Начало или конец ПАРАЛЛЕЛОГРАММ Ввод или вывод РОМБ Принятие решения ПРЯМОУГОЛЬНИК Выполнение действия

18 Текстовый алгоритм Блок-схема Начало 1.Воспринять. 2.Запомнить. 3. Выбрать форму представления. 4.Преобразовать. 5.Представить(сохранить) на Носителе. Конец. Формы записи алгоритмов Сопоставим две разные формы записи алгоритма представления информации на носителе. Начало Представить Запомнить Воспринять Выбрать Преобразовать Конец

19 И в словесной форме, и графической (блок- схема) один и тот же алгоритм. Слова «начало» и «конец» - это не команды, а неисполняемые инструкции. А вот между ними располагаются исполняемые инструкции: «Воспринять», «Запомнить», «Выбрать», «Преобразовать», «Представить». Формы записи алгоритмов

20 В алгоритмах команды записываются друг за другом в определенном порядке. Выполняются они необязательно в записанной последовательности. В зависимости от порядка выполнения команд выделяют три типа алгоритмов. Типы алгоритмов. Базовые структуры алгоритма Следование ВетвлениеЦикл

21 Линейным называется алгоритм, в котором команды выполняются в порядке их записи, то есть последовательно друг за другом. Типы алгоритмов. Линейные алгоритмы. Начало Действие 1. Действие 2. Действие N. Конец Структура следование указывает на то, что управление передается последовательно от одного действия к другому.

22 Пример линейного алгоритма в двух формах записи. Алгоритм посадки дерева. Типы алгоритмов. Линейные алгоритмы. Текстовый алгоритм. Начало 1. Выкопать в земле ямку. 2. Опустить в ямку саженец. 3. Закопать ямку с саженцем землей. 4. Полить саженец водой. Конец. Блок схема. Начало Выкопать в земле ямку. Опустить в ямку саженец. Закопать ямку саженцем землей. Полить саженец водой. Конец

23 Ветвлением называется - форма организации действий, при которой в зависимости от выполнения или невыполнения некоторого условия совершается либо одна, либо другая последовательность действий. Типы алгоритмов Алгоритмы с ветвлением. Алгоритмы с ветвлением. В программировании структура ветвление используется тогда, когда в зависимости от результата проверки условия выполнение программы может измениться и пойти разными путями. Основные варианты структуры ветвление. если-то если-то-иначе выбор-иначе

24 Типы алгоритмов. Алгоритмы с ветвлением. Начало Действие 1. Конец Условие если да если нет Начало Действие 1. Конец Условие если да если нет Действие 2.

25 Цикл (повторение) это - форма организации действий, при которой выполнение одной и той же последовательности действий повторяется, пока выполняется некоторое заранее установленное условие. Алгоритм, содержащий циклы, называется циклическим. Зацикливание ситуация, при которой выполнение цикла никогда не заканчивается. Алгоритмы с повторением. Структура цикл служит для записи алгоритмов, в которых определенная часть повторяется несколько раз. Цикл с предусловием, или цикл «пока»Цикл с параметром Цикл с постусловием, или цикл «до» Типы алгоритмов

26 Цикл с предусловием, или цикл «пока». При реализации этого цикла сначала проверяется условие его выполнения. Если оно выполняется, то будет выполняться тело цикла. Если при первой проверке условие не выполняется, то цикл не выполняется вообще. Алгоритмы с повторением. Цикл с предусловием, или цикл «пока». Условие Тело цикла нет да Типы алгоритмов

27 Цикл с параметром. В таких циклах заранее известно количество повторений цикла. Здесь вводится понятие счетчик цикла, который по умолчанию считается равным 1, либо -1. Для организации цикла необходимо задать верхнюю и нижнюю границы изменений счетчика цикла. Типы алгоритмов Алгоритмы с повторением. Цикл с параметром. i=i1, i2,... Тело цикла нет да

28 Цикл с постусловием, или цикл «до». При реализации этого цикла условие проверяется после тела цикла, и таким образом тело цикла выполняется хотя бы один раз. Цикл выполняется до тех пор, пока условие не будет реализовано. Типы алгоритмов Алгоритмы с повторением. Цикл с постусловием, или цикл «до». Условие Тело цикла нет да

29 Алгоритмические языки программирования и их классификация Программа - это набор инструкций (операторов), записанных на алгоритмическом языке и реализующих заданный алгоритм. Программа на алгоритмическом языке записывается в обычном текстовом редакторе и сохраняется как файл. Такой программный файл называется исходным модулем программы.

30 Алгоритмические языки программирования и их классификация -процедурные, к которым относится большинство классических языков программирования, например: Fortran, Pascal, Basic, C и др. -логические, например: Lisp, Prolog и др. -объектно- ориентированные, например: C++, Java, Python, Delphi и др. языки ассемблера; языки высокого уровня; командные языки базы данных.

31 Основные этапы решения задачи на ПЭВМ 1. Постановка задачи: сбор информации; формулировка условия; определение конечных целей решения; форма выдачи результатов; описание данных. 2. Формулировка математической модели задачи: составление математической модели; выбор метода решения задачи; разработка структур данных, 3. Разработка алгоритма: метод построения алгоритма; выбор тестов и методов тестирования; построение алгоритма. 4. Составление программы: выбор языка программирования; уточнение способов организации данных; запись алгоритма на языке программирования. 5. Отладка и тестирование программы на ПЭВМ: проверка синтаксиса, семантики и логической структуры; тестовые расчеты; совершенствование программы. 6. Реализация программы на ПЭВМ для реальных данных. 7. Анализ полученных результатов. 8. Модернизации алгоритма расчета и программы (если необходимо)

32 СПАСИБО ЗА ВНИМАНИЕ.