1. 1Жиын ұғымы. Шекті және шексіз жиындар. Жиындарды анықтау тәсілдері.Ішкі жиындар. Берілген жиынның барлық жиынтығы. К- элемент жиындарының саны туралы n- элемент жиынтығы
Дискретті экстремалды тапсырмалар минималды канкалык бутакты табу алгоритмі
жүктеу/скачать 336,61 Kb.
|
| 2.4Дискретті экстремалды тапсырмалар минималды канкалык бутакты табу алгоритмі
бастапқы берілген мәліметтермен бір мәнде анықталатын нәтиже алу үшін қай амалды (жұмысты) қандай ретпен орындау қажеттігін белгілейтін есептерді (мәселелерді) шешу (математикалық есеп-қисаптар орындау, техникалық объектілерді жобалау, ғылыми-зерттеу жұмысын жүргізу т.б.) тәсілдерінің дәл сипаттамасы. Алгоритм — математика мен кибернетиканың негізгі ұғымдарының бірі. Алгоритмді орындау алгоритмдік үрдіс деп аталады. Жалпы Алгоритм деп алдын ала не істеу керек екені дәл көрсетілген есептеу үрдісін айтады. Есептеу үрдісі қандай болса да алғашқы мәндерден бастап, сол арқылы толық анықталған қорытынды шыққанша жүргізіледі. Алгоритм ұғымының алғышартына алгоритмдік үрдіспен қатар мүмкін болатын алғашқы деректер жиынтығының нұсқауы және қорытынды алуға байланысты жүргізілген үрдістің аяқталғандығын көрсететін ереже енеді. Белгілі бір бастапқы деректердің жиынына қолданылған Алгоритм тиянақты қорытындыға келмеуі немесе есептеу барысы аяқталмай тоқталуы мүмкін. Егер есептеу үрдісі белгілі бір қорытынды алумен аяқталса (не аяқталмай қалса), онда Алгоритм мүмкін болатын бастапқы деректерге қолданылады (не қолдануға болмайды) деп ұйғарылады. Графтагы ен кыска жолдарды аныктау әдістері Граф берілген деп айтылады, егер: 1. Х бос емес жиыны берілсе; 2. Х жиыны, Г бейнелеуі Х -те берілсе. G=(X,Г) символымен белгіленген граф, Х жиынынан жəне Г бейнелеуінен тұратын жұп болып табылады. Адамдар жиынындағы əке жəне ана қарым-қатынасын граф анықтайды; шахмат ойынының ережелері үшін, электр құрылғыларын өзара байланыстыру үшін де граф қолданылады. Мүмкін болған жағдайда, Х жиынының элементтерін жазықтық нүктелерімен бейнелейміз, ал y ∈ Гx болатын х жəне y нүктелер жұбын x-тен y-ке бағытталған бағыттауышы бар үзіксіз сызықпен байланыстырамыз. Бұл X жиынының əрбір элементін нүкте немесе граф төбесі, ал y ∈Гx болатын (x,y) элементтер жұбын граф доғасы деп атауға негіз береді. Ары қарай графтың доғалар жиынын U арқылы, ал доғалардың өзін u, v немесе w (қажет болған жағдайда индекстермен) деп белгілейміз. Мысалы. 2.9-суретте бейнеленген G графында X жиыны a,b,c,d,e,xтөбелері арқылы, ал U жиыны – (a,b), (b,a), (b,x), (x,x), (x,c), (c,x), (x,d), (e,e) доғалар арқылы қалыптасқан. Г бейнелеуін анықтау қиын емес: мысалы, Гx = {x,c,d}, Гd = ∅ жəне т.с.с. Доғалар жиыны граф бейнелеуін анықтайтыны белгілі, жəне керісінше Г бейнелеуі U жиынын анықтайды; сондықтан графты G = ( X , Г ) түрінде де, G = ( X ,U ) түрінде де жаза аламыз. (X,Г)графының ішкі графы деп, (A,ГА)түріндегі граф аталады, онда А ⊂ Х , ал ГА келесідей анықталады: Г А x = Гx ∩ A (Х,Г) үшін жартылай граф деп (Х,Δ) түріндегі граф аталады, онда барлық х ∈Х үшін Δx ⊂ Гх. (Х,Г) графы үшін жартылай ішкі граф деп (А,ΔА) түріндегі графаталады,онда А⊂Х жəне ΔАх⊂Гх∩А. «Дискретті математика» пәні мемлекеттік, жалпы білім беру стандартына сәйкес білім мен дағдыларды меңгеруді қамтамасыз етеді және сонымен бірге іргелі білім, дүниетанымын қалыптастыру және логикалық ойлауын дамыту. График теориясы дискретті объектілерге қатысты қазіргі заманғы инженерлік есептерді ресімдеудің тиімді құралы болып табылады. Ол интегралдық схемалар мен басқару схемаларын жобалауда, автоматтар мен логикалық схемаларды зерттеуде, жүйелік талдау, автоматтандырылған өндірісті басқару, компьютерлік және ақпараттық желілерді дамытуда, схемалық және конструкторлық-топологиялық жобалауда және т.б. AT оқу құралыграфиктер теориясының негіздерін, негізгі әдістері мен алгоритмдерін сипаттайды. Мұнда n-графтар мен диграфтар; изоморфизмдер; ағаштар; Эйлер графиктері; жазық графиктер; жабындар мен тәуелсіз жиынтықтар; күшті байланыс жылы диграфтар; Марковтың тізбекті графигін талдау; графиктердегі ең қысқа жолдарды табу алгоритмдері; Гамильтон циклін табу мәселесі жылы график; саяхатшы сатушы мәселесі; графиктер мен бейнелеулерді санау; экстремалды тапсырмалар; оңтайландыру мәселелері; әмбебап міндеттер; тармақтау және байланыстыру әдісі; сонымен қатар жоғарыда аталған ұғымдарды қолданудың практикалық дағдыларын дамыту. Курстың мақсаты – студенттерді қалыптастыру теориялық білім, жаратылыстану мен техникадағы процестер мен құбылыстарды модельдеу саласындағы практикалық дағдылар ке, пайдалану мүмкіндігімен математикалық белгілерақпараттық қауіпсіздік саласындағы қызметтік қызметті жоғары кәсіби деңгейде орындауға қажетті объектілердің сандық және сапалық қатынастарын білдіру. Осы мақсатқа жету үшін келесі міндеттер қызмет етеді: графтар теориясының ұғымдарының кең ауқымын зерттеу; оқу және практикалық мәселелерді шешу дағдыларын алу; оңтайландыру әдістерін меңгеру; жүктеу/скачать 336,61 Kb. Достарыңызбен бөлісу:
|