Метод Рунге-Кута 4-го порядку

Читайте также:

Вирішує диференційне рівняння 1-го порядку при заданих початкових умовах x0,y(x0), y(x0)

Для обрахунку значення y(x):

• Діапазон значень від х0 до х розбивається на частини (n відрізків);

• Для кожного відрізка обраховується приріст функції та додається до попереднього значення.

23. Що таке регулярний вираз? У реалізації яких задач застосовуються регулярні вирази?

Регулярний вираз -це текстовий рядок який описує шаблон деякого текста.

Застосовується для пошуку та синтаксичного аналізу текста.

24. За якими правилами формуються регулярні вирази?

Регулярні вирази повинні складатися з:

- Символів все, крім спец символів - будь який символ за виключенням спеціальних

- Метасимволів |, \d,., () - це елементи регулярного виразу які управляють роботою регулярного виразу

- класа символів [0-9]

- квантифікаторів?, +, *, {min,max} - це елементи регулярного виразу, які вказуються після класу символів і показують кількість входжень символів з класу.

25. Як чином організована робота з регулярними виразами в мові програмування Java2?

Потрібно бібліотеку java.util.regex

Pattern patr=Pattern.compile("^#([0-9]*|[A-F]*)@#([0-9]*|[A-F]*)$");

Matcher match=patr.matcher(“#abc@#123”);

if(match.find())

Pattern patr=Pattern.compile("[;.]");

strLine = patr.split(“a;as.sad 324”);

- Створили рядок стрінг з регулярним виразом, потім передали його у статичний метод complite() класу Pattern, на основі результату буде створений об’єкт.

- Асоціювати регулярний вираз з текстом (метод matcher() класу Pattern)

- Метод find() класу Matcher вказує, чи текст відповідає заданому шабону регулярного виразу

- Метод split() класу Pattern дає можливість розділити рядок символів, за шаблоном регулярного виразу і повернути масив стрінг.

26. Що таке скінчений автомат? У яких областях застосовується скінчений автомат?

Кінцевий автомат -абстрактний автомат без вихідного потоку, число можливих станів якого скінчене. Результат роботи автомата визначається за його кінцевий стан.

Кінцевий автомат – це певний підхід до ідентифікації об’єкта.

- Розробка ПЗ моделі поведінки цифрових пристроїв

- Проведення лексичного аналізу мови програмування (компілятори)

- Розробка ПЗ для обробки і пошуку інформації на web-сторінці

- Розробка ПЗ для верифікації системи, які мають кінцеве число різних станів (комутація, криптографія і т.д.)

Автомат Мілі – це впорядкована пятірка {Q,X,Y,fq,gq}.

Q – множина станів атомата.

X – це алфавіт вхідних символів.

Y – це алфавіт вихідних символів.

fq – це функції перехода (Q*X=Q)

gq – це функції виходу (Q*X=Y)

27. Як можна класифікувати автомат?

1.Якщо з множини станів автомату можна виділити деякий стан q₀, називаємий початковим, то автомат називається Ініціальним

2.В залежності від визначення множини станів, алфавітів вхідних і вихідних символів автомати бувають:

2.1.Кінцевими (якщо всі три множини Q,X,Y кінцеві)

2.2.Некінцеві (якщо хоча б одна множина не кінцева)

3.В залежності від визначення функцій переходу:

3.1.Повний (якщо функція переходу та виходу визначена повністю)

3.2.Частковий (якщо одна з функцій переходу чи виходу визначена частково)

4.В залежності від правил визначення функцій переходу:

4.1.Детермінований (якщо із стану q_і в стан q_j існує лише один варіант переходу)

4.2.Недетермінований (тобто якщо при зчитуванні символа алфавіту Х існує декілька варіантів переходу із стану q_і)

5.Якщо автомат представлений упорядкованою четвіркою {Q,X,f_q,F}, де F - підмножина станів Q, називається заключними

То такий автомат називається автоматом без виходу

28. Якими способами можна представити скінчений автомат?

Графа переходів, таблиця переходів, таблиця виходів.

1.Таблиці переходів і виходів автомату - це дві матриці однакової розмірності, де рядки позначені символами із вхідної множини, а стовбці - станами

2.Граф переходів і виходів автомата - це орієнтований граф, вершини якого визначають стани автомата, а ребра - взаємозв’язки

29. Як застосовується скінчений автомат для регулярної мови?

Створюють компілятор.

Теорема Кліні. Будь-яка мова, є регулярною тоді і тільки тоді, коли вона допускається деяким кінцевим автоматом.

30. Якими способами можна реалізувати скінчений автомат?

1.Наоснові оператора switch і перерахувань (представлення у вигляді графа)

2.На основі колекцій і перерахувань (представлення в вигляді таблиці переходів)

3.На основі шаблонів станів, оператора switch і перерахувань станів

31. Як застосувати шаблон проектування до реалізації скінченого автомату?

32. Що таке комбінаторика? Які існують загальні принципи комбінаторики?

Комбінаторика – це розділ математики, що вивчає спосіб підрахунку кількості різноманітних наборів, які задовільняють певним правилам. (умовам).

(як правило, підрахунок має бути значено швидшим, ніж перебирання всіх варіантів)

Принцип множення:

Якщо існує множина об’єкта А і якщо вибрать об’єкт а1 можна м1 способами, об’єкт

а2->м2 способами, …, об’єкт аr->мr способами, то вибір впорядкованих послідовності об’єктів (а1,а2,..,аr) можна здійснити (м1*м2*….*мr) способами.

Принцип додавання:

Якщо існує множина об’єкта А і якщо вибрать об’єкт а1 можна м1 способами, об’єкт

а2->м2 способами, …, об’єкт аr->мr способами, при цьому всі способи різні, то вибір будь-якого об’єкта аi можна здійснити (м1+м2+….+мr) способами.

33. Як розв’язуються комбінаторні задачі на розміщення?

Розміщення – це підрахунок кількості різних комбінацій формування послідовності по k елементів із N можливих, при цьому важливий порядок елементів. А k із n = n! / (n-k)!

Розміщення з повторенням – це підрахунок кількості різних комбінацій формування послідовності по k елементів із N можливих, при цьому елементи можуть повторятися і враховувати порядок елементів. А k із n = n^k

34. Які розв’язуються комбінаторні задачі на перестановку?

Перестановка – це підрахунок кількості різних комбінацій формування послідовності із N елементів. Рn=n!

Перестановка з повторенням – це підрахунок кількості різних комбінацій формування послідовності із N елементів, які можуть повторятися (N<k). Pn(n1,n2,n3)=n! / (n1!*n2!*n3!)

35. Які розв’язуються комбінаторні задачі на комбінацію

Комбінація – це підрахунок кількості різних комбініцій формування послідовності по k елементів із N можливих, при цьому порядок елементів не враховується. Ck із n=n!/ (k!*(n-k)!)

Комбінація з повторенням – це підрахунок кількості різних комбініцій формування послідовності по k елементів із N можливих, при цьому порядок елементів не враховується і елементи можуть повторюватися. C k із n = (n+k-1)! / (k! * (n-1)!)

36. Як використовується рекурсія для комбінаторних задач?

37. Як визначається граф? Де він застосовується?

Граф - абстрактна структура даних, яка представляє собою множину вершин і множину ребер, з’єднуючих пари різних вершин (одне ребро може з’єднати тільки одну пару вершин)

Кількість ребер не перевищує значення V*(V-1)/2

V - кількість вершин

Області застосування

1.Подорожі (визначення шляху проходження з однієї точки в іншу з найменшими часовими витратами)

2.Обробка гіпертексту (пошук інформації в глобальній мережі).

3.Розклад (розподіл занять з обліком не більше трьох пар в день і навчального навантаження викладача).

4.Зв'язок (відстеження трафіку).

5.Створення мікросхем (розподіл елементів таким чином, щоб не створити коротке замикання або шини не повинні перетинатися).

6.Створення мережі (забезпечення надійності функціонування при зміні конфігурації).

38. Як класифікуються графи?

39. Якими способами можна представити (реалізувати) граф? Як реалізувати граф у вигляді масиву ребер?

1.Масив ребер

2. Матриця суміжності - це матриця логічних значень розмірності V (V - кількість вершин), елемент якої на перетині і-го рядка і j-го стовпця встановлюється

в true, якщо в графі мається ребро, що з'єднує і-ю вершину з j-й вершиною.

3.Список суміжних вершин - являє собою одномірний масив посилань на односпрямовані списки, де індекс елемента масива являється вершиною, а список, зв’язаний з кожною вершиною, визначає суміжні їй вершини

40. Якими способами можна представити (реалізувати) граф? Як реалізувати граф у вигляді матриці суміжності?

1.Масив ребер

в true, якщо в графі мається ребро, що з'єднує і-ю вершину з j-й вершиною.

Матриця суміжності це двовимірний масив розміром N*N:

// матриця суміжності

Type TAdjacencyMatrix = array [1..N, 1..N] of Integer;
Var Graph: TAdjacencyMatrix;

При цьому Graph[i, j] дорівнює 0, якщо вершини i та j не є суміжними, та 1 для суміжних вершин. Для зваженого графа Graph[i, j] дорівнює вазі вершини i, якщо i=j, а для суміжних вершин — вазі ребра (дуги) з вершини i у вершину j.

Просторова складність цього способу O(N²)

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

41. Якими способами можна представити (реалізувати) граф? Як реалізувати граф у вигляді списку суміжних вершин?

1.Масив ребер

в true, якщо в графі мається ребро, що з'єднує і-ю вершину з j-й вершиною.

Список суміжності це послідовність (масив, список) розміром N, кожен елемент якої є списком вершин суміжних з даною:

// список суміжності

Type TAdjacencyList = array [1..N] of record
Count: Integer; {кількість елементів у списку}
List: array [1..N] of
record {список}
Node, {номер суміжної вершини}
Weight: Integer; {вага ребра}
end;
end;
Var Graph: AdjacencyList;

Цей спосіб збереження найкраще підходить для перерахування усіх вершин суміжних з x.

42. Як здійснити обхід графа в ширину?

1.Необхідно задати першу (вихідну) вершину (вершина дерева)

2.Відвідати (відкрити) всі вершини суміжні з першою (тобто які знаходяться на близькій відстані - перший рівень)

3.Відвідати всі вершини суміжні з вершинами першого рівня і не відкриті раніше

4.Повторювати дію в пункті 3 до тих пір поки не будуть відкриті всі вершини

43. Як здійснити обхід графа в глибину?

1.Необхідно задати вихідну вершину, від якої буде здійснюватися пошук

2.Відвідати (відкрити) будь яку суміжну з нею вершину і зробити її поточною (спуститися вглибину)

3.Продовжитии пошук суміжної вершини з нової поточної і т.д. поки не знайдеться вершина, у якої всі суміжні вершини оброблені

4.Повернутись на рівень вище і закінчити обробку всіх суміжних і невідкритих вершин

5.Продовжувати пункт 4 до тих пір, поки не повернеться до першої вершини.

44. Які існують задачі пошуку шляху на графах? Чим вони відрізняються?

1.Чи існує шлях між двома вершинами

2.Знаходження простого шляху

3.Знаходження циклічного шляху

Знаходження шляху, з’єднуючого дві вершини, повинно здійснюватися за лінійний час (час, який не перевищує деяке значення)

Дата добавления: 2015-11-14; просмотров: 29 | Нарушение авторских прав

<== предыдущая страница	\|	следующая страница ==>
Метод дотичних	\|	Способи отримання даних.

mybiblioteka.su - 2015-2024 год. (0.018 сек.)