Інформатика:основи комп’ютерних алгоритмів

Матеріал з USIC Wiki

Перейти до: навігація, пошук

Ця стаття відноситься до групи довідкових статей для студентів ФІН.

Портал:Інформаційні науки

Державний іспит

Зміст

1 Спискові структури даних.
2 Основні алгоритми на графах.
3 Часова складність алгоритмів.
4 Формальні мови й граматики.
5 Метод резолюцій та його застосування в логічному програмуванні.
6 Дерева та графи; їх подання в пам’яті комп’ютера.
7 Метод перебору з поверненнями (back tracking).
8 Метод „розділяй і пануй”, його часова оцінка та застсування.
9 Метод динамічного програмування та його застосування.
10 Фреймова модель задання знань.
11 Семантичні мережі.
12 Розпізнавання образів.
13 Метод резолюцій, як основа логічного виведення.
14 Функціональна мова програмування ЛІСП.
15 Логічна мова програмування ПРОЛОГ.
16 Застосування методу динамічного програмування до задачі добутку матриць.
17 Алгоритм впорядкування злиттям.
18 Метод найшвидшого спуску.
19 Знаходження найкоротших шляхів у графі.
20 Задання дерев у пам’яті.
21 Фундаментальна множина циклів графу.
22 Алгоритми розфарбовування графів.
23 Алгоритми генерування всіх перестановок.
24 Алгоритми пошуку на графах.
25 Стеки та черги.
26 Алгоритми знаходження остовного дерева найменшої вартості.
27 Ізоморфізм дерев.
28 Задача про розташування n ферзів.
29 Метод гілок і границь.
30 Бінарний пошук.
31 Планування в просторі станів і в просторі задач.

Спискові структури даних.

Основні алгоритми на графах.

Часова складність алгоритмів.

Матеріали з російської вікіпедії, сподіваюся, всі зрозуміють без перекаду -- oksamyt 15:51, 3 червень 2008 (EEST)

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

Трудоёмкость алгоритмов по-разному зависит от входных данных. Для некоторых алгоритмов трудоемкость зависит только от объема данных, для других алгоритмов — от значений данных, в некоторых случаях порядок поступления данных может влиять на трудоемкость. Трудоёмкость многих алгоритмов может в той или иной мере зависеть от всех перечисленных выше факторов.

Одним из упрощенных видов анализа, используемых на практике, является асимптотический анализ алгоритмов. Целью асимптотического анализа является сравнение затрат времени и других ресурсов различными алгоритмами, предназначенными для решения одной и той же задачи, при больших объемах входных данных. Используемая в асимптотическом анализе оценка функции трудоёмкости, называемая сложностью алгоритма, позволяет определить, как быстро растет трудоёмкость алгоритма с увеличением объема данных. В асимптотическом анализе алгоритмов используются обозначения, принятые в математическом асимптотическом анализе. Ниже перечислены основные оценки сложности.

Основной оценкой функции сложности алгоритма f(n) является оценка $\boldsymbol{\Theta}$ . Здесь n — величина объёма данных или длина входа. Мы говорим, что оценка сложности алгоритма

$f(n) = \boldsymbol{\Theta}(g(n))$

если при g > 0 при n > 0 существуют положительные с₁, с₂, n₀, такие, что:

$c_1 g(n)\le \; f(n) \le \; c_2 g(n)$

при n > n₀, иначе говоря, можно найти такие с₁ и c₂, что при достаточно больших n f(n) будет заключена между

$\boldsymbol{c_1\;g(n)}$ и $\boldsymbol{c_2\;g(n)}$ .

В таком случае говорят еще, что функция g(n) является асимптотически точной оценкой функции f(n), так как по определению функция f(n) не отличается от функции g(n) с точностью до постоянного множителя (см. асимптотическое равенство). Например, для метода сортировки heapsort оценка трудоёмкости составляет

$f(n) = \boldsymbol{\Theta}(n \log n)$ то есть $g (n) = n log n$

Из $f(n) = \boldsymbol{\Theta}(g(n))$ следует, что $g(n) = \boldsymbol{\Theta}(f(n))$ .

Важно понимать, что $\boldsymbol{\Theta}(g(n))$ представляет собой не функцию, а множество функций, описывающих рост $\boldsymbol{f(n)}$ с точностью до постоянного множителя.

