Спеціальні глави математики

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

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

Кафедра інформаційно-вимірювальних систем

Курсова робота

з дисципліни: «Спеціальні глави математики»

Виконав: студент Перевірив: к.т.н. Марченко Н.Б.

Варіант № 5

Київ 2009

Варіант

граф матриця математична логіка

Номер розрахункового варіанту m визначається за списком групи: m=5.

Курсова робота повинна складатись з двох частин: Пояснювальної записки та Додатку. В пояснювальній записці всі символи і позначення беруться з та з запропонованих завдань, не допускається вживання програмних символів, в Додатку символіка вільна, але повинна відповідати певній одній системі, а також обов’язково повинна бути описана відповідність символіки кожної програми та позначень вживаних в тексті Пояснювальної записки.

Пояснювальна записка повинна містити:

текст завдань (без змін і спотворень) ;

постановку кожної задачі;

числові значення параметрів визначені за номером варіанта та вказані в завданні по яких розв’язується задача; а також їх фізичні розмірності;

розгорнуті розв’язки з вказівкою усіх використовуваних основних формул, їх номерів та сторінок в літературі, з якої вони взяті;

зведення результатів;

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

список використовуваної літератури,

всі основні формули та математичні вирази повинні мати порядкові номери, сторінки пронумеровані.

Додатки включають:

обчислювальні програми, алгоритми та коментарі до них; результати розрахунків; графічні побудови,

основні формули в програмі повинні бути пронумеровані окремими номерами з буквою Д. Малюнки підписані і теж пронумеровані окремо.

Реферат

Об'єкт дослідження — задачі з дисципліни «Спеціальні глави математики».

Мета роботи: узагальнення і систематизація знань з дисципліни «Спеціальні глави математики», отриманих протягом навчального семестру. Закріплення пройденого матеріалу, а саме з теорії множин, математичної логіки, теорії графів та теорії рядів.

Зміст

Реферат

1. Вступ

2. Основні позначення

3.Пояснювальна записка

Завдання 1

Завдання 2

Завдання 3

Завдання 4

Завдання 5

Список використаної літератури

Додатки

Вступ

Дана курсова робота проводиться з метою більш поглибленого вивчення дисципліни «Спеціальні глави математики» та для набуття навиків самостійного вирішення заданих задач.

Для успішного виконання КР студент повинен вміти працювати з літературою, знати необхідний матеріал для виконання роботи, а саме, з теорії множин, математичної логіки, теорії множин та графів.

Завдання № 1

Розв’язання задач з теорії множин та математичної логіки Довести і навести діаграму Ейлера-Вена

Завдання № 2

Записати таблицю істинності висловлювань

Завдання № 3

Для заданого графа з :

1. Знайти число ребер та число вершин відповідного повного графа.

2. Визначити характеристики графа у відповідності до таблиці 1

Таблиця 1

3. Визначити характеристики вершини графа (заповнити таблицю 2)

Таблиця 2

4. Побудувати матрицю інцидентності графа

5. Намалювати зв’язні підграфи графа з 4 і 5 вершинами.

6. Виписати їх матриці інцидентності.

7. Мінімальним числом операцій вилучення та доповнення ребер зробити заданий граф Ейлеровим.

8. Мінімальним числом операцій вилучення та доповнення ребер зробити заданий граф Гамільтоновим.

Завдання № 4

«Розклад функцій дискретного аргументу в ряди по базисним функціям»

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

Функція визначається з таблиці 3, де номер варіанта.

Таблиця 3

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

Завдання № 5

Для процесора, що реалізує алгоритм дискретного (або швидкого) перетворення Фур'є, при заданих значеннях обсягу вибірки відліків вхідного сигналу і частоті дискретизації, вирахувати та побудувати нормовану амплітудно-частотну характеристикуго вихідного сигналу.

— номер варіанту

Методичні вказівки

