ПЛАН ЗАНЯТТЯ No4
Дата: група: Дисципліна: Алгоритми та структури даних. Тема: Виконання та аналіз правильності алгоритмів Мета:
Методична: закріпити методику проведення лекційного заняття. Дидактична: розглянути загальні правила алгоритмічної мови, команди галуження, команди повторення. Виховна: зміцнювати бажання вивчення дисципліни.
Вид заняття: лекційне заняття. Форми та методи проведення заняття: інформаційно-рецептивні, фронтальне опитування, викладання нового матеріалу.
Міжпредметні зв’язки:
- Дисципліни, що забезпечують: математичний аналіз, лінійна алгебра та аналітична геометрія.
- Дисципліни, що забезпечуються: алгоритмічні мови та програмування, об'єктно-орієнтоване програмування.
Науково-методичне забезпечення:
- Алтухов Е.В., Рыбалко Л.А., Савченко В.С. Основы информатики и
вычислительной техники: Учеб. пособие для учащ. средн. спец. уч. заведений. – М.: Высш. шк., 1992. – 303 с. 2. Савченко В.С. Разработка алгоритмов: от простого к сложному.
Учебное пособие для классов с углубленным изучением информатики. – Донецк, 1996 – 320 с.
ХІД ЗАНЯТТЯ.
- Організаційний момент: перевірка відсутніх, зовнішнього вигляду,
готовності аудиторії. 2. Повідомлення теми, формування мети та основних завдань. 3. План викладання нового матеріалу: надано в конспекті лекції. 4. Актуалізація опорних знань:
- Дати визначення похідної;
- Дати визначення первісної, невизначеного інтегралу;
- Дати визначення диференціалу;
- Визначити зв’язок неперервності та диференційованості;
- Необхідні умови інтегрованості функції;
- Таблиця похідних, таблиця інтегралів основних елементарних функцій. 5. Вивчення нового матеріалу: Тема лекції: Виконання та аналіз правильності алгоритмів.
- Мотивація вивчення матеріалу: диференціальні рівняння – це основний сучасний засіб розв’язання прикладних задач, який дає змогу описати математичну модель на зрозумілій мові. Тому, сучасному студенту необхідно вміти не тільки розв’язувати основні типи звичайних диференціальних рівнянь, але моделювати за допомогою диференціальних рівнянь текстові задачі.
- План вивчення нового матеріалу: надається в конспекті лекції. 6. Виклад нового матеріалу: конспект лекції надається. 7. Закріплення нового матеріалу: обговорення окремих питань алгоритмів. 8. Підведення підсумків заняття. 9. Домашнє завдання:
Викладач М.П.Леверя
Лекція No4 Тема: Виконання та аналіз правильності алгоритмів.
План 1. Виконання та аналіз правильності алгоритмів.
- Виконання та аналіз правильності алгоритмів. Исполнение алгоритмов. Составленный алгоритм необходимо проверить, т. е. убедиться в том, что он описывает именно тот процесс, который приводит к нужному результату. Одним из способов проверки правильности алгоритма является его исполнение с некоторыми контрольными (тестовыми) наборами исходных данных. Умение быстро и правильно исполнять алгоритмы облегчает задачу создания новых алгоритмов. В процессе разработки алгоритма составитель постоянно должен отдавать себе отчет в том, какие действия исполнителя на самом деле будут вызваны командами алгоритма и к каким изменениям значений используемых переменных эти действия при- ведут.
Исполнение алгоритмов удобно делать, заполняя специальную таблицу значений используемых в алгоритме переменных (табл. 2.3).
Таблица 2.3 Шаги алгоритма
Аргумен ты
Промеж уточные вели- чины
Результа ты
Проверк а условий
... ... ...
Некоторые графы таблицы могут отсутствовать, если в алгоритме соответствующих величин нет. Возможно объединение граф «Аргументы» и «Результаты».
Исполнение алгоритма начинается с задания начальных значений аргументов. Эти значения даются исполнителю алгоритма поручителем. Если же контролируется правильность составления алгоритма (самоконтроль), то значения аргументов подбираются составителем. Варианты значений аргументов должны быть, во-первых, достаточно просты, чтобы можно было легко определить правильный ответ каким-либо другим способом, во-вторых, достаточно разнообразны, чтобы можно было проверить все ветви алгоритма. Отметим, что неверный ответ при исполнении алгоритма говорит о наличии ошибки, но верный ответ еще не доказывает правильности алгоритма, так как при других исходных данных ответ может оказаться неверным (с этим как раз и связано требование использовать для проверки алгоритма различные варианты исходных данных).
Начальные значения аргументов вписываются в соответствующие графы таблицы исполнения и отделяются штриховой линией. Затем начинается пошаговое исполнение команд алгоритма. Если какой-либо переменной присваивается новое значение, то старое значение этой переменной уже не может быть использовано в алгоритме. Чтобы случайно не ошибиться, можно старые значения переменных сразу же зачеркивать. При проверке условий в таблице пишут «да», если условие соблюдается, и «нет», если оно не соблюдается. Пример 2.39. Исполнитель алгоритм НОД (см. пример 2.33) для х=85, у =34.
Таблица 2.4 Шаги алгоритма
Аргументы Результаты Промежуточные
значения
Проверка условий
x y d 85 34 1 85≠34, да 2 85>34, да 3 51 4 51≠34, да 5 51>34, да 6 17 7 17≠34, да 8 17>34, нет 9 17 10 17≠17, нет 11 17 Пример 2.40. Проверить, решает ли следующий алгоритм задачу упорядочения по возрастанию значений величин а1, а.2: алг упорядочение двух элементов (вещ a1, а2) арг а1, а2 рез a1, a2 нач вещ r
если а1 > а2
то r: = а1; a1:=a2; a2:=r все кон
В этом примере исходные значения величин а1, а2 могут быть либо уже упорядочены (а1≤а2), либо не упорядочены (а1>а2) и тогда они должны обменяться своими значениями. Поэтому данный алгоритм достаточно исполнить для двух вариантов исходных данных. Первый вариант: а1=5, а1=7
Таблица 2.5 Шаги алгоритма
Аргументы Результаты Промежуточные
величины
Проверка условий а1 а2 r 1 5 7 5>7, нет
Второй вариант: а1=7, а2=5
Таблица 2.6 Шаги алгоритма
Аргументы Результаты Промежуточные
величины
Проверка условий а1 а2 r 7 5 1 7 7>5, да 2 3 5 4 7
Оба варианта исполнения алгоритма приводят к правильному результату, следовательно, алгоритм составлен верно.
Пример 2. 41 Проверить правильность составления алгоритма вычисления z по формуле
z
= 321 2
+
2 + n
2 + ... + n
2 .
алг сумма (нат n, вещ z) арг n
рез z нач нат i
для i от 1 до n
нц
z
:
=
iz +
n
2
кц кон
Исполним алгоритм для n=2. Результат должен быть равен (1
2
+2
2
)/2=2,5
Таблица 2.7 Шаги алгоритма
Аргументы Результаты Промежуточные
Проверка величины
условий n i z 2 1 1 2 1≤2, да 3 ? При вычислении выражения (z+i
2
)/n оказалось, что значение величины z еще не определено – ошибка в подготовке цикла. Еѐ легко исправить, дописав перед командой повторения команду z:=0. Еще раз исполним алгоритм z:=0 для i от 1 до n
нц
z
:
=
iz +
n
2
кц
Таблица 2.8 Шаги алгоритма
Проверка условий n i z 1 0 2 1 3 1≤2, да 4 0,5 5 2 6 2≤2, да 7 2,25 8 3 9 3≤2, нет Полученный результат z= 2,25 не совпадает с ожидаемым, следовательно, алгоритм составлен неверною
Составим алгоритм заново, проанализировав сначала процесс решения этой задачи. В заданной формуле необходимо сумму квадратов n чисел разделить на n. Выполняя вычисления, мы сначала нашли бы числитель, т. е. сумму квадратов чисел, а затем полученный результат разделили бы на n. Следовательно, деление на n выполняется после суммирования всех чисел, значит, после цикла: z:=0 для i от 1 до n
нц izz : =
+ 2 кц
Аргументы Результаты Промежуточные
значения
nzz =:
Возможен, конечно, и такой вариант решения: z:=0 для i от 1 до n
нц
zz : =
+ i
2
n кц но он нерационален, так как операцию деления придется выполнять n раз.
Для перегляду тексту необхідно залогінитись.