Презентация на тему Алгоритми та рекурсія

алгоритми
Складність алгоритмів
Алгоритми сортування
Префіксний та суфіксний запис
Двійкові та шістнадцяткові числа
Числа

зі знаком
Подальше вивчення матриць

по перетворенню інформації (команд), виконання яких приводить до результату.

Властивості алгоритму:
Елементарність
Визначеність
Масовість
Результативність

Лекція 1. Алгоритми та рекурсія. Слайд 4 з 40

послідовності:





n разів
Загальна формула:
...
...
Лекція 1. Алгоритми та рекурсія. Слайд 5

з 40

= 0;
Цикл по i від 1 до n:
Замінити значення

S на S + p(i);
Кінець циклу.

Лекція 1. Алгоритми та рекурсія. Слайд 6 з 40

називається топологічним сортуванням впорядкування 1, якщо 2 є повним

впорядкуванням, і кожен раз, коли а 1 b, тоді а 2 b.

Алгоритм знаходження топологічного сортування для впорядкування 1 на множині S.
Процедура TC(S, 1):
Вибрати мінімальний елемент s із (S, 1);
Вилучити s із S;
Виконувати наступні кроки до тих пір, поки S не порожнє;
Вибрати мінімальний елемент t з (S, 1) і вилучити його;
Покласти s 1 t;
Перейменувати t в s;
Кінець процедури.

Лекція 1. Алгоритми та рекурсія. Слайд 7 з 40

і B = [Bij] – матриці розміру m 

n.
Добуток матриці А на скаляр a є матриця [Bij] =a[Aij].

Алгоритм знаходження B такий:
Процедура Скаляр(а, А, m, n):
Цикл по i від 1 до m:
Цикл по j від 1 до n:
Bij = aAij ;
Кінець циклу;
Кінець циклу;
Кінець процедури.

Лекція 1. Алгоритми та рекурсія. Слайд 8 з 40

= [Cij] розміру m  n, де Cij  = Aij + Bij.

Алгоритм знаходження суми двох матриць:
Процедура Додавання матриць(А, В, m, n):
Цикл по i від 1 до m:
Цикл по j від 1 до n:
Cij = Aij + Bij ;
Кінець циклу;
Кінець циклу;
Кінець процедури.

Лекція 1. Алгоритми та рекурсія. Слайд 9 з 40

 р, а B = [Bij] є матриця p

 n.Тоді (матричний) добуток A і B, що позначається через AB, є матриця C = [Cij] розміру m  n, де Cij – скалярний добуток i-го рядка матриці A і j-го стовпця матриці B.

Cij = [Ai1 Ai2 Ai3 … Aip] *

Лекція 1. Алгоритми та рекурсія. Слайд 10 з 40

і від 1 до m:
Цикл по j від 1

до n:
Сij = 0;
Цикл по k від 1 до p:
Сij замінити на Сij + АikBkj
Кінець циклу;
Кінець циклу;
Кінець циклу;
Кінець процедури.

Лекція 1. Алгоритми та рекурсія. Слайд 11 з 40

навіть необхідніше задавати за допомогою так званого «рекурсивного методу».

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

Лекція 1. Алгоритми та рекурсія. Слайд 12 з 40

1·2·3·...·n

Процедура Факторіал(n):
Якщо n = 0, то Факторіал(n) =

1;
Покласти Факторіал(n) = 1;
Цикл по k від 1 до n:
Значення Факторіал(n) замінити на k · (Факторіал(n));
Кінець циклу;
Кінець процедури.

Рекурсивне визначення функції «факторіал»:
Факторіал(0) = 1;
Факторіал (k + 1) = (k + 1) · Факторіал(k).

Процедура Факторіал(n):
Якщо n = 0, то Факторіал(n) = 1;
Якщо n > 0, то Факторіал(n) = n · Факторіал(n - 1);
Кінець процедури.

Лекція 1. Алгоритми та рекурсія. Слайд 13 з 40

5, 8, 13, 21 і 34 (кожен наступний є

сумою двох попередніх)
a1 = 1, a2 = 1, a3 = a1 + a2, … , an = an-2 + an-1

Алгоритм
Процедура Фіб(n):
Якщо n = 1, то Фіб(n) = 1;
Якщо n = 2, то Фіб(n) = 1;
Якщо n > 2, то Фіб(n) = Фіб(n-1) + Фіб(n-2);
Кінець процедури.

