Ім'я файлу: Контрольна робота.docx
Розширення: docx
Розмір: 313кб.
Дата: 05.11.2023
скачати
Пов'язані файли:
ПРАКТИКА ЗВІТ.doc
Індивідуальна робота з Логіки.docx
основн_ напрямки оздоровчої ф_зичної культури.docx
Питання_модуль_Меліорація_1_2020.doc
Психічні порушення при єпілепсії.docx
Африканський союз.docx
Завдання для самроботи.docx


Міністерство освіти і науки України

Національний авіаційний університет

Навчально-науковий інститут неперервної освіти


Контрольна робота

з дисципліни «Теорія алгоритмів»

варіант № 7


Виконав студент/ка________

групи___________

Номер залікової книжки

__________________________

Перевірила доцент
Київ 2022

Зміст


Питання 1 Нечіткі множини й нечіткі алгоритми. Адаптивні нечіткі системи. Трикутна функція приналежності. Результат нечіткого виводу. 3

Питання 2 Прості алгоритми сортування та їх програмування. Сортування вставками – алгоритм сортування на основі порівнянь. 8

Завдання 3 16

Завдання 4 19

Висновки 23

Список використаних джерел 24

Тема: Контрольна робота з теорії алгоритмів

Питання 1 Нечіткі множини й нечіткі алгоритми. Адаптивні нечіткі системи. Трикутна функція приналежності. Результат нечіткого виводу.


У математиці нечіткі множини (вони ж невизначені множини) – це множини, елементи яких мають ступені належності. Нечіткі множини були введені незалежно Лотфі А. Заде та Дітером Клауа у 1965 році як розширення класичного поняття множини.

Нечітка множина – це відображення набору дійсних чисел (x i ) на значення членства (ui ), які (зазвичай) лежать у діапазоні [0, 1]. У цьому нечіткому пакеті нечітка множина представлена набором пар ui / xi, де ui – значення приналежності для дійсного числа xi. Ми можемо представити набір значень як {u1/x1u2/x2...un/xn}. Значення x у наборі розташовані в порядку зростання (x1<=x2<=...<=xn). Значення до x1 мають те значення приналежності, як і x1 , а значення після xn мають те значення приналежності, як і xn. Значення між xi та xi+1 визначаються значенням, що лежить на прямій лінії між двома послідовними точками. По суті, ми представляємо графік з прямими лініями, що з'єднують точки нечіткої множини, і з горизонтальними лініями, що йдуть до першої та останньої точок.

Як приклад розглянемо (опуклу) нечітку множину FuzzySet{0,0/0,3 1,0/0,5 0,0/0,7}. Як показано на діаграмі нижче, це нечітка множина трикутної форми. Це дуже компактне уявлення нечіткої множини, що покриває всі значення в рядку дійсних чисел.



Рисунок 1 – Нечітка множина трикутної форми

Код створення цього FuzzySet буде просто таким:

FuzzySet fSet = новий трикутникFuzzySet(0.3, 0.5, 0.7);

Розглянемо тепер трохи складніший (неопуклий) FuzzySet: { 0,0/0,1 1,0/0,3 0,65/0,4 1,0/0,5 0,0/0,8}.



Рисунок 2 – Нечітка множина неопукла
Код для створення цього нечіткого набору із 5 точок може виглядати приблизно так:

double yValues[] = {0, 1, 0,65, 1, 0};

double xValues[] = {0,1, 0,3, 0,4, 0,5, 0,8};

FuzzySet fSet = new FuzzySet (xValues, yValues, 5);

Нечітка множина, що визначається однією точкою, наприклад { 0,5/25 }, являє собою одну горизонтальну лінію (нечітка множина зі значеннями членства 0,5 для всіх значень x).

Для представлення таких синглетонів можна використовувати {0.0/0.5 1.0/0.5 0.0/0.5}. По суті, це графік з нульовими значеннями членства для всіх значень x, за винятком значення x 0,5 де воно дорівнює 1. Такий вид нечіткої множини іноді використовується для розмиття чітких значень (коли немає помилки у значенні x). Часто чітке значення, таке як показання температури, допустиме лише в межах деякого допуску, тому для розмиття значення використовуються інші форми нечіткого набору, такі як PIFuzzySet або TriangleFuzzySet.