$\boldsymbol{\Theta}$ дает одновременно верхнюю и нижнюю оценки роста функции. Часто бывает необходимо рассматривать эти оценки по отдельности. Оценка $\boldsymbol{O}$ представляет собой верхнюю асимптотическую оценку трудоемкости алгоритма. Мы говорим, что $f(n)=\boldsymbol{O}(g(n))$ если

$\exists \; c > 0, n_0 > 0 : 0 \le \; f(n) \le \; c g(n), \forall \; n > n_0$

Иначе говоря, запись $f(n) = \boldsymbol{O}(g(n))$ означает, что f(n) принадлежит классу функций, которые растут не быстрее, чем функция g(n) с точностью до постоянного множителя.

Оценка $\boldsymbol{\Omega}$ задает нижнюю асимптотическую оценку роста функции f(n) и определяет класс функций, которые растут не медленнее, чем g(n) с точностью до постоянного множителя. $f(n)=\boldsymbol{\Omega}(g(n))$ если

$\exists \; c > 0, n_0 > 0 : 0 \le \; c g(n) \le \; f(n), \forall \; n > n_0$

Например, запись $f(n)=\boldsymbol{\Omega} (n \log \; n)$ обозначает класс функций, которые растут не медленнее, чем $\boldsymbol{g(n) = n \log \; n}$ , в этот класс попадают все полиномы со степенью большей единицы, равно как и все степенные функции с основанием большим единицы. Равенство $f(n) = \boldsymbol{\Theta}(g(n))$ выполняется тогда и только тогда, когда $f(n)=\boldsymbol{O}(g(n))$ и $f(n)=\boldsymbol{\Omega}(g(n))$ .

Асимптотический анализ алгоритмов имеет не только практическое, но и теоретическое значение. Так, например, доказано, что все алгоритмы сортировки, основанные на попарном сравнении элементов, отсортируют n элементов за время, не меньшее $\boldsymbol{\Omega}(n \log n)$ .

Важную роль в развитии асимптотического анализа алгоритмов сыграли A. Ахо, Дж. Ульманом, Дж. Хопкрофт.

http://ru.wikipedia.org/wiki/Теория_алгоритмов

Розглядаючи вхідні дані достатньо великих розмірів для оцінки такої величини, як порядку росту часу роботи алгоритму ми тим самим вивчаємо асимптотичну ефективність алгоритмів. Це означає, що нас цікавить тільки те, як час роботи алгоритму зростає, коли розмір вхідних даних прямує до нескінченності. За звичай алгоритм, більш ефективний в асимптотичному смислі, буде більш ефективним для всіх вхідних даних за винятком хіба що дуже малих.

$\boldsymbol{\Theta}$ - позначення

Для деякої функції $g (x)$ запис $\boldsymbol{\Theta}(g(n))$ означає множину функцій $\boldsymbol{\Theta}(g(n)) = \begin{Bmatrix} f(n) : \exists \; c_1 > 0, c_2 > 0, n_0 > 0 \\ 0 \le \; c_1 g(n)\le \; f(n) \le \; c_2 g(n), n \ge n_0 \end{Bmatrix}$

Функція $f (n)$ належить $\boldsymbol{\Theta}(g(n))$ , якщо існують додатні константи $c 1$ та $c 2$ , такі що вона буде обмежена функціями $c 1 g (n)$ та $c 2 g (n)$ для достатньо великих n. Оскільки $\boldsymbol{\Theta}(g(n))$ це множина, то можна написати $f(n) \in \boldsymbol{\Theta}(g(n))$ . Для цього зазвичай використовують еквівалентне позначення $f(n) = \boldsymbol{\Theta}(g(n))$ . Знак дорівнює для позначення належності множині може збивати з пантелику, але як буде видно далі це має свої переваги. Кажуть, що функція $g (n)$ є асимптотично точною оцінкою функції $f (n)$ . Відповідно до означення множини $\boldsymbol{\Theta}(g(n))$ , потрібно щоб кожен її елемент $f (n)$ був асимптотично невідємним. Це означає, що при достатньо великих $n$ функція $f (n)$ є невідємною. Відповідно функція $g (n)$ має бути асимптотично невідємною, оскільки в протилежному випадку множина $\boldsymbol{\Theta}(g(n))$ буде порожньою.