Необхідно мати на увазі, що при частоті вхідного сигналу, співпадаючої з частотою настройки 1-го каналу процесора, у випадку, якщо, відгукго каналу рівний нулю. Розрахунок значення АЧХ достатньо проводить в трьох точках по вісі частот у кожному з інтервалів між резонансними частотами процесора. Зручно у якості цих точок вибрати середину інтервалу розносу резонансних частот процесора та середні точки половинок інтервалів що утворилися.

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

Таблиця 4

2.Основні позначення

Завдання № 1

Розв’язання задач з теорії множин та математичної логіки Довести і навести діаграму Ейлера-Вена Згідно варіанту:

Короткі теоретичні відомості

Поняття множини — одне з основних понять математики, яке не визначається. Множину можна уявити як сукупність деяких об'єктів, об'єднаних за якою-небудь ознакою. При цьому передбачається, що об'єкти даної сукупності відрізняються один від одного і від предметів, що не входять до цієї сукупності. Множини позначаються великими літерами A, B, C, D та т. д.

Існує два основних способи завдання (опису) множин.

1) Множина, А визначається безпосередньо перелічуванням своїх елементів а1, а2, …аn, тобто записується у вигляді

2) Множина, А визначається як сукупність тих і тільки тих елементів з деякої основної множини В, що мають властивість б (x). У цьому випадку використовуються позначення або. Таким чином, множина вважається заданою, якщо відома властивість, яку мають елементи цієї множини.

Операції над множинами.

Перетином (або додатком) множин, А і В (позначення або А•В) називається множина, що складається з елементів, які належать одночасно як множин А, так і множині В:

(1)

На рис. 1. а множина заштрихована.

Розглянемо властивості операції перетину:

1)

2)

3)

4)

5)

6)

Об'єднанням (або сумою) множин, А і В (позначення або А+В) називається множина, що складається з усіх елементів, які належать хоча б одній з цих множин.

(3)

На рис. 1. б множина заштрихована.

Розглянемо властивості операції об'єднання:

1)

2)

3)

4)

5)

6)

Різницею множин (позначення АВ) називається множина, що складається з елементів, як належать множині А, але не належать множині В. На рис. 1. в множина АВ заштрихована.

(4)

Розглянемо властивості операції різниці:

1)

2)

3)

4)

5)

Доповненням множини, А (позначення) називається множина елементів універсальної множини Щ, не приналежних множині А.

Якщо Щ зобразити у вигляд прямокутника, то множина заштрихована на рис. 1.г.

Розглянемо основні властивості операції доповнення:

1)

2)

3)

4)

5)

Доведення: Нехай спираючись на властивість різниці можна стверджувати, що

Тепер нехай спираючись на властивості операцій пертину Та різниці, ми отримаємо, а отже

Отже ми можемо сказати, що, А є пдмножино С, а враховуючи оперцію різниці, В виключається.

Нехай, тоді не існує таких і, тобто множина, А буде підмножиною В.

Отже наша умова виконується Наведемо діаграми Ейлера-Вена

Отже твердження — вірне, що і було доведено

Висновок: в результаті нескладних методів розв’язання задач з теорії множин та математичної логіки та за допомогою діаграм Ейлера-Вена було доведено вираз. Результат отримали однаковий.

Завдання № 2

Записати таблицю істинності висловлювань

Складні висловлення утворюються з простих за допомогою логічних операцій. Розглянемо основні з них.

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

Наведене в означенні можна записати з допомогою таблиці істинності.

Означення. Еквівалентністю двох висловлень називається таке складне висловлення, яке істинне тоді і тільки тоді, коли значення істинності висловлень однакові, і хибне — якщо різні.

Таблиця істинності еквівалентності:

Означення. Імплікацією двох висловлень називається таке складне висловлення (інше позначення), яке хибне тоді і тільки тоді, коли, а .

Таблиця істинності для імплікації така:

Розв’язання:

Для зручності будемо робити розрахунки в таблиці.

Отримали таку таблицю істиності:

Таблиця 5

Висновок: за допомогою простих логічних операцій отримали таблицю істиності виразу

Завдання № 3

Граф — множина точок, що сполучені деякими відрізками.