Лекція 1. Алгоритми та рекурсія. Слайд 14 з 40

та набір дисків різного діаметру. Диски нанизані на один

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

Лекція 1. Алгоритми та рекурсія. Слайд 15 з 40

перемістити єдиний диск із стрижня А на С;
Покласти В

= 6 - А - С;
Якщо n > 1, тоді
Змістити верхні n - 1 дисків на В, використовуючи Хан(А, B, n-1);
Змістити останній диск з А на С, використовуючи Хан(А, С, 1);
Змістити верхні n - 1 дисків на С, використовуючи Хан(B, С, n-1);
Кінець процедури.

Головоломку Ханойська вежа придумав французький математик Едуард Люка в 1883 р. Він зв’язував свою іграшку з міфічною легендою про значно більшу вежу Брами, яка, як стверджувалося, складалась з 64 дисків чистого золота, а стержні представляють собою три діамантових шпиля. При створенні світу Всевишній помістив диски на перший шпиль та велів, щоб жреці перемістили їх на третій у відповідності з визначеними правилами. За наявними відомостями жреці трудяться над цією задачею вдень і вночі – і як тільки вони завершать, башня розсиплеться в прах і наступить кінець світу.

Лекція 1. Алгоритми та рекурсія. Слайд 16 з 40

- множина цілих додатних чисел, а множина їх значень

- множина дійсних чисел.
Функція g мажорує функцію f, якщо існує дійсне число k і ціле додатне число m таке, що |f(n)| ≤ k|g(n)| для всіх n ≥ m.
Якщо g мажорує f, це позначається як f(n) = O(g(n)). Символ O(g(n)) читається як "О велике" від g(n); при цьому говорять, що f(n) має порядок О велике від g(n).

ТЕОРЕМА 4.1. Якщо r і s - дійсні числа, r ≤ s і n > 1, тоді nr ≤ ns. Отже, nr = O(ns).

Лекція 1. Алгоритми та рекурсія. Слайд 17 з 40



то cf(n) = О(g(n)).

ТЕОРЕМА 4.3. Якщо f(n)

= О(g(n)) і h(n)= О(g(n)), то (f+h)(n) = О(g(n))

ТЕОРЕМА 4.4. Якщо f(n) = О(g(n)) і h(n) = О(e(n)), то (f  h)(n) = О((g · e)(n)).

Лекція 1. Алгоритми та рекурсія. Слайд 18 з 40







В, m, n):
Цикл по i від

1 до m:
Цикл по j від 1 до n:
Cij = Aij + Bij ;
Кінець циклу;
Кінець циклу;
Додавання відбувається для кожного і та j. Оскільки i приймає m значень, а j приймає n значень, то виконується mn операцій додавання. Нехай N = max(m, n). Тоді число виконуваних арифметичних операцій має порядок О(N2).

Лекція 1. Алгоритми та рекурсія. Слайд 19 з 40

p, n)
Цикл по і від 1 до m:
Цикл по

j від 1 до n:
Сij = 0;
Цикл по k від 1 до p:
Сij замінити на Сij + АikBkj
Кінець циклу;
Кінець циклу;
Кінець циклу;
Кінець процедури.
Виконується mnp операцій додавання і mnp операцій множення. Отже, всього виконується 2mnp операцій. Нехай N = max(m, n, p). Порядок О(N3).

Лекція 1. Алгоритми та рекурсія. Слайд 20 з 40

до n-1:
Покласти min = i;
Цикл по j від 1

до n:
Якщо ai < amin, то нехай min = j;
Кінець циклу;
Поміняти місцями ai і amin;
Кінець циклу;

Задана послідовність

Крок 0: 2 ↔ 4

Крок 1: 3 ↔ 9

Крок 2: 4 ↔ 7

Крок 3: 6 ↔ 6

Крок 4: 7 ↔ 7

Лекція 1. Алгоритми та рекурсія. Слайд 21 з 40

n:
Цикл по j від n до i з кроком

-1:
Якщо aj < aj-1, то поміняти місцями aj і aj-1;
Кінець циклу;
Кінець циклу;
Кінець процедури.

і = 0

і = 1

і = 2

і = 3

і = 4

і = 5

Лекція 1. Алгоритми та рекурсія. Слайд 22 з 40

r = n;
Якщо l  r, то
Покласти m

