WWW.UA.Z-PDF.RU

БЕЗКОШТОВНА ЕЛЕКТРОННА БІБЛІОТЕКА - Методички, дисертації, книги, підручники, конференції

 
<< HOME
CONTACTS




Продажа зелёных и сухих саженцев столовых сортов Винограда (по Украине)
Тел.: (050)697-98-00, (067)176-69-25, (063)846-28-10
Розовые сорта
Белые сорта
Чёрные сорта
Вегетирующие зелёные саженцы

Продажа зелёных и сухих саженцев столовых сортов Винограда (по Украине)
Тел.: (050)697-98-00, (067)176-69-25, (063)846-28-10
Розовые сорта
Белые сорта
Чёрные сорта
Вегетирующие зелёные саженцы
Pages:     | 1 || 3 | 4 |

«ДИСКРЕТНИЙ АНАЛІЗ КОНСПЕКТ ЛЕКЦІЙ (для студентів спеціальності „Економічна кібернетика” денної та заочної форм навчання) ВІННИЦЯ – 2007 ВІННИЦЬКИЙ ФІНАНСОВО – ЕКОНОМІЧНИЙ ...»

-- [ Страница 2 ] --

• Якщо Аі,Аj S і ак Аі, то існує елемент аq Aj такий, що (Аі \ {ak}) {aq}.

Елементи сукупності S називають базами матроїда. Можна показати, що будь-які дві бази матроїда М містять однакове число елементів. Це число називається рангом матроїда М.

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

Приклад.

Припустимо, що сукупність S містить всі підмножини з А, що мають p n елементів. Тоді ми маємо матроїд рангу р, в якому всі елементи з S є базами, а всі підмножини з А, що містять не більше р елементів множини А є незалежними множинами. Циклами розглядає мого матроїда будуть підмножини множини А, що містять р + 1 елемент.

Іноді матроїд визначають в термінах незалежних множин.

Нехай А є кінцевою множиною, визначеною вище.

Нехай, далі, Q є сукупністю підмножин множини А, що задовольняють наступним умовам:

• Q;

• якщо Ai Q i Aj Ai, Aj Q;

• якщо Ai, Aj Q i (Ai = (Aj +1, то існує такий елемент a Ai \ Aj, що Aj {a} Q.

Тут Ai є числом елементів підмножини Аі.

Тоді пара М = (А, Q) називається матроїдом. Елементи множини А називаються елементами матроїда М. Елементи сукупності Q називаються незалежними множинами матроїда, а всяка максимальна за включенням незалежна множина називається базою матроїда М. Тоді підмножина множини А, що не належить Q, називається залежним.

Розглянемо таку опитмізаційну задачу.

Нехай А = {a1, a2,… an}є певною множиною і нехай кожному елементу з А поставлено у відповідність певне число w(aj) (j = 1,…,n) – „вага” елемента aj A. Нехай, далі, S = {A1, A2,…Am} є непустою родиною підмножин множини А. Тоді вагою елемента Аі S (i = 1, m), називається сума w ( Ai ) = a j длявсіх Ai.a j У випадку, якщо w(aj = 1), то w(Ai) = Card (Ai).

Є можливість будувати елементи родини S, послідовно обираючи елементи з множини А. Відоме правило P, яке дозволяє визначити, чи є обрана сукупність елементів з А підмножиною певного елементу з S.

Інакше кажучи, в задачі виконується перша з властивостей матроїда:

якщо Аі S і Аj Ai, то Аj S.

Питання для самоконтролю:

1. Як розуміють поняття множини? Наведіть синоніми цього поняття.

2. Які форми завдання множин існують?

3. Як формулюється поняття підмножини?

4. Що таке множина підмножин?

5. Які операції виконують над множинами?

6. Які множини називають впорядкованими?

7. Які відношення називають бінарними?

8. Як можна задати бінарне відношення?

9. Які операції виконують над бінарними відношеннями?

10. Що таке композиція бінарних відношень?

11. Які властивості можуть мати бінарні відношення?

12. Які бінарні відношення називають відношеннями порядку?

13. Які відношення називають відношеннями строгого і нестрогого порядку?

14. Які елементи впорядкованої множини називають мінорантами і мажорантами?

15. Що є потужністю множини?

–  –  –

Ключові поняття: алгебра; алгебраїчна система; групоїд; підстановка;

полугрупа; моноїд; асоціативність; нейтральний елемент; кільце;

гомоморфізм; ізоморфізм.

Література: [8,12 ].

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

Алгебраїчною системою називається трійка U = (A, F, P), що складається з непустої множини А, множини операцій F і множини предикатів р. Множина А називається носієм, або основною множиною системи U, а його елементи – елементами системи U.

Потужність Card (A) множини А називають потужністю, або порядком системи U і позначають як Card (U).

Об’єднуючи множини F і P і вважаючи, що = F P, ми можемо записати систему U коротше: U = (A, ).

Система U = (A, ) називається скінченною, якщо множина А скінченна.

Алгебраїчна система U = (A, ) називається алгеброю, якщо P = і моделлю (реляційною системою), якщо F =.

Прикладами алгебраїчних систем можуть бути:

U = (Z, +), = (R, +, -, ), G = (Z, + ), D = (Z, ), Де Z – множина всіх цілих чисел, R – множина всіх раціональних чисел, +,

-, - звичайні операції складання, віднімання і множення.

Згідно введеній термінології, U, - алгебри, D – модель.

2. Група; групоїди; полугрупи

Групою називається алгебра U = (A, *), що задовольняє умовам:

–  –  –

Умови 1) – 3) часто називають аксиомами групи.