Хоча можна створювати нечіткі множини та виконувати з ними різні операції, в основному вони використовуються при створенні нечітких значень та для визначення лінгвістичних термінів нечітких змінних.

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

Контрольований алгоритм навчання лінійного зворотного поширення був застосований для моделювання системи шляхом визначення нечітких параметрів. Нечітка система навчання з алгоритмом навчання називається адаптивною нечіткою системою. Розроблена адаптивна нечітка система була реалізована як ідентифікатор динамічних систем.

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

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

Продуктивність адаптивних нечітких систем оцінюється з використанням середньоквадратичної помилки (точність), так і середньоквадратичної відстані (значення) в експериментах з прогнозування часових рядів з даними Mackey Glass і Box Jenkins.

Нечітка система (FS) – це будь-яка система на основі нечіткої логіки, яка використовує нечітку логіку як основу для представлення знань з використанням різних форм знань.
Для чого використовуються нечіткі системи?

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

На сьогоднішній день нечіткі експертні системи є найбільш поширеним використанням нечіткої логіки. Вони використовуються в кількох широких областях, включаючи: Лінійне та нелінійне керування. Розпізнавання образів.

Відповідно до класичної або чіткої логіки кожне судження має бути істинним або хибним, проте нечітка логіка є рішенням для представлення та лікування невизначеності та неточності за допомогою лінгвістичних термінів, представлених функціями належності. Наприклад, ми можемо розглядати довжину як лінгвістичну змінну з трьома можливими лінгвістичними значеннями {short, medium, tall}.

Процес нечіткої логіки маніпулює вхідними та вихідними змінними і базується на трьох фазах: фазифікації, нечіткому висновку та дефазфікації. Фазифікація перетворює чіткі значення в нечіткі значення, відображає фактичні вхідні значення в нечіткі функції належності та оцінює ступінь належності кожного входу в кожній функції членства. Функція належності нечіткої множини A визначається як µA(x), де µA(x) [0, 1], і вона представляє ступінь належності x до нечіткої множини A. Кожна функція належності ілюструється графічним зображенням ступінь участі кожного входу в наборі. Функція трикутної належності, яка використовується в даній роботі, характеризується математичною простотою. Він визначається трьома параметрами {a, b, c}, де для кожного значення x функція належності µA(x) описується, як показано на малюнку 3. Ці значення параметрів отримані з знань експертів.



Рисунок 3 – Представлення функцій трикутної належності

Друга фаза процесу нечіткої логіки включає виведення вхідних значень. Система нечітких висновків генерує висновки з набору нечітких правил, заснованого на знаннях, лінгвістичних тверджень ЯКЩО-ТО. Правила використовують вхідні значення належності як вагові коефіцієнти для визначення їх впливу на нечіткі вихідні набори кінцевого вихідного висновку. Останнім етапом є дефаззифікація, де нечіткі результати перетворюються на чіткі значення.

Питання 2 Прості алгоритми сортування та їх програмування. Сортування вставками – алгоритм сортування на основі порівнянь.


Сортування – це процес перестановки об’єктів даної множини в певному порядку. Мета сортування – полегшити наступний пошук елементів у відсортованої множині.

Алгоритм сортування – це алгоритм, який призначений для впорядкування елементів у списку або у масиві. У випадку, коли елемент списку має декілька полів, поле, що служить критерієм порядку, називається ключем сортування.

Прості алгоритми сортування, усім відомі як сортування обміном, вставками та вибором можуть мати складність в гіршому випадку . Більш ефективні алгоритми, наприклад, пірамідальне сортування мають складність . Існують ситуації, коли прості алгоритми випереджають складні по ефективності, наприклад, сортування вставками на невеликих наборах може бути найкращим. Такі випадки можуть самі стати об’єктами досліджень.

Критеріями оцінки методів сортування є:

  • кількість операцій порівняння пар ключів;

  • кількість перестановок елементів;

  • економне використання пам’яті.

Для тих чи інших даних існують певні методи сортувань, які покращують продуктивність та швидкість сортування саме для цього типу даних.

При відносно малій кількості елементів що сортуються, прості методи сортування працюють достатньо швидко.

Задачі сортування послідовностей є дуже відомими і поширеними. В загальному вигляді вони формулюються так:

Дана послідовність довжини заданого типу, на якому існують операції >, <, >=, <=. Необхідно відсортувати послідовність, тобто переставити її елементи таким чином, щоб для кожного виконувалось відношення , де , а є однією з зазначених операцій.

Ефективні алгоритми сортування потребують порядку порівнянь, де – кількість елементів, а – кількість необхідних порівнянь.

Розглянемо деякі прості методи сортування, які потребують кількість порівнянь порядку .

Методи сортування без копіювання масиву можна поділити на три основних класи:

  • сортування вибором;

  • сортування обміном;

  • сортування вставками.

Сортування вибором

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



Рисунок 4 – Схематичне зображення сортування простим вибором

Наведемо фрагмент коду сортування вибором:

for (i = 0; i < n; i++)

{

for( j = n – 1; j >= i; j--)

if (a[j-1] > a[j])

{

temp = a[j-1];

a[j-1] = a[j];

a[j] = temp;

}

}
Приклад роботи алгоритму сортування вибором.

Масив (4 1 5 2 3) з п’яти елементів ( ).

Перший етап:

Максимальний елемент «5» обмінюється місцями з елементом «3», який знаходиться на позиції .

(4 1 5 2 3) (4 1 3 2 5)

Другий етап:

Максимальний елемент «4» обмінюється місцями з елементом «2», який знаходиться на позиції .

(4 1 3 2 5) (2 1 3 4 5)

Третій етап:

В даному випадку елемент «3» є максимальним і розташовується на позиції , тому фізично обмін відбувається, але масив не змінюється.

(2 1 3 4 5) (2 1 3 4 5)

Четвертий етап

Максимальний елемент «2» обмінюється місцями з елементом «1», який знаходиться на позиції .

(2 1 3 4 5) (1 2 3 4 5)

Сортування вибором не є складним в аналізі та порівнянні його з іншими алгоритмами, оскільки жоден з циклів не залежить від даних у списку. Знаходження найбільшого елементу вимагає перегляду усіх елементів (у даному випадку здійснюється порівняння), і після цього, перестановки його на останню позицію. Знаходження наступного елементу вимагає перегляду елементів ( порівняння), і так далі, для порівнянь. Алгоритм не використовує додаткової пам’яті. Існує також варіант сортування методом вибору, в якому на кожному етапі відшукуються й встановлюються на свої місця як мінімальний, так і максимальний елементи.

Сортування обміном

Основна характеристика сортування обміном – перестановка місцями двох сусідніх елементів, якщо вони розташовані не так, як потребує відсортований масив. Проходи по масиву повторюються до тих пір, доки на черговому проході не виявиться, що обміни більше не потрібні, що означатиме – масив відсортований. При проході алгоритму, елемент, що стоїть не на своєму місці, «спливає» до необхідної позиції як бульбашка, звідси і назва алгоритму (рис.5).



Рисунок 5 – Схематичне зображення сортування простим обміном

Наведемо фрагмент коду реалізації сортування простим обміном.

for(i = 0 ; i < n ; i++)

{

for (j = 0 ; j < n – i -1; j++)

if (a[j] > a[j+1])

{

swap = a[j];

a[j] = a[j+1];

a[j+1] = swap; } }

Приклад роботи алгоритму сортування обміном.

Масив (4 1 5 2 3) з п’яти елементів ( ). На першому етапі маємо порівнянь.

Перший етап:

(4 1 5 2 3) (1 4 5 2 3)

(1 4 5 2 3) (1 4 5 2 3)

(1 4 5 2 3) (1 4 2 5 3)

(1 4 2 5 3) (1 4 2 3 5)

Так як максимальний елемент стоїть вже на своєму місці, тобто у кінці масиву, то на наступному етапі виконуємо порівнянь.

Другий етап:

(1 4 2 3 5) (1 4 2 3 5)

(1 4 2 3 5) (1 2 4 3 5)

(1 2 4 3 5) (1 2 3 4 5)

Третій етап передбачає виконувати порівнянь. В даному випадку масив відсортувався вже після другого етапу, однак алгоритму це ще не відомо. Тому при реалізації алгоритму сортування обміном, треба врахувати цей нюанс, а саме вдосконалити алгоритм таким чином, щоб він запам’ятовував, чи відбувався на даному етапі будь-який обмін. Якщо ні – алгоритм припиняє роботу. На третьому етапі алгоритм виконає свої порівнянь, під час яких жодні два елементи не поміняються місцями і завершує роботу.