Неорієнтовані (ненапрямлені) графи Означення. Нехай множина — множина точок, — множина усіх двоелементних невпорядкованих підмножин множини X (множина відрізків, які сполучають точки з X). Графом (неорієнтованим, ненапрямленим) називають систему множин X і W, де (X — множина точок — вершин, W — множина відрізків — ребер).

Якщо і, то називається скінченним графом, в іншому випадку — нескінченний граф.

Означення. — повний граф якщо .

Означення. — порожній граф якщо .

Означення. Нехай — граф. Матриця, складена з чисел, називається матрицею інцидентності (суміжності) графа .

Іншими словами,, коли вершини та не з'єднані ребром і, коли ці вершини з'єднані ребром.

Степінь вершини графа Означення. Нехай — граф, , — вершини цього графа. Вершини та інцидентні (вершини та сполучені ребром).

Означення. Нехай — граф,. — степінь (валентність) вершини x число вершин, інцидентних з x (число ребер, що виходять з вершини x).

Теорема Ейлера. (кожне ребро при підрахунку суми степенів усіх вершин враховується два рази).

Означення.. Якщо, то вершина називається кінцевою. Якщо, то вершина називається ізольованою.

Підграфи Означення. Нехай — граф. Впорядкований набір елементів (ребер) з: називається маршрутом. Якщо, то маршрут називається замкненим, інакше — відкритим.