= l і розбити список (al, al+1, al+2, ..., ar) на
S1, отриманий як {ai : ai  al, i  l}і
S2, отриманий як {ai : ai > al}, так що
S1 = (al, al+1, al+2, ···,aj) і S2 = (aj+1, aj+2, aj+3, ···,ar) після перепозначення;
Провести конкатенацію ШС(1, j), aт і ШC(j + 1, r);
Кінець процедури.

Лекція 1. Алгоритми та рекурсія. Слайд 23 з 40

процедури
Лекція 1. Алгоритми та рекурсія. Слайд 24 з 40

(польському) запису, якщо в ньому знак операції безпосередньо передує

операндам, на які вона діє.
Вираз знаходиться в суфіксному (постфіксному, або зворотному польському запису), якщо в ньому знак операції слідує безпосередньо за операндами, на які вона діє. Вираз знаходиться в інфіксному запису, якщо в ньому знак операції знаходиться між операндами, на які вона діє.

Арифметичний вираз знаходиться в повному дужковому запису, якщо кожному оператору в ньому відповідає пара дужок, в які вкладені оператор і ті операнди, на які він діє.

Лекція 1. Алгоритми та рекурсія. Слайд 25 з 40

здійснено за допомогою наступної процедури:
1. Додавати дужки у

вираз, поки він не стане повнодужковим.
2. Починаючи з самих внутрішніх дужок, видалити пару дужок і помістити оператор, що знаходиться усередині дужок на місце відповідне його правій дужці. За наявності більше однієї самої внутрішньої пари дужок починати потрібно з лівої пари.
3. Перейти до наступної пари дужок, вилучити її і помістити оператор, що знаходиться усередині дужок, на місце відповідне його правій дужці.
4. Продовжувати крок (3), поки всі дужки не будуть видалені.

Лекція 1. Алгоритми та рекурсія. Слайд 26 з 40

 (с + d) ^ x. Додаємо дужки, поки вираз не

стане повнодужковим. Одержуємо вираз ((а + b)  ((с + d) ^ x)). Виконавши крок (2), отримаємо (ab +  (cd + ^ х)). Виконавши крок (3), одержуємо (ab +  cd + х^). Повторюючи крок (3), приходимо до запису ab + cd + x ^ .

2. Нехай задано інфіксний вираз а  b + с  d. Додаємо дужки, поки не одержимо повнодужковий вираз, тобто вираз ((а  b) + (с  d)). Виконавши крок (2) одержимо (ab + cd)). Повторюючи крок (3), одержуємо ab  cd +.

Лекція 1. Алгоритми та рекурсія. Слайд 27 з 40

наступної процедури:
1. Починати зчитування виразу зліва направо.
2.

Якщо зчитаний символ не є символом операції, тоді помістити його в стек і продовжувати читання.
3. Якщо зчитаний символ є символом операції, то:
а) виштовхнути зі стека два верхні елементи;
б) помістити символ операції між другим і першим елементом із стека і поставити дужки;
в) помістити вираз, одержаний на кроці (б), знову в стек.
4. Продовжувати читання зліва направо і виконувати кроки (2) і (3) до завершення.

Лекція 1. Алгоритми та рекурсія. Слайд 28 з 40

оскільки це не символ операції, поміщаємо цей елемент в

стек, як показано на мал. 1. Потім прочитуємо b і, оскільки це не символ операції, поміщаємо його в стек, як показано на мал. 2.





мал.1 мал.2 мал.3
Далі зчитуємо с і, оскільки це не символ операції, поміщаємо його в стек, як показано на мал. 3.

Лекція 1. Алгоритми та рекурсія. Слайд 29 з 40

виштовхуємо із стека (видаляємо)
с (верхній елемент) і b

(наступний елемент),
поміщаємо  між b і с, як показано на мал.4. мал. 4
Поміщаємо (b  с) у стек, як показано на мал. 5. Далі зчитуємо + і, оскільки це символ операції, виштовхуємо із стека (видаляємо) (b  с) і а (наступний елемент). Поміщаємо + між а і (b  с), як показано на мал. 6.
Поміщаємо (а + (b  с)) в стек. Одержуємо шуканий вираз.




мал. 5 мал.6

Лекція 1. Алгоритми та рекурсія. Слайд 30 з 40

десятковій системі числення, в основі якої лежить число 10,

як
amam-1am-2 …a2a1a0
то
n = am10m + аm-110m-1 + … +a2102 + a110 + a0,
де aj - цифри від 0 і 9 для всіх 0  і  m.