Якщо, крім того, для групи справедливий комунікативний закон, тобто

4) a * b = b * a для будь-яких a, b А, то група U називається комунікативною, або абелевою.

–  –  –

Алгебраїчна система U = (A, F), де множина F складається з одної двомісної операції (як правило, операції множення), називається групоїдом. Групоїд часто представляють так: U = (a, * ).

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

У випадку скінченності множини А групоїд (А, *) часто задають за допомогою таблиць Келлі. Таблиця Келлі – це прямокутна таблиця, рядкам і стовпчикам якої відповідають елементи множини А, на перетині рядків і стовпчиків таблиці знаходиться результат, який належить множині

А (таблиця Келлі нагадує таблицю множення чисел):

* ab… y …d a b … x x*y … d Приклади групоїдів: множина натуральних чисел відносно операції складання; множина всіх цілих чисел відносно операції віднімання;

множина всіх раціональних чисел відносно операції ділення.

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

Групоїд (А, *) називається ідемпотентним, якщо а * а = а для всіх а А.

Групоїд (А, *) називається комунікативним, якщо х * у = у * х для будь-яких х, у А.

(А, *) прийнятний Якщо для будь-яких елементів групоїда асоціативний закон

–  –  –

Перший рядок представляє праву частину R+ бінарного відношення R, а другий рядок – ліву частину R_ бінарного відношення R.

Крім того, оскільки R_ ( другий рядок) має завжди один і той самий вигляд, то підстановку записують одним рядком:

(2,3,1).

–  –  –

Прикладом кільця може слугувати множина чисел, в якій виконуються операції складання (віднімання) і множення.

Кільце називається абелевим, якщо a b = b a.

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

–  –  –

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

4. Гомоморфізм та ізоморфізм Ізоморфізм (з грецької) означає буквально одну форму.

ІЗОМОРФНІ

–  –  –

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

Узагальненням поняття ізоморфізму є гомоморфізм (однаковий, подібний, рівний).

Відображення f групоїда U = ( A, *) на G – (В, о ) називається гомоморфізмом, якщо для всіх х, у А f (x * y) = f (x) o f (y).

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

При гомоморфізмі U = ( A, *) і G – (В, о ) зберігаються властивості комунікативності та асоціативності алгебраїчної операції.

–  –  –

Ключові поняття: граф; орієнтоване ребро; неограф; мультиграф;

матриця суміжності; матриця інцидентності; підграф; доповнення графа;

зв’язність графа; ізоморфні графи; покриваючі дерева.

Література: [25, 26].

1. Введення в теорію графів Графом називають двійку G = (V, E), де V = {v1, v2,…vn} – множину елементів, які називаються вершинами, а Е = {е1, е2,...еm} множина ребер (дуг) графа. Кожне ребро (дуга) з Е визначається парою вершин vi i vj, які воно з’єднує. Такі вершини називають кінцевими для ребра (дуги). Ребро графа G задається невпорядкованою парою вершин: {vi, vj}, а дуга – впорядкованою парою вершин: ( vi, vj ). Дугу графа G називають також орієнтованим ребром.

Отже, граф задає бінарне відношення Е, а множина V є полем даного відношення. Невпорядкованій парі { vi, vj } вершин у відношенні Е відповідають дві впорядковані пари (vi, vj ) і (vj, vi ). Однак, теорія графів розвивалася незалежно від теорії множин і тому в цій теорії виникли власні позначення і своя термінологія.

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

•• ••

–  –  –

Граф називають неорієнтованим, якщо він не має орієнтованих ребер.