Доведемо, що має місце $n^2/2 - 3n = \boldsymbol{\Theta}(n^2)$ за допомогою формального означення. Для цього потрібно визначити чому дорівнюють додатні константи $c 1$ , $c 2$ та $n 0$ , щоб виконувалась нерівність $c_1n^2\le \; n^2/2 - 3n \le \; c_2n^2$ , при всіх $n_0\le \;n$ . Поділивши дану нерівність на $n 2$ , отримаємо: $c_1\le \; \frac{1}{2} - \frac{3}{n} \le \; c_2$ . Права нерівність виконується при всіх $n \ge 1$ , якщо обрати $c_2 \ge \frac{1}{2}$ . Аналогічно, ліва нерівність виконується при всіх $n \ge 7$ , якщо обрати $c_1 \le 14$ . Таким чином, обравши $c_1=\frac{1}{14}, c_2 = \frac{1}{2}, n_0 = 7$ , переконуємось в тому, що $n^2/2 - 3n = \boldsymbol{\Theta}(n^2)$ .

Також за допомогою формального означення покажемо, що $6n^3 \ne \boldsymbol{\Theta}(n^2)$ . Від супротивного...Припустимо, що знайдуться такі $c 2$ та $n 0$ , що $6n^3 \le c_2n^2$ для всіх $n \ge n_0$ . Тоді, виходить, що $n \le c_2/6$ , а ця нерівність не може виконуватись для великих $n$ , оскільки $c 2$ є константою. Суперечність...

$\boldsymbol{O}$ - позначення

В $\boldsymbol{\Theta}(n^2)$ - позначенні функція асимптотично обмежена зверху і знизу. Якщо досить визначити тільки асимптотично верхну межу використовують $\boldsymbol{O}$ -позначення. Для деякої функції $g (n)$ позначення $\boldsymbol{O(g(n))}$ означає множину функцій таких, що $\boldsymbol{O}(g(n)) = \begin{Bmatrix} f(n) : \exists \; c > 0, n_0 > 0 \\ 0 \le f(n) \le cg(n), n \ge n_0 \end{Bmatrix}$ .

Щоб вказати, що функція $f (n)$ належить множині пишуть $f(n) = \boldsymbol{O(g(n))}$ . Також варто звернути увагу на те, що із $f(n) = \boldsymbol{\Theta}(g(n))$ випливає, що $f(n) = \boldsymbol{O}(g(n))$ , оскільки $\boldsymbol {\Theta}(g(n)) \subset {O}(g(n))$ .

$\boldsymbol{\Omega}$ - позначення

Аналогічно тому як для $\boldsymbol{O}$ дається асимптотична верхня межа функції, в $\boldsymbol{\Omega}(g(n))$ -позначеннях дається її асимптотична нижня оцінка. Для даної функції $g (n)$ позначення $\boldsymbol{\Omega(g(n))}$ означає множину функцій таких, що $\boldsymbol{\Omega}(g(n)) = \begin{Bmatrix} f(n) : \exists \; c > 0, n_0 > 0 \\ 0 \le cg(n) \le f(n), n \ge n_0 \end{Bmatrix}$ .

Теорема. Для довільних двої функцій $f (n)$ та $g (n)$ співвідношення $f(n) = \boldsymbol{\Theta}(g(n))$ , виконується тоді і тільки тоді, коли $f(n) = \boldsymbol{O}(g(n))$ та $f(n) = \boldsymbol{\Omega}(g(n))$ .

Формальні мови й граматики.

Метод резолюцій та його застосування в логічному програмуванні.

Дерева та графи; їх подання в пам’яті комп’ютера.

Метод перебору з поверненнями (back tracking).

Метод „розділяй і пануй”, його часова оцінка та застсування.

Метод динамічного програмування та його застосування.

Фреймова модель задання знань.

Семантичні мережі.

Розпізнавання образів.

Метод резолюцій, як основа логічного виведення.

Функціональна мова програмування ЛІСП.

Логічна мова програмування ПРОЛОГ.

Застосування методу динамічного програмування до задачі добутку матриць.

Алгоритм впорядкування злиттям.

Метод найшвидшого спуску.

Знаходження найкоротших шляхів у графі.

Задання дерев у пам’яті.

Фундаментальна множина циклів графу.

Алгоритми розфарбовування графів.

Алгоритми генерування всіх перестановок.

Алгоритми пошуку на графах.

Стеки та черги.

Алгоритми знаходження остовного дерева найменшої вартості.

Ізоморфізм дерев.

Задача про розташування n ферзів.

Метод гілок і границь.

Бінарний пошук.

Планування в просторі станів і в просторі задач.