Информатика. Домашнее задание 2 семестр
Срок сдачи до 20.05.2013г. (на титульном листе написать ФИО студента и номер группы). Выбираете вариант согласно Вашему номеру в списке группы. Нарисовать блок-схему алгоритма и программу на любом из языков программирования Си, Паскаль Бейсик, в задании 4 дополнительно оценить сложность алгоритма (число операций в зависимости от размерности исходных данных). Блок-схемы выполнять по ГОСТ 19.701-90 (см. приложение 1) на листах формата А4.
Задание 1
Задание 4
Методические указания
Алгоритм – понятное и точное предписание исполнителю выполнить конечную последовательность команд, приводящую от исходных данных к искомому результату.
Согласно определения алгоритм – неразрывное единство данных и процессов их обработки (преобразования). Поэтому при разработке алгоритма следует уделять внимание обоим аспектам (наиболее типичные ошибки):
А) Нельзя выполнять обработку если не определены исходные данные. Например,
Неверно: X:=X*2, если в ячейку X ничего не занесено
Верно: INPUT X; X=:X*2
Б) Обработка данных переводит их из одного состояния в другое, при этом также возможны ошибки, например, Вы полагаете, что данные в ячейке памяти старые, а они уже изменились.
Например, требуется переставить местами 2 числа X и Y:
Неверно писать X:=Y; Y:=X
После первой операции присваивания X:=Y в ячейку X запишется значение из ячейки Y; второе присваивание ничего не изменит. В результате в обеих ячейках X и Y будет одинаковое значение (какое?)
Правильно: A:=X; X:=Y; Y:=A
Блок-схемы служат для записи алгоритмов. Преимущества блок-схем – их наглядность и интуитивная понятность.
Алгоритмы строятся из базовых конструкций: линейная, ветвление, цикл. Примеры алгоритмов:
|
|
|
|
|
|
|
Пример 1
Пример 2. Суммирование
Пример 3. Счетчик.
Работа с одномерным массивом
Пример 4.
Работа с матрицей (двумерный массив)
В математике двумерный массив (таблица чисел) называется матрицей. Каждый ее элемент имеет два индекса aij, первый индекс i определяет номер строки, в которой находится элемент (координата по горизонтали), а второй j – номер столбца (координата по вертикали). Двумерный массив характеризуется двумя размерностями N и M, определяющими число строк и столбцов соответственно.
Пример 5
|
|
Основы оценок сложности алгоритмов
Нам уже известно, что правильность -- далеко не единственное качество, которым должна обладать хорошая программа. Одним из важнейших является эффективность, характеризующая прежде всего время выполнения программы 
для различных входных данных (параметра 
).
Нахождение точной зависимости для конкретной программы -- задача достаточно сложная. По этой причине обычно ограничиваются асимптотическими оценками этой функции, то есть описанием ее примерного поведения при больших значениях параметра . Иногда для асимптотических оценок используют традиционное отношение 
(читается <<О большое>>) между двумя функциями 
, определение которого можно найти в любом учебнике по математическому анализу, хотя чаще применяют отношение эквивалентности 
(читается <<тэта большое>>).
|
|
Рассмотрим предыдущий пример с матрицей. Предположим, что размер матрицы равен X(MxN), где M и N достаточно большие числа. Тогда первый цикл (ввод матрицы) выполняется за O(MxN) операций, второй также – за O(MxN) операций. Мы ищем асимптотическую оценку (при M и N ® ¥), поэтому M и N можно заменить одним числом n, получим O(n2), где n –размерность матрицы. В качестве окончательной оценки выбираем наибольшую из составляющих оценок (в нашем случае они равны), окончательная оценка - O(n2).
В качестве первого примера вернемся к только что рассмотренным программам нахождения факториала числа. Легко видеть, что количество операций, которые должны быть выполнены для нахождения факториала 
числа в первом приближении прямо пропорционально этому числу, ибо количество повторений цикла (итераций) в данной программе равно . В подобной ситуации принято говорить, что программа (или алгоритм) имеет линейную сложность (сложность 
или 
).
Можно ли вычислить факториал быстрее? Оказывается, да. Можно написать такую программу, которая будет давать правильный результат для тех же значений , для которых это делают все приведенные выше программы, не используя при этом ни итерации, ни рекурсии. Ее сложность будет 
, что фактически означает организацию вычислений по некоторой формуле без применения циклов и рекурсивных вызовов!
Не менее интересен и пример вычисления -го числа Фибоначчи. В процессе ее исследования фактически уже было выяснено, что ее сложность является экспоненциальной и равна 
. Подобные программы практически не применимы на практике. В этом очень легко убедиться, попробовав вычислить с ее помощью 40-е число Фибоначчи. По этой причине вполне актуальна следующая задача.
|
|
Вот решение этой задачи, в котором переменные j и k содержат значения двух последовательных чисел Фибоначчи.
Следующий вопрос вполне естественен -- а можно ли находить числа Фибоначчи еще быстрее?
После изучения определенных разделов математики совсем просто вывести следующую формулу для -ого числа Фибоначчи 
, которую легко проверить для небольших значений :
Может показаться, что основываясь на ней, легко написать программу со сложностью , не использующую итерации или рекурсии.
На самом деле эта программа использует вызов функции возведения в степень Math.pow(f,n), которая не может быть реализована быстрее, чем за логарифмическое время (
). Про алгоритмы, в которых количество операций примерно пропорционально 
(в информатике принято не указывать основание двоичного логарифма) говорят, что они имеет логарифмическую сложность (
).
В заключение приведем сравнительную таблицу времен выполнения алгоритмов с различной сложностью и объясним, почему с увеличением быстродействия компьютеров важность использования быстрых алгоритмов значительно возрастает.
Рассмотрим четыре алгоритма решения одной и той же задачи, имеющие сложности 
, 
, 
и 
соответственно. Предположим, что второй из этих алгоритмов требует для своего выполнения на некотором компьютере при значении параметра 
ровно одну минуту времени. Тогда времена выполнения всех этих четырех алгоритмов на том же компьютере при различных значениях параметра будут примерно такими, как в таблице 5.1.
| Таблица 5.1. Сравнительная таблица времен выполнения алгоритмов | |||
| Сложность алгоритма | n=10 | n=103 | n=106 |
| log n | 0.2 сек. | 0.6 сек. | 1.2 сек. |
| n | 0.6 сек. | 1 мин. | 16.6 час. |
| n2 | 6 сек. | 16.6 час. | 1902 года |
| 2n | 1 мин. | 10295 лет | 10300000 лет |
Когда начинающие программисты тестируют свои программы, то значения параметров, от которых они зависят, обычно невелики. Поэтому даже если при написании программы был применен неэффективный алгоритм, это может остаться незамеченным. Однако, если подобную программу попытаться применить в реальных условиях, то ее практическая непригодность проявится незамедлительно.
С увеличением быстродействия компьютеров возрастают и значения параметров, для которых работа того или иного алгоритма завершается за приемлемое время. Таким образом, увеличивается среднее значение величины , и, следовательно, возрастает величина отношения времен выполнения быстрого и медленного алгоритмов. Чем быстрее компьютер, тем больше относительный проигрыш при использовании плохого алгоритма!