Для стислості неорієнтований граф називають також неографом.

Іноді кожне ребро такого графа представляють як дві дуги, направлені у протилежні сторони.

Граф називають орієнтованим, як що він складається тільки з орієнтованих ребер (направлення кожного ребра вказано стрілкою). Для стислості орієнтований граф називають також орграфом.

Якщо граф має як орієнтовані, так і неорієнтовані ребра, то такий граф називають змішаним.

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

Між вершинами графа G і його ребрами має місце відношення інцидентності. Вершина vi є інцидентною ребру ек, якщо vi – одна з кінцевих вершин цього ребра. Навпаки, всяке ребро є іцидентним стосовно своїх кінцевих вершин.

Вершини vi, vJ V графа G називають суміжними, або сусідніми, якщо вони інцидентні стосовно одного і того самого ребра (тобто з’єднані хоча б одним ребром або дугою).

Якщо хоч одну пару вершин графа G з’єднує декілька ребер, то такий граф називають мультиграфом.

Вершину графа G називають ізольованою, якщо вона не є інцидентною жодній вершині цього графа.

Нехай в графі G є дуга ek = (vi,, vJ) E. Тоді дуга ek походить з вершини vi і заходить у вершину vJ.. Вершину vi, називають також початковою, а вершину vJ – кінцевою для дуги ek..


Купить саженцы и черенки винограда

Более 140 сортов столового винограда.


–  –  –

2. Способи завдання графа Матриця суміжності Матриця суміжності – це булава матриця (Інді її називають також двоїстою, або бітовою) порядку n: R riJ, в якій рядкам і стовпчикам поставлені у відповідність вершини графа G і riJ = 1, якщо вершини vi,, vJ V є суміжними, і riJ = 0, в протилежному випадку.

Матриця інцидентності Матриця інцидентності графа G – це також булава матриця Q = qiJ розміру n m, в якій рядкам поставлені у відповідність вершини графа, а стовпчикам – ребра.

Якщо граф G неорієнтований, то матриця інциденцій такого графа є булавою матрицею, в якій qiJ = 1, якщо вершина vi, є інцидентною ребру eJ і qiJ = 0, в протилежному випадку.

Для орієнтованого графа G елементи матриці інциденцій дорівнюють:

qiJ = 1, якщо в графі є дуга eJ = (vk, vi), в якій вершина vi – початкова, qiJ = - 1, якщо в графі є дуга eJ = (vk, vi), в якій вершина vi – кінцева, і qiJ = 0 у всіх інших випадках.

–  –  –

Структури суміжності В орієнтованому графі вершина w називається послідовником другої вершини v, якщо існує дуга, направлена з v у w.

Граф може бути заданий структурою суміжності, тобто списком усіх послідовників (сусідів) кожної вершини: для кожної вершини v задається Adj (v) - список усіх послідовників (сусідів) вершини v.ї Граф, заданий структурою суміжності, зазвичай позначають: G = (V, Г), де Г – відображення V у V.

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

3. Операції на графах

На графах виконуються певні теоретико-множинні операції. Розглянемо їх.

Нехай є графи G1 = (V1, E1) i G2 = (V2, E2).

Об’єднанням графів G1 = (V1, E1) i G2 = (V2, E2) називається граф G = ( V, E) = G1 G2, якщо V = V1 V2 i E = E1 E2. Іншими словами, граф об’єднання графів G1 і G2 містить вершини і ребра, які належать хоча б одному з цих графів.

Перетином графів G1 = (V1, E1) i G2 = (V2, E2) називається граф G = ( V, E)= G1 G2, якщо V = V1 V2 i E = E1 E2. Іншими словами, граф перетину графів G1 і G2 містить вершини і ребра, які є загальними для цих графів.

Доповненням графа G = ( V, E) називають граф G = ( V, E ), в якому &&& E=(VV) \ ( E v ), де v - це діагональне відношення на множині V1. Іншими словами, додатковий граф G має ту саму множину вершин, що і граф G, а ребра з’єднують дві його різноманітні вершини тільки тоді, коли у вихідному графі ребро між вершинами, що розглядаються, відсутнє.

Отже, додатковий граф є доповненням даного графа до повного.

Композицією графів G1 = (V1, E1) i G2 = (V2, E2) називається граф G = ( V, E) = G1 о G2, в якому є ребро {xi, xJ}, якщо тільки є ребра {xi, xk} E1, {xk,xj}E2.

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

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

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

Зв’язність графів і дерева

Нехай є граф G = ( V, E).

