1i 7 ii1 8 if i0 then brek 9 end while 10 i1key 11 end for У найсприятливішому випадку час роботи алгор
Работа добавлена на сайт samzan.net:
Поможем написать учебную работу
Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
от 25%
Подписываем
договор
Перевір себе (тести на екзамен з амо)
- Процес створення комп’ютерної програми для розв’язку певної інженерної задачі складається із таких етапів:
- формалізація сформованої задачі;
- розроблення алгоритму розв’язку задачі;
- написання налагоджування і тестування програми;
- отримання результату розв’язку задачі на ЕОМ.
- Яка із наведених процедур сортування даних (sort) є вірною?
Сортування вставками:
1 n=length(A)
2 for j=2 to n
3 key=A(j)
4 i=j-1
5 while i>0 and A(i)>key
6 A(i+1)=A(i)
7 i=i-1
8 if i=0 then break
9 end while
10 A(i+1)=key
11 end for
- У найсприятливішому випадку час роботи алгоритму сортування вставками визначається функцією:
- У найгіршому випадку час роботи алгоритму сортування вставками визначається функцією: (в відповідях є опечатка опечатка!!! – n3 замість n2 )
- Час роботи алгоритму визначають у найгіршому випадку
- Якщо алгоритм обробляє вхідні дані розміром n за час, де с – деяка постійна величина, то складність такого алгоритму буде:
- Визначити порядок складності алгоритму, якщо , n=210. Порядок: 210*10 = 10240
(в завданні опечатка!!! – 220 замість 210)
- Визначити порядок складності алгоритму , якщо при обсягу вхідних даних 1000.
Порядок: 10002 = 106
- Якщо деяка функція, то запис означає, що знайдуться такі , і таке , що для всіх .
- Час роботи деякого алгоритму оцінюється наступним чином: . Знайти такі константи: ,, .
Розв’язання:
Згідно визначення необхідно знайти такі константи і , щоб нерівність виконувалась для всіх . Розділимо останню нерівність на : . Остання умова розпадається на дві нерівності і .
Для виконання другої нерівності достатньо взяти . Перша нерівність буде виконана, якщо . Тоді .
Відповідь: а1=1\14; а2=1\2; n=7.
- Яка із наведених процедур знаходження найбільшого елементу множин S (max) є вірною?
1 n=length(S)
2 Вибираємо довільний елемент із множини S
3 max=S(1)
4 for i=2 to n
5 x=S(i)
6 if x>max
7 then max=x
8 end if
9 end for
(Для справки: щоб знайти найбільший і найменший елементи треба виконати порівнянь )
- Знайти розв’язок рекурентного співвідношення , яке характеризує складність алгоритму знаходження найменшого і найбільшого елементів із множини S.
Розв’язання:
Нехай приймає довільне значення. Тоді , , . Допустимо, що . Тоді , , , …
Шляхом послідовного підставлення знаходимо, що
,
,
Останній вираз подамо у такому вигляді: .
Для довільного k, будемо мати .
Допустимо, що . Тоді . Оскільки , то при
.
Перший доданок суми, яка є правою частиною останнього співвідношення - , а другий доданок – це геометрична прогресія, в якої перший член ; знаменник прогресії - , а кількість її членів дорівнює .
Тому .
Враховуючи значення , маємо .
Таким чином, розв’язком рекурентних співвідношень є функція за умови, що , де - ціле додатне число.
Відповідь: T(n)=(3/2)*n-2.
- Знайти розв’язок рекурентного співвідношення , яке характеризує складність алгоритму сортування даних злиттям.
Розв’язання:
Нехай аргумент приймає будь-яке ціле значення , яке , тобто .
Тоді матимемо при : , , , , …
Здійснюючи послідовну підстановку отриманих значень отримаємо:
,
,
.
Процес підставлення можна продовжувати до досягання у правій частині отриманих послідовностей . Аналіз отриманої послідовності показує, що , тобто коефіцієнт при співпадає з показником степеня числа, яке є знаменником аргумента . Крім того .
У загальному випадку . Нехай .
Тоді .
Проведений аналіз показав, що при поділі списку кожний раз на половину . Звідси випливає, що . Оскільки , то .
Сума у останній формулі є геометричною прогресією, знаменник якої . Тому . Оскільки і , то.
Таким чином, .
Відповідь: T(n)=n*log2n-n+1.
- Алгоритми сортування даних злиттям використовують стратегію розділяй і володарюй (поділ складної задачі на простіші підзадачі).
- Складність аглоритму сортування вставками (опечатка в умові!!! - не вставками, а злиттям!!!) : - для злиття, для вставок - .
- Для розв’язку задачі комівояжера використовують стратегію жадібні алгоритми (на кожному кроці забезпечує локально найкращий вибір).
- Задачу тріангуляції розв’язують, використовуючи стратегію динамічне програмування (процес заповнення таблиці для отримання розв’язку певної задачі).
- Стандартний алгоритм множення двох матриць А і В розмірами mxr i rxn має наступний вигляд:
1 Визначити розміри матриць А і В – m,r,n
2 for i=1 to m
3 for j=1 to n
4 C(i,j)=0
5 for k=1 to r
6 C(i,j)=C(i,j)+A(i,k)*B(k,j)
7 end for
8 end for
9 end for
- Задані дві матриці розмірами 10x5 і 5x5. Скільки операцій множення необхідно виконати щоб отримати добуток цих двох матриць? Відповідь: 10х5х5=250
- Перемножуються дві квадратні матриці розміром n=20. Скільки операцій множення необхідно здійснити, якщо використовувати класичний алгоритм, алгоритм Винограда, алгоритм Штрассена?
Розв’язання:
Класичний алгоритм: операцій множення, тобто маємо 20*20*20=8000
Алгоритм Винограда: операцій множення, тобто маємо (203+2*202)/2=4400
Алгоритм Штрасена: операцій множення, тобто маємо 202,81=4528
Відповідь: 8000, 4400, 4528
- Перемножуються дві квадратні матриці розміром n=20. Скільки операцій додавання необхідно здійснити, якщо використовувати класичний алгоритм, алгоритм Винограда, алгоритм Штрассена?
Розв’язання:
Класичний алгоритм: операцій додавання, тобто маємо 20*19*20=7600
Алгоритм Винограда: операцій додавання, тобто маємо (3*203+4*202-4*20)/2=12760
Алгоритм Штрасена: операцій додавання, тобто маємо 6*202,81-6*202=24767
Відповідь: 7600, 12760, 24767
- Знайти кількість операцій множення при перемноженні трьох матриць, розміри яких відповідно 20х10, 10х5, 2х20.
Розв’язання:
, кількість операцій множення: 20*10*5=1000, розмірність отриманої матриці: 20х5
, кількість операцій множення: 2*20*5=200
Загальна кількість операцій множення: 1000+200=1200
Відповідь: 3000 - опечатка в умові!!! – остання матриця має розмірність 20х20, а не 2х20, тоді кількість операцій множення для буде рівна 5*20*20=2000, а загальна кількість операцій множення – 1000+2000=3000.
- Який метод використовують для розв’язку FFT-задачі? Розділяй і володарюй.
- За якою формулою визначають дискретне перетворення Фур’є?
(опечатка!!! -)
- Яке із наведених рівнянь відповідає поданню системи алгебраїчних лінійних рівнянь у матрично-векторній формі? Аx=b
- Чим зумовлена непридатність методу Крамера для розв’язку системи лінійних алгебраїчних рівнянь з великим числом невідомих? Тим, що число ітерацій пропорційно факторіалу числа невідомих.
- Систему алгебраїчних лінійних рівнянь з великим числом невідомих розв’язують методом прямого ходу Гауса.
- Матрицю А= [ 1 3 2 ] [4 6 5 ] [7 2 9 ] привести до верхнього трикутного вигляду.
Розв’язання: К1: А=[1 3 2] [0 -6 -3] [0 -19 -5]; К2: А= [1 3 2 ] [0 -6 -3] [0 0 ((-19)/6)*(-3)-5].
Відповідь: А= [1 3 2 ] [0 -6 -3] [0 0 4.5]
- Використовуючи результати п.6, знайти розв’язок системи лінійних алгебраїчних рівнянь X1+3X2+2X3=20, 4X1+6X2+5X3=47, 7Х1+2Х2+9Х3=58.
Розв’язання:
4,5 X3=22,5, X3=5
-6 X2 -15=-33, X2=3
X1+9+10=20, X1=1
Відповідь: x1=1; x2=4; x3=6 – Знову помилка. Ну не піздєц???
- Знайти матрицю обернену до матриці А= [2 1] [3 4] як розв'язок матричного рівняння .
Розв’язання:
, .
det A = 2*4-3=5, A11=4, A12=-3, A21=-1, A22=2.
Відповідь: X= [0,8 -0,2] [-0.6 0.4]
- Якщо виконується умова , то кількість дійсних коренів рівняння f(x)=0 на інтервалі непарне число
- Якщо виконується умова , то кількість дійсних коренів рівняння f(x)=0 на інтервалі парне число
- Знайдіть максимальну кількість інтерацій необхідних для розв'язку алгебраїчного рівняння f(x)=0 з точність E=10-4, якщо а=2, b=4.
Розв’язання:
, . Так, як 214=16384<20000, a 215=32768>20000, то (k+1)=15, k=14.
Відповідь: 14
- Корінь функції f(x) = -x3 * e - 0.8e + cos(x) шукали на інтервалі ( 0, 2) методом дихотомії. Оцінити похибку знаходження кореня на цьому інтервалі, якщо було здійснено 10 ітерацій.
Розв’язання:
Відповідь: а) 9,7656*10(-4).
- Який із трьох методів - дихотомії, хорд, Ньютона-Рафсона має найвищу збіжність?
Метод Ньютона-Рафсона
- Яка із наведених формул визначає ітераційний процес розв’язку рівняння f(x)=0 у методі Ньютона-Рафсона? .
- Знайти три перші значення Хк за допомогою ітераційного процесу розв’язку рівняння e(-3)-x=0 методом Ньютона-Рафсона, якщо х0=0.
Розв’язання:
А фіг його знає, як «це» робити. Береш формулу , підставляєш значення і маєш щастя.
Відповідь: 0,50000; 0,5663; 0,5671
- Метод хорд збігається до розв'язку нелінійного алгебраїчного рівняння f(x)=0 значення швидше ніж метод дихотомії у тому випадку коли f(x) близька до лінійної функції.
- Яка із наведених формул визначає ітераційний процес розв’язку рівняння f(x)=0 y модифікованому методі січних?
- Формула визначає метод Ньютона для розв’язку систем нелінійних рівнянь.
( для справки: - модифікований метод Ньютона, - дискретний (- матриця Якобі, в якій часткові похідні замінені різницевими відношеннями) )
- У методі Ейлера використовується наступна ітераційна процедура: , .
- Метод Ейлера розв'язання диференціальних рівнянь дає похибку першого порядку .
- Метод Гюна розв'язання диференціальних рівнянь дає похибку другого порядку .
( для справки: у методі Гюна використовується ітераційна процедура: , , )
- Якщо n ітераційні процедури Рунге-Кутта а=0.5 , то маємо метод Хойна.
( для справки: при а=1 маємо метод середньої точки )
- Метод Рунге-Кутта розв'язання диференціальних рівнянь дає похибку четвертого порядку
(опечатка!!! – третього замість четвертого)
( для справки: в методі Рунге-Кутта четвертого порядку використовується ітераційна процедура: , , , , )
- Задане диференціальне рівняння . Знайти значення y(t) при t=[0.5; 1.0; 1. 5] якщо y(0)=0. Для розв'язку задачі використати метод Ейлера.
Розв’язання:
, . З умови видно, що h=0,5, тоді , , .
Відповідь: y0=0; y1=0; y2=0.3536; y3= 1,0303
- Задане диференціальне рівняння . Знайти значення y(t) при t=[0.5; 1.0; 1.5]. якщо у(0)=0.1. Для розв’язку задачі використати метод Ейлера. у(0)=0.1, у(1)= 0.2581, у(2)=0.5767. - (див. 46)
- Інтегральне рівняння носить назуву інтегральне рівняння Вольтеррі.
( для справки: лінійні інтегральні рівняння другого роду Фредгольма - )
- Яку назву мають інтегральні рівняння з зміною верхньою межею інтегрування? Вольтеррі
- Як підвищити точність розв'язку інтегрального рівняння при використанні числових методів?
Використанням точніших квадратурних формул
- Яку підвищену точність, з використанням числових методів розв'язку інтегрального рівняння, забезпечують методи обчислення визначених інтегралів? Використання формули Сімпсона
- Записати квадратурну формулу для наближеного обчислення інтегрального рівняння Вольтеррі, якщо t=2
Розв’язання:
, , ; , , .
Відповідь: а11=1- А1Q11, a21= -AQ21, a22=1-A2Q22, b1=f1
- Записати квадратурну формулу для наближеного обчислення інтегрального рівняння Фредгольма другого роду, якщо і=1, n=3.
Розв’язання:
, , ; , , .
Відповідь: a11=1 1-YA1 Q11- 1 a12= - YA2Q12, a13= YA3Q13, b1=f1
- Якщо , то диференціальне рівняння у часткових похідних носить назву еліптичного.
( для справки: - параболічне, - гіперболічне. Якщо рівняння звести до виду, де b=0, то якщо постійні коефіцієнти при похідних другого порядку мають одинакові знаки в одній частині рівняння, то таке рівняння – еліптичне; якщо різні – гіперболічне; якщо похідна другого порядку за однією із змінних відсутня (b = 0; ас = 0 при ) – параболічне. )
- Інтерполяція - це процес побудови інтерполяційної функції, з метою знаходження проміжних значень табличної функції.
- Коли , наближення P(x) називають значенням інтерполяції.
( для справки: якщо або , то P(x) називають значенням екстраполяції )
- За якою із наведених формул визначають інтерполяційний поліном Лагранжа ?
- Для табличних значень функції f(x) обчислити коефіцієнти інтерполяційного полінома Лагранжа PN(x)
Розв’язання:
Відповідь1: а0=1. а1=0.2. а2= - 0.632 Відповідь2: a0=1; a1=3; a2=0.8
- На системі вузлів x=[ 2;3;4] відомі значення функції f(x)= [1,60; 1,24; 0,63]. Апроксимуйте функцію f(x) на заданому інтервалі, використавши кусково-лінійну апроксимацію.
Розв’язання:
Якщо функцію взяти у вигляді , виходячи із умов інтерполяції, отримуємо систему із лінійних рівнянь: …
,
,
Відповідь: a1=-0.3627; b1=2.3279; a2=-0.6102; b2=3.0705
- На системі вузлів x= [2,3,4] відомі значення функції f(x)= [2,1074: 2,8307; 3,3863]. Апроксимуйте функцію f(x) на заданому інтервалі, використавши кусково-квадратичну апроксимацію.
Розв’язання:
При кусково-квадратичній інтерполяції функція вибирається у вигляді - . При кожна ланка кусково-квадратичної функції визначається трійкою коефіцієнтів , і , послідовним розв’язком трьохвимірних лінійних систем:
де .
Отримаємо систему:
, .
Розв’яжемо систему відносно трьох невідомих методом Гаусса:
2a1=-0,1677, a1=-0,08385
b1-0,41925=0,7233, b1=1,1358
c1+2,2716-0,3354=2,1074, c1=0,1712
Відповідь: a1= -2,1074; b1=2,8307; C1= -3,3863 – Щось не добре!!
- У яких випадках застосовують кубічний сплайн? масив вхідних даних має велику розмірність
- Кубічний сплайн має дефект 1
- У яких випадках застосовують наближення функцій методом найменших квадратів?
вхідні дані спотворені похибками вимірювань
- Знайти параметри моделі y=a0+a1x за даними, які наведені у табл. використавши метод найменших квадратів
Розв’язання:
, .
Відповідь: а0=2.0403. а1= 4.9858
- Яка із наведених формул визначає параметри моделі лінійної відносно своїх параметрів ?
а= M(-1) F(T) Y
66. Чи має функція z= 4x2 + 2xy + y2-12x-6y+2 мінімум?
Розв’язання:
; ; .
Отже, функція має критичну точку M(1, 2). Перевіримо, чи критична точка є екстремумом функції, виходячи із правила:
, , .
16-4=12>0. Тому точка М є точкою екстремуму, а так, як А=8>0, то М – точка мінімуму.
Відповідь: а) має у точці ( 1,2).
- Для функції f(x)=x12+ e -x1x2 матриця Гессе буде такою.
Розв’язання:
Перші похідні: , .
Другі похідні: , ,
Матриця Гессе:
Відповідь: б) [ 2+x22 e -x1x2 e-x1x2(x1x2-1) ] [ e-x1x2(x1x2-1) x12-x1x2 ]
- Ємність має форму закритого циліндру, повна поверхня якої дорівнює 8 м2.Знайти геометричні розміри ємності (висоту Н та діаметр D) такі, щоб об'єм ємності був максимальним.
Розв’язання:
Нема!!!
Відповідь: в)D=1.303; h=1.303.
- Ємність має форму закритого циліндру, об’єм якої дорівнює 8 м3. знайти геометричні розміри ємності (висоту h та діамтр D) такі, щоб повна поверхня ємності була б мінімальною.
Розв’язання:
Нема!!!
Відповідь: б) D=2.1677; h= 2,1677.
- Ємність має форму прямого паралелепіпеда, верхня і нижня гарні якого - квадрати. Повна поверхня такої ємності S= 125 дм2. Знайти геометричні розміри ємності( висоту h та довжину сторін квадрата а) такі, щоб об'єм ємності був би мінімальним.
Розв’язання:
Нема!!!
Відповідь: д)а=5дм. h=5 дм.
- Необхідні і достатні умови у задачі безумовної мінімізації в) f ' (x)=0 , f ' (x)>0.
( для справки: Необхідні і достатні умови у задачі безумовної мінімізації: Допустимо, що функція неперервна на інтервалі і має першу і другу похідні. Тоді, якщо мають місце умови , , то у точці функція має локальний мінімум. )
- Числові методи знаходять однозначний мінімум функції для випадку, якщо б) функція - унімодальна.
( для справки: Функція унімодальна на відрізку , якщо існує єдина точка така, що для будь-яких і . , якщо ; , якщо .
)
- Яка із наведених послідовностей є числами Фібоначчі? г)1 2 3 5 8 13 21 34.
( для справки: числа Фібоначчі отримують із співвідношення: , , )
- Шукали мінімум функції f(x)= e(-x) + x2 на інтервалі [0,1] методом пошуку Фібоначчі з точністю E=10-2. Яке максимальне число Фібоначчі слід вибрати, щоб забезпечити задану точність розв'язку задачі.
Розв’язання:
Ряд Фібоначі: 1 2 3 5 8 13 21 34 55 89 144 … Так, як 89<100<144, максимальним треба вибрати число 144.
Відповідь: в)144.
- Шукали мініум функції f(x) = e(-2) + x2 на інтервалі ( 0, 1 ) методом пошуку Фібоначчі з точністю E=10(-1). Яке максимальне число Фібоначчі слід вибрати, щоб забезпечити задану точність? 13 (8<10<13).
- На наведене твердження одна або декілька відповідей мають бути вірними? в)якщо вірно тільки 2,3
Метод Фібоначчі має наступні недоліки:
- оперує лише з додатніми інтервалами;
- важко налаштувати на критерій зупину, який вимагає, щоб значення функції на кінцевому інтервалі Iε відрізнялось би від Iε не більше, ніж на задану величину ε.
- Метод золотого січення пошуку мінімуму функції однієї змінної використовує поділ початкового інтервалу у пропорції а) .
- Шукали мінімум функції f(x)=e-2+x2 на інтервалі [0;1] методом золотого січення. Який новий інтервал було вибрано після закінчення першої ітерації обчислень?
Розв’язання:
f(0)= e-2 , f(1)= e-2 + 1. f(0)< f(1), тому стискаємо справа: [0,0; 0,618].
Відповідь: б) [0,0; 0,618].
- Як здійснюється вибір довжини кроку в градієнтних методах? в)
- Усі градієнти методи мають таку узагальнюючу схему:
1.К3. Розрахувати ненульовий n-мірний вектор р , названий напрямком пошуку.
2.К2. Перевірити умови зупинок, і якщо вони виконуються, обчислення припинити і прийняти х ( на першому кроці обчислень к=0) як розв’язок задачі, в іншому ж випадку перейти до наступного кроку)
( Пояснення: Узагальнена схема градієнтних методів:
K1. Вибрати початкову (стартову) точку .
K2. Перевірити умови зупинок, і якщо вони виконуються, обчислення припинити і прийняти (на першому кроці обчислень ) як розв’язок задачі, в іншому ж випадку перейти до наступного кроку.
K3. Розрахувати ненульовий n-мірний вектор , названий напрямком пошуку.
K4. Вирахувати додатне число (довжину) кроку, яке забезпечить виконання нерівності . Обчислити .
K5. Замінити на і на і перейти до кроку 2. Хоча узагальнююча схема розв’язку задачі оптимізації і гарантує одержання монотонно спадної послідовності , це не означає, що така послідовність завжди сходиться до екстремальної точки . )
- В інтервальному процесі, який реалізує пошук мінімуму функції методом найвищого спуску , були вибрані такі параметри процесу: початкова точка - x(0)=(1.2); довжина кроку - Y=0.5. Якого значення набула точка Х(1).
Розв’язання:
.
, , , .
(Так, як в умові нема x(0), то для прикладу було вибрано x(0)=(1; 2) тому відповідь відрізняється від результату!!!)
Відповідь: г) Х(1)= (- 0.6 , -0.2)
- У методі Ньютона пошуку мінімуму функції реалізована наступна ітераційна процедура:
а)
- На наведене твердження одна або декілька відповідей мають бути вірними
Методи, які застосовують для розв’язку задач бузумовної мінімізації , можна ранжувати наступним чином ( у порядку зменшення їх ефективності): в) якщо вірно 3,2,1.
( Пояснення: найкрутішими є ньютонівські методи (з урахуванням других похідних), потім ідуть квазіньютонівські (з урахуванням градієнтів), за ними методи спряжених градієнтів, а аутсайдерами залишаються методи прямого пошуку. )
- На наведене твердження одна або декілька відповідей мають бути вірними. г) якщо вірно 4,2,1,3,5.
Увага!!! Тут НЕМАЄ тестів по ВОСЬМІЙ темі!!!
PAGE 10
EMBED Equation.3