Поможем написать учебную работу
Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
- формалізація сформованої задачі;
- розроблення алгоритму розвязку задачі;
- написання налагоджування і тестування програми;
- отримання результату розвязку задачі на ЕОМ.
Сортування вставками:
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
(в завданні опечатка!!! 220 замість 210)
Порядок: 10002 = 106
Розвязання:
Згідно визначення необхідно знайти такі константи і , щоб нерівність виконувалась для всіх . Розділимо останню нерівність на : . Остання умова розпадається на дві нерівності і .
Для виконання другої нерівності достатньо взяти . Перша нерівність буде виконана, якщо . Тоді .
Відповідь: а1=1\14; а2=1\2; n=7.
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
(Для справки: щоб знайти найбільший і найменший елементи треба виконати порівнянь )
Розвязання:
Нехай приймає довільне значення. Тоді , , . Допустимо, що . Тоді , , , …
Шляхом послідовного підставлення знаходимо, що
,
,
Останній вираз подамо у такому вигляді: .
Для довільного k, будемо мати .
Допустимо, що . Тоді . Оскільки , то при
.
Перший доданок суми, яка є правою частиною останнього співвідношення - , а другий доданок це геометрична прогресія, в якої перший член ; знаменник прогресії - , а кількість її членів дорівнює .
Тому .
Враховуючи значення , маємо .
Таким чином, розвязком рекурентних співвідношень є функція за умови, що , де - ціле додатне число.
Відповідь: T(n)=(3/2)*n-2.
Розвязання:
Нехай аргумент приймає будь-яке ціле значення , яке , тобто .
Тоді матимемо при : , , , , …
Здійснюючи послідовну підстановку отриманих значень отримаємо:
,
,
.
Процес підставлення можна продовжувати до досягання у правій частині отриманих послідовностей . Аналіз отриманої послідовності показує, що , тобто коефіцієнт при співпадає з показником степеня числа, яке є знаменником аргумента . Крім того .
У загальному випадку . Нехай .
Тоді .
Проведений аналіз показав, що при поділі списку кожний раз на половину . Звідси випливає, що . Оскільки , то .
Сума у останній формулі є геометричною прогресією, знаменник якої . Тому . Оскільки і , то.
Таким чином, .
Відповідь: T(n)=n*log2n-n+1.
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
Розвязання:
Класичний алгоритм: операцій множення, тобто маємо 20*20*20=8000
Алгоритм Винограда: операцій множення, тобто маємо (203+2*202)/2=4400
Алгоритм Штрасена: операцій множення, тобто маємо 202,81=4528
Відповідь: 8000, 4400, 4528
Розвязання:
Класичний алгоритм: операцій додавання, тобто маємо 20*19*20=7600
Алгоритм Винограда: операцій додавання, тобто маємо (3*203+4*202-4*20)/2=12760
Алгоритм Штрасена: операцій додавання, тобто маємо 6*202,81-6*202=24767
Відповідь: 7600, 12760, 24767
Розвязання:
, кількість операцій множення: 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.
(опечатка!!! -)
Розвязання: К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]
Розвязання:
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 Знову помилка. Ну не піздєц???
Розвязання:
, .
det A = 2*4-3=5, A11=4, A12=-3, A21=-1, A22=2.
Відповідь: X= [0,8 -0,2] [-0.6 0.4]
Розвязання:
, . Так, як 214=16384<20000, a 215=32768>20000, то (k+1)=15, k=14.
Відповідь: 14
Розвязання:
Відповідь: а) 9,7656*10(-4).
Метод Ньютона-Рафсона
Розвязання:
А фіг його знає, як «це» робити. Береш формулу , підставляєш значення і маєш щастя.
Відповідь: 0,50000; 0,5663; 0,5671
( для справки: - модифікований метод Ньютона, - дискретний (- матриця Якобі, в якій часткові похідні замінені різницевими відношеннями) )
( для справки: у методі Гюна використовується ітераційна процедура: , , )
( для справки: при а=1 маємо метод середньої точки )
(опечатка!!! третього замість четвертого)
( для справки: в методі Рунге-Кутта четвертого порядку використовується ітераційна процедура: , , , , )
Розвязання:
, . З умови видно, що h=0,5, тоді , , .
Відповідь: y0=0; y1=0; y2=0.3536; y3= 1,0303
( для справки: лінійні інтегральні рівняння другого роду Фредгольма - )
Використанням точніших квадратурних формул
Розвязання:
, , ; , , .
Відповідь: а11=1- А1Q11, a21= -AQ21, a22=1-A2Q22, b1=f1
Розвязання:
, , ; , , .
Відповідь: a11=1 1-YA1 Q11- 1 a12= - YA2Q12, a13= YA3Q13, b1=f1
( для справки: - параболічне, - гіперболічне. Якщо рівняння звести до виду, де b=0, то якщо постійні коефіцієнти при похідних другого порядку мають одинакові знаки в одній частині рівняння, то таке рівняння еліптичне; якщо різні гіперболічне; якщо похідна другого порядку за однією із змінних відсутня (b = 0; ас = 0 при ) параболічне. )
( для справки: якщо або , то P(x) називають значенням екстраполяції )
Розвязання:
Відповідь1: а0=1. а1=0.2. а2= - 0.632 Відповідь2: a0=1; a1=3; a2=0.8
Розвязання:
Якщо функцію взяти у вигляді , виходячи із умов інтерполяції, отримуємо систему із лінійних рівнянь: …
,
,
Відповідь: a1=-0.3627; b1=2.3279; a2=-0.6102; b2=3.0705
Розвязання:
При кусково-квадратичній інтерполяції функція вибирається у вигляді - . При кожна ланка кусково-квадратичної функції визначається трійкою коефіцієнтів , і , послідовним розвязком трьохвимірних лінійних систем:
де .
Отримаємо систему:
, .
Розвяжемо систему відносно трьох невідомих методом Гаусса:
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 Щось не добре!!
вхідні дані спотворені похибками вимірювань
Розвязання:
, .
Відповідь: а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).
Розвязання:
Перші похідні: , .
Другі похідні: , ,
Матриця Гессе:
Відповідь: б) [ 2+x22 e -x1x2 e-x1x2(x1x2-1) ] [ e-x1x2(x1x2-1) x12-x1x2 ]
Розвязання:
Для закритого циліндра повна поверхня рівна: .
Обєм циліндра: .
Із формули площі виразимо висоту: .
Підставимо її в формулу для знаходження обєму: .
Якщо увести позначення і , то .
Необхідна умова екстремуму функції: .
.
Звідси маємо: , .
Маючи радіус, знайдемо висоту: .
Відповідь: в)D=1.303; h=1.303.
Розвязання:
Для закритого циліндра повна поверхня рівна: .
Обєм циліндра: .
Із формули обєму виразимо висоту: .
Підставимо її в формулу для знаходження площі: .
Якщо увести позначення і, то .
Необхідна умова екстремуму функції: .
. Звідси маємо: .
Домножимо вираз на x2: , , .
; .
Відповідь: б) D=2.1677; h= 2,1677.
Розвязання:
Для прямого паралелепіпеда із квадратом в основі повна поверхня рівна: .
Обєм: . Із формули площі виразимо висоту: .
Підставимо її в формулу для знаходження обєму: .
Якщо увести позначення і , то .
Необхідна умова екстремуму функції: .
.
Звідси маємо: , ..
Відповідь: д)а=5дм. h=5 дм.
( для справки: Необхідні і достатні умови у задачі безумовної мінімізації: Допустимо, що функція неперервна на інтервалі і має першу і другу похідні. Тоді, якщо мають місце умови , , то у точці функція має локальний мінімум. )
( для справки: Функція унімодальна на відрізку , якщо існує єдина точка така, що для будь-яких і . , якщо ; , якщо .
)
( для справки: числа Фібоначчі отримують із співвідношення: , , )
Розвязання:
Ряд Фібоначі: 1 2 3 5 8 13 21 34 55 89 144 … Так, як 89<100<144, максимальним треба вибрати число 144.
Відповідь: в)144.
Метод Фібоначчі має наступні недоліки:
Розвязання:
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), то для прикладу було вибрано x(0)=(1; 2) тому відповідь відрізняється від результату!!!)
Відповідь: г) Х(1)= (- 0.6 , -0.2)
а)
Методи, які застосовують для розвязку задач бузумовної мінімізації , можна ранжувати наступним чином ( у порядку зменшення їх ефективності): в) якщо вірно 3,2,1.
( Пояснення: найкрутішими є ньютонівські методи (з урахуванням других похідних), потім ідуть квазіньютонівські (з урахуванням градієнтів), за ними методи спряжених градієнтів, а аутсайдерами залишаються методи прямого пошуку. )
Увага!!! Тут НЕМАЄ тестів по ВОСЬМІЙ темі!!!
PAGE 1
EMBED Equation.3