Маршрутом М у графі G називають послідовність вершин ребер з G М = (vi1, ei1, vi2, ei2, vi3,…, eip, vip+1).

Таку, що сусідні ребра eik, eik+1 (k = 1,2,…p) послідовності М є суміжними, а вершини viL,, viL+1. є кінцевими для ребра viL,. Вершину vi1 називають початковою, а вершину хір+1 – кінцевою вершинами маршруту М. Число р ребер маршруту називають його довжиною.

Іноді маршрут М задають або послідовністю ребер, що його складають:

М = (еі1, еі2,..., еір),

Або послідовністю вершин, через які він проходить:

М = (vi1, vi2, vi3,…, vip+1).

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

В загальному випадку граф G може мати декілька компонент зв’язності.

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



Pages:     | 1 || 3 | 4 |
Похожие работы:

«Семикіна К.В. Проблеми інвестування агропромислового комплексу України УДК 330 ПРОБЛЕМИ ІНВЕСТУВАННЯ АГРОПРОМИСЛОВОГО КОМПЛЕКСУ УКРАЇНИ Семикіна К.В., асистент, ДНАБА У статті зроблено аналіз ситуації щодо залучення інвестицій в сільське господарство і поліпшення інвестиційного клімату, вивчені регіональні особливості залучення інвестицій в АПК України. Окреслено специфіку аграрного сектора економіки, виявлено головні проблеми залучення інвестицій в АПК та основні чинники, що зумовлюють їх....»

«Покращення можливостей щодо гідної праці для молоді за допомогою знань та дій 25 червня 2014 р. План • Контекст зайнятості молоді • Проект W4Y і його логіка втручання • Головні результати проекту: o Опитування щодо переходу від школи до роботи o Глобальні бази даних o Звіти та публікації План • Контекст зайнятості молоді • Проект W4Y і його логіка втручання • Головні результати проекту: o Опитування щодо переходу від школи до роботи o Глобальні бази даних o Звіти та публікації Контекст...»

«ІННОВАЦІЙНА ЕКОНОМІКА – 5’2013[43] Всеукраїнський науково-виробничий журнал Література 1. Котлер Ф. Маркетинг менеджмент. Экспресс-курс / Ф. Котлер. – СПб: Питер, 2001. – 496 с.2. Kotler P. Marketing management: analysis, planning and control / Philip Kotler. – Stuttgart, 1982. – 656 p.3. Акимов Д.И. Социальный маркетинг : монография / Д.И. Акимов. – К. : Наукова думка, 2008.– 144 с.4. Примак Т.О. Маркетингова політика комунікацій: Навчальний посібник / Т.О. Примак. – К. : Атака, Ельга-Н, 2009....»

«Звіт про виконання плану роботи фінансового управління Конотопської міської ради за 2013 рік На початку січня місяця 2014 року був підготовлений та наданий тимчасовий розпис доходів та видатків міського бюджету на І квартал 2014 року до Конотопського УДКСУ. В січні місяці 2014 року на сесії міської ради було ухвалене рішення «Про міський бюджет на 2014 рік». Протягом лютого складений та наданий до Конотопського УДКСУ помісячний розпис міського бюджету на 2014 рік, затверджені кошториси...»

«ПримЕчаниЯ [1] Бунин И.А. Темные аллеи. Рассказы. 1931– 1952. Собр. соч. в 9– ти томах, т.7. – М., 1965. [2] Иванова Л.П. Кавказ в русском языковом сознании XIX– XX столетий. – К.: Издательский Дом Дмитрия Бураго, 2004. – 110 с. [3] Наливайко Д.С. Козацька християнська республіка (Запорозька Січ у західноєвропейських літературних пам’ятках). – К.:Дніпро,1992. – 494 с. [4] Наливайко Д.С. Очима Заходу. Рецепція України в Західній Європі ХІ– ХVІІІ ст.– К.: Основи, 1998. – 578 с. [5] Орехов В.В....»

«Таврійський державний агротехнологічний університет Summary Purpose statement. After Soviet Union collapsed many economic relationships were broken in all branches of economy including processing. In such situation processing plants had to look for new opportunities to survive. One of the ways that was found is tolling operations. This was reasonable for processors as well as for owners of raw materials. It was a new type of economic relationship and a lot of questions appeared and one of them...»

