ИНФОРМАЦИЯ ДЛЯ ПРАВООБЛАДАТЕЛЕЙ

Все рефераты, курсовые, дипломные работы на нашем сайте представлены исключительно в образовательных целях и бесплатно. Все права на работы принадлежат их законным владельцам и предназначены только для ознакомления.
Наличие материалов на сайте никаким образом не претендует на обозначение нашего авторского права на данные материалы. Посетитель обязуется не применять полученную здесь информацию в целях, запрещённых УК РК.
Если вы соглашаетесь с указанными условиями, то можете приступить к просмотру материалов. Иначе вы должны немедленно покинуть сайт.

Все материалы, размещенные на сайте, взяты с открытых (общедоступных) источников.
Если Вы являетесь правообладателем какого-либо материала, размещённого на этом сайте, и не хотели бы чтобы данная информация распространялась без Вашего на то согласия, то мы будем рады оказать Вам содействие, удалив соответствующие материалы.

Для этого достаточно, чтобы вы прислали нам письмо на topreferat@mail.ru

Матроидтарда қолданылатын алгоритм реферат
№2819



МАЗМҰНЫ - www.topreferat.com
Кіріспе .................................................................................................................. 2
І тарау. Матроидтарда қолданылатын алгоритм
Матроид түралы ұғым ................................................................................. 3
Циклдер матроиды, Еркін матроид, Бинарлы матроид ........................... 3
Бағаналық матроид ...................................................................................... 4
ІІ тарау. Негіздер мен қарапайым циклдар
2.1 Матроидтың қарапайым циклі ................................................................... 6
2.2 Салдарлары .................................................................................................. 7
2.3 Матроидтар мен комбинаторлық тиімділендіру ...................................... 7
Қорытынды ..................................................................................................... 13
Пайдаланылған әдебиеттер ...................................................................... 14




Жұмыс түрі: Реферат
Пәні: Соңғы қосылған рефераттар
Жұмыс көлемі: - бет

-----------------------------------------------------------------------------------
https://www.topreferat.com/
РЕФЕРАТТЫҢ ҚЫСҚАРТЫЛҒАН МӘТІНІ