Третій етап:

(1 2 3 4 5) (1 2 3 4 5)

(1 2 3 4 5) (1 2 3 4 5)

Тепер алгоритм може припинити свою роботу.

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

Сортування вставками

У сортуванні вставками елементи поділяються на вже впорядковану та невпорядковану послідовності. Спочатку впорядкована частина містить тільки один елемент. Наступний елемент, що розташовується на початку невпорядкованої частини, вставляється на підходяще місце впорядкованої частини. При цьому впорядкована частина подовжується на один елемент, а невпорядкована – зменшується. Сортування завершується коли зникає невпорядкована частина (рис.2.2).



Рисунок 6 – Схематичне зображення сортування простими вставками

Наведемо код реалізації сортування простими вставками.

#include "stdafx.h"

#include

#include

using namespace std;

int _tmain(int argc, _TCHAR* argv[])

{

int n, i, j, temp;

cout<<"please insert size of array ";

cin>>n;

int a[100];

for (i = 0; i < n; i++)

{

cout<<"please insert "<
cin>>a[i];

}

for (i = 1; i < n; i++)

{

temp = a[i];

j = i – 1;

while (j >= 0 && a[j] > temp)

{

a[j + 1] = a[j];

j--;

}

a[j + 1] = temp;

}

for (i = 0; i < n; i++)

{

cout<
}

getch();

return 0;

}

Приклад роботи алгоритму сортування вставками.

Масив (4 1 5 2 3) з п’яти елементів ( ).

Перший етап:

В даному випадку вважається, що елемент «4» є впорядкованою частиною масиву, відносно якого сортується невпорядкована частина, тобто частина, що починається з другого елементу.

(4 1 5 2 3) (1 4 5 2 3)

Другий етап:

На другому етапі впорядкована частина містить вже два елементи: «1» та «4», тому сортування починається з третього елементу.

(1 4 5 2 3) (1 4 5 2 3)

Третій етап:

Впорядкована частина складається з елементів «1», «4» та «5» На черзі четвертий елемент, який вставляється в впорядковану частину

(1 4 5 2 3) (1 2 4 5 3)

Четвертий етап:

Останній п’ятий елемент з невпорядкованої частини вставляється у впорядковану.

(1 2 4 5 3) (1 2 3 4 5)

Невпорядкована частина зникла, а тому алгоритм припиняє роботу.

Сортування вставками – простий алгоритм сортування на основі порівнянь. На великих масивах є значно менш ефективним за такі алгоритми, як швидке сортування, пірамідальне сортування та сортування злиттям. Однак має цілу низку переваг:

  • ефективний за звичай на маленьких масивах, на наборах даних до десятків елементів може бути найкращим;

  • ефективний на наборах даних, які вже частково відсортовані;

  • це стійкий алгоритм сортування (не змінює порядок елементів, які вже відсортовані);

  • може сортувати список під час його отримання;

  • не потребує тимчасової пам’яті, навіть під стек;

  • є стабільним алгоритмом.


Завдання 3


Знайти мінімальний позитивний елемент масиву (N) і кількість парних елементів.

Блок-схема



Текст програми
#include

#include

#include

#include

using namespace std;

int main()

{

setlocale(LC_ALL,"Rus");

srand(time(0));

int N,i;

int Min=0;

int k=0;

cout << "Введiть N:" << endl;

cout << "N = ";

cin >> N;

int* A = new int[N];

cout << "Масив A: "<
for(i = 0; i < N; i++)

{

A[i] = rand()%31 – N;

if (A[i]>=0) Min=A[i];

cout << A[i] << " ";

}

for(i = 0; i < N; i++){

if((A[i] >= 0) && (A[i] < Min)) Min = A[i];

if(A[i]%2==0) k++;

}

cout <
cout << "\nMin = " << Min << "\n";

cout << "\nКiлькiсть парних елементiв масиву= " << k << "\n";

return 0;

}

Результат роботи програми





Завдання 4


4) Зміст завдання
Ілюстрація

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