«ЕКОНОМІКА РЕГІОНІВ УДК:334.722:338.26:330.34 Кашуба Я.М. ОЦІНЮВАННЯ РЕЙТИНГУ РЕГІОНІВ ЗА РІВНЕМ РОЗВИТКУ ПІДПРИЄМНИЦТВА НА ОСНОВІ СТРУКТУРНИХ ПОКАЗНИКІВ В статті розроблено метод оцінювання якості розThe author grounds the new method for the витку підприємництва в регіоні на основі аналізу відestimation of development’s quality for enterprise in a носних структурних показників. Виконано регіональні region using the analysis of structural indicators. Author порівняння спеціалізації та в сфері...»

«Збірник наукових №2 (64) Серія: Економічні науки праць ВНАУ 2012 УДК 657.6 (477) ПРОБЛЕМИ ПІДВИЩЕННЯ ЕФЕКТИВНОСТІ ЗДІЙСНЕННЯ ДЕРЖАВНОГО ФІНАНСОВОГО КОНТРОЛЮ В УКРАЇНІ Фурман І.В., асистент Сивак Б.В., Покотило Ю.І. Вінницький національний аграрний університет Розглянуто основні підходи до визначення сутності державного фінансового контролю. Наведено систему критеріїв ефективності його здійснення. На основі зарубіжного досвіду показано основні напрямки реформування системи державного фінансового...»

«Збірник наукових №3 (69) Серія: Економічні науки праць ВНАУ 2012 УДК 658:330.341 МОДЕЛІ І МЕТОДИ УПРАВЛІННЯ ІННОВАЦІЙНИМ РОЗВИТКОМ АГРОПРОМИСЛОВОГО ВИРОБНИЦТВА Бурденюк І.І., к.т.н., доц., Черняк Н.І., к.т.н. Вінницький національний аграрний університет У статті розглядаються питання використання методів математичного моделювання в управлінні інноваційним розвитком агропромислового виробництва, запропоновано перелік методів і моделей на різних етапах процесу управління. Ключові слова:...»

«Науковий вісник Академії муніципального управління: Серія «Управління», випуск 1, 2014 необхідних. Подальшим напрямом наукового дослідження у даному напрямі вбачається у впровадженні комплексної методики визначення необхідного складу сил і засобів для реагування на надзвичайні ситуації.Використані джерела інформації: 1. Бакуменко В.Д. Прийняття рішень в державному управлінні: Навчальний посібник [у 2 ч.] / В. Д. Бакуменко // Ч. 1. Теоретико-методологічні засади. К. : ВПЦ АМУ, 2010. – С 107-113....»

«МЕНЕДЖМЕНТ, МАРКЕТИНГ, ПІДПРИЄМНИЦТВО 6. Голіков А. П. Розміщення продуктивних сил і регіоналістика : [навч. посіб.] / Голіков А. П., Дейнека А. Г., Казакова Н. А. – Х. : ТОВ «Олант», 2002. – 356 с.7. Про Загальнодержавну програму розвитку рибного господарства України на період до 2010 року : Закон України від 19 лютого 2004 року № 1516-IV [Електронний ресурс]. – Режим доступу : http://search.ligazakon.ua/l_doc2.nsf/link1/ed_2004_02_19/JD2NQ00G.html# 8. Стеченко Д. М. Розміщення продуктивних...»

«Звіт міського голови за 2014 рік Сьогодні я хочу підбити підсумки виконаної за рік роботи, представити Вам картину наших досягнень, позначити проблеми у розвитку Червонозаводського. 2014 рік був дуже складним в економічному та політичному плані в житті нашої держави та кожної громади. Цей рік став серйозним іспитом і для Червонозаводської міської ради. Я вважаю, що ми гідно вистояли в цей непростий час. За звітний період міська рада не звернула і не скоротила жодної соціально значимої програми....»

«учета // [електронний ресурс] / http://www.cfin.ru/ias/manacc/reporting.shtml. 9. Бухгалтерський управлінський облік: [підруч. для студентів спеціальності “Облік і аудит” вищих навчальних закладів] / [Бутинець Ф.Ф., Давидюк Т.В., Малюга Н.М., Чижевська Л.В.]. – Житомир: ПП “Рута”, 2002. – 480 с. 10. Соколов Я.В. Расходы будущих отчётных периодов: форма и содержание / Я.В. Соколов, В.В. Патров // Бухгалтерский учёт. – 1998. – № 8. – С. 91–93. УДК 338. 242: 658.14 О.А. Ліпич Національний...»




Продажа зелёных и сухих саженцев столовых сортов Винограда (по Украине)
Тел.: (050)697-98-00, (067)176-69-25, (063)846-28-10
Розовые сорта
Белые сорта
Чёрные сорта
Вегетирующие зелёные саженцы


 
2017 www.ua.z-pdf.ru - «Безкоштовна електронна бібліотека»