Означення. Маршрут, у якого всі ребра різні називається ланцюгом, що сполучає (з'єднує) вершини і (кінці ланцюга).

Означення. Ланцюг, у якого називається простим ланцюгом (див. рис. 2.).

Рис. 2.

Означення. Ланцюг називається замкненим (або циклом), якщо .

Означення. Граф називається підграфом графа, якщо .

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

Незв’язний граф складається з k>1 окремих підграфів, кожний з яких є зв’язним графом.

Означення. Граф без циклів називається ациклічним або лісом.

Означення. Зв’язний граф без циклів називається деревом.

Теорема 1. Нехай — зв’язний граф.

— дерево тоді і тільки тоді, коли .

містить хоча б один цикл тоді і тільки тоді, коли .

Зауваження. По суті, 2-й пункт теореми 1 є наслідком першого і навпаки. Але нам тут зручніше розглядати їх разом.

Наслідок. При заданому, дерево — це зв’язний граф, який має найменшу кількість ребер.

Ейлерові графи

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

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

Теорема. Зв’язний граф ейлеровий тоді і тільки тоді, коли степінь кожної його вершини — парне число.

Наслідок. Зв’язний граф напівейлеровий, якщо існує не більше двох його вершин непарного степеня.

Гамільтонові графи Означення. Зв’язний граф називається гамільтоновим, якщо існує цикл, який проходить через кожну його вершину тільки один раз.

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

Рис. 3. Граф

Розв’язування:

Для заданого графа з :

1. Знайдемо число ребер та число вершин відповідного повного графа.

2. Визначимо характеристики графа у відповідності до таблиці 6

Таблиця 6

3. Визначимо характеристики вершини графа

Таблиця 7

4. Побудувати матрицю інцидентності графа

Згідно з визначенням будуємо матрицю інцидентності графа:

5. Намалювати зв’язні підграфи графа з 4 і 5 вершинами. Виписати їх матриці інцидентності.

6. Мінімальним числом операцій вилучення та доповнення ребер зробити заданий граф Ейлеовим.

7. Мінімальним числом операцій вилучення та доповнення ребер зробити заданий граф Гамільтоновим.

Завдання № 4

«Розклад функцій дискретного аргументу в ряди по базисним функціям»

Розглянемо простір функцій дискретного аргументу (тобто, таких функцій, областю визначення яких є впорядкована дискретна множина): .

Різницевий оператор у просторі функцій вводиться наступним чином:

(5)

Крім різницевого оператора вводять ще оператор попередньої різниці:, (при :), який зв’язаний з різницевим оператором формальним співвідношенням: при ().

Властивості різницевого оператора:

, тобто різницевий оператор є лінійним.

.

при .

При маємо:, де (- оператор зсуву).

.

— різницевий операторного порядку (повторне (разів) застосування різницевого оператора).

Теорема. Для різницевого оператора n-го порядку справедливим є наступне співвідношення:

Узагальнений степінь

Функцію

називають узагальненим степенем. Якщо, то замість вживається позначення

.

Для натуральних маємо:

при ,

зокрема,. Кількість розміщень з по

Розклади функцій за узагальненими степенями

Аналогічно розкладу функцій неперервного аргументу в ряди за степеневими функціями (ряди Тейлора), можна будувати розклад деякої функції в ряд за узагальненими степенями :

Розв’язання

Згідно з варіантом m=5, ,

Проведемо розрахунок різницевого оператора згідно формули (6) отримаємо:

Знайдемо коефіцієнти в точці скориставшись формулою:

Отримаємо:

Згідно формули (7) отримаємо:

По отриманим значенням побудуємо графік:

Рис. 4. Графік функції та цієї ж функції розкладеної за узагальненими степенями Додатки:

Завдання № 5

Для процесора, що реалізує алгоритм дискретного (або швидкого) перетворення Фур'є, при заданих значеннях обсягу вибірки відліків вхідного сигналу і частоті дискретизації, вирахувати та побудувати нормовану амплітудно-частотну характеристикуго вихідного сигналу.

— номер варіанту Таблиця

Короткі теоретичні відомості.

В загальному випадку, рівняння має незвідних коренів

Нехай: .

Побудуємо матрицю .

Отримаємо:

Для справедлива властивість:, де — остача від ділення на,. Дійсно, можемо записати, де — неповна частка від ділення на. Тому .

Матриця симетрична:. Зокрема, другий рядок (другий стовпець) матриці містить усі незвідні корені рівняння .

Має місце:, тому — унітарна матриця, тобто .

Таким чином, якщо — вектор-стовпець (в загальному випадку, з комплексними елементами), то

де

.

Ортогональні перетворення та називаються парою дискретних (скінченних) перетворень Фур'є (ДПФ).

У розгорнутому вигляді розглянуті вище матричні перетворення можна записати так:

.

Останній вираз можна записати так:

, (9)

де

.

Алгоритм швидкого перетворення Фур'є (ШПФ)

Цей алгоритм застосовується для обчислення дискретного перетворення Фур'є і не є яким-небудь різновидом самого ДПФ.

Розглядуваний алгоритм ШПФ використовується лише при, де — натуральне число (відомі й інші алгоритми ШПФ, у яких не обов’язково має бути степенем двійки).

Розіб'ємо масив на дві частини:

.

Представимо теперий коефіцієнт ДПФ у вигляді:

.

Безпосередньо видно, що перша половина коефіцієнтів ДПФ виражається через коефіцієнти ДПФ послідовностей та, тобто Оскільки, то

.

Крім того, множник, при можна записати так:

.

Тому для другої половини множини коефіцієнтів ДПФ маємо:

.

Процес повторюється по ітерації, поки не залишиться один елемент. Його ДПФ буде він сам. Число операцій при використанні ШПФ .

Розв’язання:

Вирахуємо вираз для нормованої амплітудно-частотної характеристикиго вихідного сигналу:

Після підстановки у вираз наших даних отримуємо графік:

Рис. 5. Амплітудно-частотна характеристикаго вихідного сигналу.

Висновок: Значення отриманої функції у точках, кратних 9 рівна нулю, бо і головний пелюсток зсунутий праворуч на дев’ять позицій від нульової координати через те, що k=9.

СПИСОК ВИКОРИСТАННОЇ ЛІТЕРАТУРИ:

1. Марченко Б. Г., Марченко Н. Б., Фриз М.Є. Спеціальні глави математики. Навч. посібник. — Тернопіль: Вид-во ТДТУ ім. І.Пулюя, 2004. — 159 с.

2. Марченко Б. Г., Фриз М.Є. Основи дискретної математики. Конспект лекцій. — Тернопіль: Вид-во ТДТУ ім. І. Пулюя, 2000. — 96 с.

Додатки Додаток 1

Додаток 2