3124 = 3(10)3 + 1(10)2 + 2(10) + 4.

Аналогічно, якщо число n подане в двійковій системі числення, в основі якої лежить число 2, то кожна цифра повинна бути або 1, або 0, і її значення визначається позицією в записі числа.
n = am2m + аm-12m-1 + … +a222 + a12 + a0

Лекція 1. Алгоритми та рекурсія. Слайд 31 з 40

+ 1· 22 + 0·21 + 1·20 =
=

24 + 22 + 1 = 16 + 4 + 1 = 21

Лекція 1. Алгоритми та рекурсія. Слайд 32 з 40

від’ємних чисел у двійковій та шістнадцятковій системах будується за

допомогою методу двійкового доповнення.
Цей метод вимагає, щоб цілі числа були записані з використанням фіксованої кількості бітів (двійкових розрядів).
Для представлення цілого додатнього числа за допомогою 8 біт перед ним при необхідності дописується потрібна кількість нулів.
Ціле додатнє число повинне починатися з 0, а ціле від’ємне – з 1. Оскільки при такому способі запису найбільше можнливо ціле додатнє число є 01111111, то всього є 127 цілих додатніх чисел. Якщо дано додатнє ціле число, представлене з використанням n біт, тоді відповідне йому від’ємне число знаходять шляхом віднімання цього числа з 2n, вираженому в двійковій формі. Це здійснюється відніманням числа з 2n-1 (знаходження 1-го доповнення) і додаванням 1.

Лекція 1. Алгоритми та рекурсія. Слайд 34 з 40

доповненні. Спочатку число 56 представляється як 00111000. Віднімачи його

з 11111111 отримуємо 11000111. Додавання 1 дає 11001000, так що -56 має представлення 11001000.

Знайти представлення в шістнадцятковій системі числення заперечення шістнадцяткового числа 78F з використанням 16 біт. Спочатку замінимо запис числа на 16-бітне число 078F. Потім віднімемо 078F з FFFF, отримаємо F870, і далі додаємо 1. В результаті отримуємо представлення F871.

Лекція 1. Алгоритми та рекурсія. Слайд 35 з 40

n позначається через det (A), A або






і визначається наступним

чином
а) якщо п = 1, то det (A) = A11 = А11;
б) якщо n  2, то det (A) = А1j (-1)1+j det (А1j)
Нехай Мij = det(Aij). Число Мij називається мінором елемента Aij,
а число Сi = (-1)і+j det ( Aij ) - алгебраїчним доповненням
елемента Aij. Отже det (A) = А1j (-1) 1+j det (А1j) = А1j С1j

Лекція 1. Алгоритми та рекурсія. Слайд 36 з 40

n  n, де Iij = ij , тобто

на діагоналі матриці In стоять одиниці, а вся решта її елементів дорівнюють нулю. Матриця In називається одиничною матрицею розміру n  n, або просто одиничною матрицею. Одинична матриця володіє тією властивістю, що для будь-якої матриці А розміру n  n має місце рівність АIn = InA = А.

Нехай А - матриця розміру n  n. Мультиплікативно оберненою, або просто оберненою до матриці А називається матриця А-1, яка володіє (якщо вона існує) тією властивістю, що АА-1 = А-1А = In.

Лекція 1. Алгоритми та рекурсія. Слайд 37 з 40

x n
1. Знайти det(A). Якщо він рівний нулю,

обернена матриця не існує.
2. Для кожного Aij знайти доповнення алгебри Cij і сформувати матрицю С = [Сij ], що називається матрицею алгебраїчних доповнень.
3. Знайти матрицю С t, транспоновану до матриці С, так що С tij = Cji . Матриця С t називається спряженою до матриці А і позначається adj (A).
4. Розділити кожен елемент спряженої матриці adj(A) на det(A).
5. А-1 = adj(A).

Лекція 1. Алгоритми та рекурсія. Слайд 38 з 40

Пер. с англ.. – М.: Изд. дом «Вильямс», 2003.

– 960 с.
Грэхем Р., Кнут Д., Паташник О., Конкретная математика. Основание информатики: Пер. с англ. – М.: Мир, 1998. – 703 с.
Співаковський О.В., Львов М. С. Основи алгоритмізації та програмування: Навчальний посібник. - Херсон, 1997.- 140 с.
Матеріали сайту: http://algolist.manual.ru/