АЛГОРИТМЫ и АЛГОРИТМИЧЕСКИЕ ЯЗЫКИ Лектор: Абрамов Владимир Геннадьевич кафедра алгоритмических языков ф-та ВМиК По разделу «Элементы теории алгоритмов»: - презентация

1 АЛГОРИТМЫ и АЛГОРИТМИЧЕСКИЕ ЯЗЫКИ Лектор: Абрамов Владимир Геннадьевич кафедра алгоритмических языков ф-та ВМиК По разделу «Элементы теории алгоритмов»: 1. Любимский Э.З., Мартынюк В.В., Трифонов Н.П. «Программирование» - М.: Наука, Корухова Л.С., Шура-Бура М.Р. «Введение в алгоритмы» - М.: МГУ, 1997 По разделу «Язык Паскаль»: 3. Абрамов В.Г., Трифонов Н.П., Трифонова Г.Н. «Введение в язык Паскаль» - М.: Наука, К. Йенсен, Н. Вирт. «Паскаль. Руководство для пользователя». – М.: «Компьютер», По разделу «Структуры данных»: 5. Вирт Н. «Алгоритмы + структуры данных = программы». – М.: «Мир», А. Ахо, Д. Хопкрофт, Д. Ульман «Структуры данных и алгоритмы». – М.: «Вильямс», 2000.

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

3 Алгоритм Евклида. 1. Если x=y, то положить z равным x и остановиться, иначе перейти к пункту Если x>y, то положить x равным x-y, иначе положить y равным y-x. В любом случае перейти к пункту 1.

4 Исполнение алгоритма Выполним алгоритм Евклида при конкретных исходных данных: x=45, y=30: 1. Проверяем x=y? Нет к п Проверяем x>y? Да выполняем действие после слова "то": x=45-30=15 и y=30 Переходим снова к п Снова проверяем: x=y? Нет к п Проверяем x>y? Теперь нет выполняем действие после слова "иначе": x=15 и y=30-15=15 Переходим к п x=y? Да z=15 и останов. Итак, ответ: НОД(45,30) = 15. y? Теперь нет выполняем действие после слова "иначе": x=15 и y=30-15=15 Переходим к п. 1. 5. x=y? Да z=15 и останов. Итак, ответ: НОД(45,30) = 15.">

5 Свойства алгоритмов 1) Полнота описания. 2) Выполнимость. 3) Однозначность (детерминированность). 4) Конечность (результативность).

6 Интуитивное определение алгоритма Алгоритм - это точно сформулированная совокупность правил для исполнителя, указывающая как решать задачу, причем эта совокупность должна удовлетворять свойствам полноты, выполнимости, однозначности и конечности.

7 Способы описания алгоритмов 1. СЛОВЕСНОЕ ОПИСАНИЕ АЛГОРИТМОВ 2. БЛОК-СХЕМЫ x=2 да-нет а) x:=5 б) начало в)

8 x=y да нет x:=x-y начало конец x>y y:=y-x нет да z:=x Алгоритм Евклида.

9 Задача: Дано 100 чисел х 1, х 2,..., х 100. Найти S – их сумму. начало S:=0 i:=1 S:=S+xi i:=i+1 i 100 конец да нет