Вопрос 19. Оценка сложности рекурсивных алгоритмов.

Практика разработки и использования алгоритмов выдвигает ряд серьезных причин, препятствующих широкому применению рекурсии:

рекурсивные алгоритмы, как правило, более затратные с точки зрения времени и памяти, нежели итерационные алгоритмы, решающие ту же задачу. При этом на сложность рекурсивного алгоритма большое влияние оказывает сама организация рекурсии;

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

Основными современными инструментами исследования сложности рекурсивных алгоритмов являются метод рекуррентных соотношений и теоретико-графовый метод исследования дерева рекурсии. Идея метода рекуррентных соотношений состоит в построении и решении рекуррентного соотношения, которому удовлетворяет функция сложности t(n)алгоритма. Найденное решение позволяет получить O-оценку для t(n). Этот метод не является универсальным. Во-первых, он применим только для оценки временной сложности рекурсивных алгоритмов. Оценка емкостной сложности требует учета глубины рекурсии и, как следствие, других инструментов. Во-вторых, метод рекуррентных соотношений позволяет получить лишь верхние оценки временной сложности рекурсивных алгоритмов. В-третьих, рекуррентное соотношение для t(n) удается найти только тогда, когда преобразование, уменьшающее значение параметра рекурсии n, линейно относительно n.

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

 

t(n)=

где n — параметр рекурсии; n0 — размер задачи, при котором время работы алгоритма не зависит от n; c > 0 — трудоемкость не рекурсивной ветви (некоторая постоянная величина); ts — время сведения задачи к подзадачам; tr — трудоемкость рекурсивной ветви (время выполнения подзадач); tu — время объединения решений, полученных подзадачами.

В тех случаях, когда не удается получить рекуррентное соотношение для функции временной сложности, прибегают к построению дерева рекурсии. Кроме того, дерево рекурсии незаменимо для анализа емкостной сложности рекурсивного алгоритма.

 

Вопрос 20. Структура программы на языке С++.

Препроцессор - специальная программа, которая распознает текст программы. Операторы языка разделяются друг от друга;. Программа должна обрабатывать информацию, значит нужны средства ввода/вывода информации. Для некоторых программ не нужно ввода (генератор простых чисел), но вывод должен быть обязательно.

Первоначальная инструкция для пакета ввода/вывода.

#include <iostream>;

Команда #include вставляет в программу заранее подготовленные тексты из включаемых файлов.

< > означает поиск в служебных файлах.

iostream (input/output stream) –название пакета. В отдельных пакетах собраны готовые части, содержащие служебные тексты для ввода и вывода.

using namespace std; -использование шаблонов из стандартных пакетов.

void main ()

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

void означает, что можно не указывать тип переменных.

Если мы указываем тип функции, определяющей результат (int main - целые), то необходимо будет выдать результат. Для этого return 0;-любое целое число.

{ - открывающая скобка.

} – закрывающая скобка.

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

Для перехода курсора на следующую строку надо добавить endl.

Знак = означает присваивание, а знак = = означает сравнение.

Программа на языке Си это текстовый файл с расширением. c

Текст программы имеет определенную структуру:

1. заголовок

2. включение необходимых внешних файлов

3. ваши определения для удобства работы

4. объявление глобальных переменных

Перед использованием переменной в Си её необходимо объявить! Т.е. указать компилятору какой тип данных она может хранить и как она называется.

Глобальные переменные объявляются, вне какой либо функции. Т.е. не после фигурной скобки {. Они доступны в любом месте программы, значит можно читать их значения и присваивать им значения там, где требуется.

5. описание функций - обработчиков прерываний

6. описание других функций используемых в программе

7. функция main - это единственный обязательный пункт!

 

Это не жесткий порядок, а ориентировочный!

Иногда п. 6 - это прототипы функций, а сами функции описываются полностью после п. 7.

Прототип функции - показывает образец того, как применять функцию в программе, какие значения в нее передаются и, если она возвращает какое-то значение, то прототип указывает тип возвращаемых данных. Прототип не имеет скобок { }, а после скобок () ставится знак;.

Функция - имеет { "тело" } в фигурных скобках. Тело - это код на Си определяющий то, что делает функция. Знак «;» после функции не ставится.

 

Программа на Си начинает работу с функции main(), по необходимости из main() вызываются другие функции программы, по завершении работы функции программа возвращается в main(), в то место, откуда функция была вызвана.

main(){

 

... какой то код программы...

вызов функции_1; /* программа перейдет в функцию_1 строка программы */

// будет выполнятся после

// возврата из функции_1

... какой то код программы...

}

Функции могут вызываться не только из main(), но и из других функций.