Алгоритмнің қолданбалы теориясы пәнінен емтихан сұрақтары 25 сұрақ деңгей
жүктеу/скачать 134.63 Kb.
|
| 4. Сырттай тұрғын жиындар.
G(X) – граф, . А. Егер Т-ға тиісті болмаған кез келген төбені Т-ға тиісті болған төбемен доға арқылы қосуға болса, онда Т жиынды сырттай тұрғын деп атайды. Демек, Ø. Элементтерінің саны ең кіші болған сырттай тұрғын жиындарды ең кіші сырттай тұрғын жиындар деп атайды. Бұл жиынның элементтері саны G(X) графтың сырттай тұрғындық саны деп аталады. Кодтау теориясының элементтері және Хэмминг арақашықтығы дегеніміз не? - алфавит болсын. U жиынындағы символдардың ақырлы тізбегі U алвафитінде сөз деп аталады. U алфавитіндегі барлық сөздердің жиынын S(U) арқылы белгілейміз. Айталық U және B – екі алфавит болсын. кездейсоқ ішкіжиынының ішкіжиынына бірмәнді F бейнелеуін кодтау деп атаймыз. Мұнда M ішкіжиынындағы сөздер хабарламалар, ал олардың бейнесі – хабарламалар кодтары деп аталады. С жиыны М хабарламалр жиынының коды деп аталады. U алфавиті хабарламалар алфавиті, ал В алфавиті – кодтаушы алфавит деп аталады. Ғ кодтау хабарламаның әрбір коды бір хабарлама коды болса өзара бірмәнді деп аталады. Мәтіндерді кодтаудың үш тәсілі бар: 1) графикалық – арнаулы белгілер, суреттер көмегімен; 2) сандық – сандар көмегімен; 3)символдық – негізгі мәтін жазылған алфавиттегі символдар көмегімен. Ағаштар, ағаштардың қасиеттері, діңгекті ағаштар туралы негізгі ұғымдарға түсініктеме беріңіз. Ағаш циклдары жоқ ерікті когерентті график деп аталады. Ағаштардың келесі қасиеттері бар: кез келген екі шың бір үзіліс тізбегімен жалғанған шеттер саны шыңдар санынан бір бірлікке аз кез келген жиекті алып тастағанда ағаш біртұтас емес графикке айналады ағашқа кез-келген қабырға қосылғанда, ағашта дәл бір қарапайым цикл пайда болады. Шындығында ағашты кез келген біріктірілген графиктен алуға болады Мәлімдеме: кез-келген біріктірілген графикте а діңгек субграфы бұл ағаш. Бұл субграф негізгі ағаш деп аталады. Арнайы ағаш түрлері 1 тамыр ағаштары Анықтама: тамыр ағашы-жағдайды қанағаттандыратын бағдарланған ағаш: a) дәл бір түйін бар, оған бір емес қабырға, бұл түйін-тамыр Тамырдан басқа әр түйінге дәл бір қабырға кіреді Тамырдан кез-келген шетке жол бар. Егер vl шыңынан v2 шыңына дейінгі жол болса, онда VL шыңы v2 шыңының атасы, ал v2 шыңы VL шыңының ұрпағы. Ұрпақтары жоқ шың соңғы шың немесе жапырақ деп аталады. Шеткі емес шыңды Ішкі деп атайды. Егер v1 және V2 тамыр ағашының доғасы болса, онда v1-әке, a v2-ұл Ағаштың тереңдігі-тамырдан жолдың ұзындығы. Бір тереңдікте орналасқан түйіндер ағаш қабаттары деп аталады. Тамыр ағашын орнату үшін кез-келген график үшін қолданылатын әдістерді қолдануға болады. Іс жүзінде ағаштарды бейнелеу үшін канондық әдіс қолданылады: әр түйін үшін әкесінің көрсеткіші сақталады. 2 екілік ағаштар Анықтама: екілік ағаш-әр шыңында екі ұлдан аспайтын тамыр ағашы. Мұндай ағашта кез-келген ерікті түйіннің сол және оң ұлы болады. Тамыры сол жақ ұлы болып табылатын кіші ағаш сол жақ кіші ағаш деп аталады. Тамыры оң ұл болып табылатын ішкі ағаш оң жақ ішкі ағаш деп аталады. Екілік ағаштарды бейнелеудің екі әдісі бар: 1. Екі массив түрінде ұсыну: бірінші массив - сол жақ ұлдары, екіншісі - оң. 2. Тізім құрылымы түріндегі көрініс tree_ ptr Tree_mode-құрылымы бар жазба: Элемент-түйін түрі; Сол: tree_ ptr; оң: tree_ ptr; Графтарға қолданылатын амалдар атаңыз, мысал келтіріңіз. G= графына а төбесін қосқаннан <М{a}, R> графы құралады. жүктеу/скачать 134.63 Kb. Достарыңызбен бөлісу:
|