Развити въпроси за изпита по САА при О. Наков в ТУ-София: 1. Основни понятия. Варианти на алгоритми. Влияние върху производителността. Въведение в анализа. 2. Примерна задача – свързаност на обекти. Дефиниране на абстрактни операции в задачата. Начален алгоритъм. Алгоритъм за бързо намиране. Програмна реализация. Представяне в дърво...

Идеята на метода е следната: търси се елемент с най-малкия (или най-големия) ключ; намереният елемент се премества в началото (или в края) на масива и се изключва от разглеждането; действието се повтаря, докато не се изберат всички n елемента. Методът е аналогичен на метода на простото вмъкване - и в двата случая в левия край на масива се образува поредица от вече подредените елементи.

Започва с с целта или решението и се предприема движение в обратната посока - к началната постановка на задачата. След това пак от постановката към решението и т. н. Задача за джипа: Да се пресече пустиня с дължина 1000 мили с MIN разход на гориво. Обемът на резервоара - 500 л, разходът на гориво е 1 л на 1 миля (за улесняване на сметките).

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

Съществуват две дефиниции на дървовидна структура или дърво. Нерекурсивна: Дърво е свързан граф без цикли. Рекурсивна: Дърво от тип Т е структура, образувана от данна от тип Т, наречена корен, и крайно множество (възможно и празно) елементи - дървета от тип Т, наречени поддървета.

Структурата граф подобно на дървото се състои от непразно множество върхове (възли) V и множество дъги (ребра) Е.  Графът е подмножество от декартовото произведение на двете множества - V и E: G = {V, E}

Тук ще откриете примерни задачи и задачи, които са се падали на изпити по Синтез и анализ на алгоритми (САА). Задачите включват: - Алгоритми с едномерни и двумерни масиви. - Аналитични алгоритми. - Списъци. - Сортиране.

Алгоритъм - формализирана методика за решаване на една задача. Лесно съпоста-вима с езиците за програмиране. Преди алгоритмиране трябва да имаме представа за данните и организацията им. Алг. за решаване на дадена задача е последователност от инструкции.