Блок-схема



Текст програми

#include

#include

#include

#include

using namespace std;
int main()

{

setlocale(LC_ALL,"Rus");

srand(time(0));

int N,I,j;

int Min;

cout << "Введiть N:" << endl;

cout << "N = ";

cin >> N;

int A[N][N]; //[i][j] відповідає i-му рядку и j-му стовпцю

cout << "Матриця A: "<
for(i = 0; i < N; i++)

{

for(j = 0; j < N; j++)

{

A[i][j] = rand()%31 – N;

cout << A[i][j]<<" ";

}

cout << endl;

}

for(i = 0; i < N; i++)

{

for(j = 0; j < N; j++)

{

// j > i умова елементів над головною діагоналлю

// j > (N – 1 – j) умова для елементів під побічною діагоналлю

// логічне І цих умов вибирає елементи з правого квадранту

if( j > i && j > (N – 1 – i) )

{

// копіюємо з лівого квадранту

// т.як заповнюємо матрицю зліва направо, тобто

// для кожного i,j елемент зліва вже заповнено

swap(A[i][j], A[i][N – 1 – j]);

}

}

}

cout << endl;

cout << "Нова матриця: "<
for(i = 0; i < N; i++)

{

for j = 0; j < N; j++)

{

cout << A[i][j]<<" ";

}

cout << endl;

}

cout << endl;

return 0;

}

Результат роботи програми







Висновки


При виконанні контрольної роботи було вивчено поняття нечітких множин й нечітких алгоритмів. Було дано визначення адаптивним нечіткім системам. розглянуть приклади. Також як частковий випадок була розглянута трикутна функція приналежності та визначено результат нечіткого виводу.

Також при виконанні роботі розглянуто прості алгоритми сортування та їх програмування. Більш ретельно описано алгоритм сортування вставками – алгоритм сортування на основі порівнянь та створено програмний код алгоритму на мові С++.

Практичне завдання було пов’язане з масивами – одновимірними, та двовимірними. Було створено блок-схеми алгоритмів, написано програмний код та опубліковані результати виконання програмного коду – скриншоти.

Список використаних джерел


  1. Теорія алгоритмів та математична логіка – [Електронний ресурс] – Режим доступу: https://elearning.sumdu.edu.ua/free_content/lectured:075b2e8a0bfe 48bcef0ab3106c6d51679abc41f9/latest/117286/index.html (дата звернення: 08.04.2022).

  2. United States Census // Sources of U. S. Census Data, from MIT Libraries, 2011. [Електронний ресурс]. – Режим доступу: http://libraries.mit.edu/guides/types/census/sources.html (дата звернення: 08.04.2022)

  3. Дупленко А. Г. Эволюция способов и алгоритмов сортировки данных в массивах / А. Г. Дупленко. – – [Електронний ресурс] // Молодой ученый. – 2013. – № 9 (56). – С. 17-19. – Режим доступу: https://moluch.ru/archive/ 56/7702/ (дата звернення: 08.04.2022).

  4. Melnyk M., Martynyak A., Kernytskyy A. Reverberation time study of an auditorium // Вісник Національного університету «Львівська політехніка». Серія: Комп'ютерні системи проектування теорія і практика: [зб. наук. пр.] / М- во освіти і науки України; голова Ред.-видавн. ради Н.І. Чухрай; [відп. ред. М.В. Лобур]. - 2016. - № 859. - P. 56-61.

  5. Авраменко В.С. Проектування інформаційних систем: навчальний посібник / В.С. Авраменко, А.С. Авраменко. – Черкаси: Черкаський національний університет ім. Б. Хмельницького, 2017. – 434 с.

  6. Басюк Т. М. Основи інформаційних технологій : навчальний посібник / Т.М. Басюк Н.О. Думанський О.В. Пасічник ; За ред. В.В. Пасічника. - Львів : Новий світ-2000, 2010. - 390 с.

  7. Visual Studio 2019 [Електронний ресурс]. – Режим доступу: https://visualstudio. microsoft.com/ru/vs/ (дата звернення: 22.11.2019)

  8. Васильєв О. Програмування С++ в прикладах і задачах – Київ: Ліра-К : Новий світ-2017. - 382 с.

скачати

© Усі права захищені
написати до нас