Мазмұны
Кіріспе .................................................................................................................. 2
І тарау. Матроидтарда қолданылатын алгоритм
Матроид түралы ұғым ................................................................................. 3
Циклдер матроиды, Еркін матроид, Бинарлы матроид
Бағаналық матроид ...................................................................................... 4
ІІ тарау. Негіздер мен қарапайым
2.1 Матроидтың қарапайым циклі ................................................................... 6
2.2 Салдарлары .................................................................................................. 7
2.3 Матроидтар мен комбинаторлық тиімділендіру ......................................
Қорытынды ..................................................................................................... 13
Пайдаланылған әдебиеттер ...................................................................... 14
Кіріспe
Алгоритмда сараң алгоритмдер маңызды рөл ойнайды,
Циклдер матройды
- Матроид
Еркін матроид
- Е көбейтіндісінің өзі жалғыз
Маршрут
- Кезектесуші жүйелілік
a=v0, e1, v1, e2, …, vn-1,
Бағаналардың биіктіктері мен қабырғалары осындай е=(v-1,
а = v0, v1, …, vn=b
оған енетін қабырғалар саны әрине қарама-қарсы
Аяқсыз n. тек бір ғана нүктесіне
Бинарлы мартоид
-Тұтас сандар бойынша көрсетілген матроид бағана
Келісімділік
Әңгіме үшін алдымен осы мақалада қолданылатын
Матроид туралы ұғым
Келесі матрицаны қарастырамыз.
1001000
0101110
0010110
Е көбейтіндісін анықтаймыз. Матрица бағаналырының {1,2,3,4,5,6,7}
1.Бір көбейтіндісі бос емес. Тіпті егер
і = {{□}}.
2.Бір көбейтіндісінің кез келген элементінің кез
З.Сондай-ақ бір көбейтіндісінде тағы да бір
Матроид ұғымының өзін анықтауға өтеміз. Матроид
Қарастырылым мысалда сызықтық тәуелсіз бағаналар көбейтіндісі
Дәлелдеме. Х,Ү І [Х]=[Ү]+1 болсын.
Бағаналық матроидты қарастырамыз
Бағаналар бағытталмаған және 4 биіктікпен тесік
Теорема -1
Айталық 6 сызықша бағана, ал АG
Дәлелдеме. Х□АG X циклға ие болған
Енді X сызықтық тәуелсіз деп болжамдаймыз.
Егер де D нөлдік векторға ие
Негіздер мен қарапайым циклдар
Тікелей матроидтардың көмегі арқылы әр алуан
Матроидтың қарапайым циклі - матроидтардың минимальды
Екі көбейтінді береміз - М матроидтың
Теорема - 2
X көбейтіндісі келесі екі қасиет орындалған
1. В көбейтіндісі бос емес.
2.Егер де В1, В2□В, х□В1, -
Дәлелдеме. Онда келтірілген екі қасиет орындалсын
В1□{I}□В, І=В1-В. Дегенмен бұл кезде Ү□В-(В□{I})
Айталық В - базалар көбейтіндісі, екі
Салдарлары
Кез келген базаның қуаттылығы екі қасиет
Теорема - 3
С көбейтіндісі келесі үш қасиет орындалған
1. С элементтерінің ешқайсысы бос
2. С-ның ешқандай элементі С-ның басқа
З. Егер де С1 және
Дәлелдеме.
Келтірілген екі дәлелдемеге ұқсас. Оқырманға оны
Матроидтар мен комбинаторлық тиімділендіру
Матроидтар комбинаторлық тиімділенген байланысты тапсырмаларға және
Мынадай тапсырмалар қарастырамыз: менеджерде m бір
Айталық А - қандайда бір Е
Теорема - 4
Айталық А Е көбейтіндісінің қандайда бір
Дәлелдеме
Жартылай трансверсальдың әрбір көбейтіндісі - жартылай
Салдар-1
В матроидтың кез келген негізі үшін
Келесі қадамда біз қос матроид ұғымын
Бұл қадамда біз сараң алгоритм ұғымын
Айталық Е - бос емес соңғы
және w (А) А көбейтіндісінің салмағы
Бірқатар жиынтығын ең болмағанда бір бос
Ары қарай В тәуелсіздік аксиомасын қанағаттандырады,
Келесі тапсырманы қарастырамыз: жартылай реттелген көбейтіндіде
Нысандар ұяшығына қандай жағдайларда келесі алгоритм
Сараң алгоритм.
7. е1,
8. Айталық
және
9. Мүмкін болғанға дейін екінші
Айталық В - М=М(G) матроидының бірқатар
Кез келген Т ағаш үшін М(Т)
требиальді екендігін байқаймыз.
Мысал. Келесі бағана циклдары матроидын қарастырамыз:
Сурет-1. бағана мысалы.
1. E = {е1,е2,е3,е4,е5} – матроидтың
2. В1={е2,e3,e4}, В1={е1,e3,e4}, В3={е1,e2,e4}
3. B2={е1,е5},= {е2,е5},= {е3,е5} – кобаз
4. {е1,е2}, {е1,е3}, {e2,e3},{e4} – қарастырылған
Теорема - 5.
көбейтіндісі қасиетті қанағаттандыратын Е бос емес
кез келген ко цикл үшін С*.
Дәлелдеме.
Егер X матроид циклі болып табылса,
Керісінше айталық X - көрсетілген қасиетті
Е1 матроиды еркін матроидқа қосарлы және
Айталық G
Қорытынды.
Менің бұл курстық жұмысымның тақырыбы “
Бұл жұмысты орта оқу орындарында қолдануға
Үнемі алгоритмдердің мақсаты – берілген есептерді
Мұнда тест сұрақтарын енгізетін болсақ, онда
Пайдаланылған әдебиеттер:
В.П.Сигорский. Математический аппарат инженера. – К.,
Ю.Н.Кузнецов, В.И.Кузубов, А.Б.Волощенко. Математическое программирование: учебное
Е.В.Маркова, А.Н.Лисенков. Комбинаторные планы в задачах
Е.П.Липатов. Теория графов и её применения.
В.М.Бондарев, В.И.Рублинецкий, Е.Г.Качко. Основы программирования. –Харьков,
2





19 ақпан 2020ж.
topreferat.com - Тегін қазақша рефераттар, курстық, дипломдық жұмыстар

^