Алгоритмнің қолданбалы теориясы пәнінен емтихан сұрақтары 25 сұрақ деңгей
жүктеу/скачать 134,63 Kb.
|
Алгоритмнің қолданбалы теориясы пәнінен емтихан сұрақтары 25 сұр-emirsaba.org
- Бұл бет үшін навигация:
- Анықтама 3.
- Цикломатикалық сан.
| Рекурсивті функция - мәндері және аргументтері теріс емес бүтін сандар болатын y=f(x1,x2,...,xn) функциясы. Рекурсивті функция анықталу аймағына енетін аргументтердің x1,x2,...,xn мәндері бойынша у-ті есептеудің нақты ережелері де берілуі мүмкін. Осымен қатар, қандай да болмасын бір алгоритмнің көмегімен есептелетін функциямен теңестірілген жартылай рекурсив функция туралы ұғым да қалыптасқан.[1]
андай да бір сандық бөлшек функциялар берілсін: n-орынды орынды . G және h функциясынан (n+1) орынды f функциясы примитивті рекурсия арқылы алынады, егер у натурал сандар үшін Функцияның анықталу облысы натурал сандар жиыны болғандықтан, f-бөлшекті функция да (1)-ді қанағаттандырады,және ол функция әрбір g, h бөлшек функция үшін табылады және жалғыз болады. Рекурсия қадамы өзгерген сайын (1): (2) түрінде жазылады. Примитивті рекурсия f=R(g, h) деп белгіленеді. R- бөлшек функциялар жиынында анықталған 2-орынды бөлшек операция символы деп қарастырылады. (2)=> дербес жағдайда g және h барынша анықталған болады. (2)-дегі g және h функцияларының мәндері табылатын болса функцияның мәндері де механикалық есептеледі. Анықтама бөлшек функциясы примитивті рекурсия деп аталады, егер оны қарапайым функцияларға суперпозиция немесе примитивті рекурсия операцияларын қолданып, саны санаулы операциялармен алуға болса. Мысалы:
примитивті Анықтама: f(x1,x2,...xn) – бөлшекті функция бөлшекті рекурсивті деп аталады, егер оны қарапайым - функцияларынан суперпозиция , примитивті рекурсия , минимизация операцияларын санаулы рет қолданып алуға болса. Логикалық функциялардың ақиқаттық кестесін құрыңыз. Цифрлық құрылғылардың атқарар қызметі сәйкесті логикалық функциялар арқылы сипатталады. Күрделілігі әртүрлі кез келген логикалық функцияны негізгі логикалық функциялар деп аталатын үш функция арқылы суреттеуге болады, олар – ЕМЕС, НЕМЕСЕ, ЖӘНЕ функциялары. Олардың атқарар қызметін кесте түрінде (ол ақиқаттық кестесі деп аталады) немесе сәйкесті логикалық өрнек арқылы суреттеуге болады. ЕМЕС функциясы – аргументіне қарсы мәнді шығаратын, бір аргументті функция (1.1-кесте), сондықтан бұл функция инверсия (inversion - терістеу) деп те аталады. Оның аргументі Х деп белгіленген болса, онда бұл функция Y= өрнегімен суреттеледі. 1.1 К е с т е
НЕМЕСЕ функциясы – аргументтерінің барлығы да 0 кезінде ғана 0 шығаратын, ал қалған жағдайда (яғни, аргументтерінің кем дегенде біреуінің мәні 1 болғанда) 1 шығаратын, бірнеше аргументті функция (1.2-кесте). Бұл функция дизъюнкция (disjunction) немесе логикалық қосу (logical addition) деп те атала береді. Оның логикалық өрнегі Х1Х0 түрінде суреттеледі. 1.2 К е с т е
ЖӘНЕ функциясы – аргументтерінің барлығы да 1 кезінде ғана 1 шығаратын, ал қалған жағдайда (яғни, аргументтерінің кем дегенде біреуінің мәні 0 болғанда) 0 шығаратын бірнеше аргументті функция (1.3-кесте). Бұл функция конъюнкция (conjunction) немесе логикалық көбейту (logical multiplication) деп те атала береді. Оның логикалық өрнегі Х1Х0 (немесе Х1Х0) түрінде суреттеледі. 1.3 К е с т е
Суреттелген ЕМЕС, НЕМЕСЕ, ЖӘНЕ функциялары арқылы кез келген күрделі функцияны суреттеуге болады, сондықтан, олар логикалық функциялардың түпнегіздік жинағын (core set) құрады.
Графтардың берілу циклдерін атаңыз. Графтардың берілуі дегеніміз оның төбелері мен қабырғаларынан тұратын жиындарды сипаттау болып табылады. Төбелер мен қабырғаларды жай ғана нөмірлеуге болады. 1. Төбелері: 1, 2,..., n; Қабырғалары: e1, e2, …. ,en 2. Граф құрылымы туралы ақпарат бинарлы қатынас матрицасы арқылы да беріледі. Мысалы, G=‹M,R› граф болсын. М төбелер жиыны М={a1, a2,…,an}. R граф төбелерінің арасындағы бинарлы қатынас болсын. G-графының сыбайлас матрицасы деп төмендегідей анықталған n ретті A G ={Aij} матрицаны айтамыз. н-графта ai, aj төбелері іргелес болады, егер Aij=1 немесе Aji=1, яғни н-графта Aij= Aji=1 . Егер G мультиграф болса оның іргелестік AG матрицасының Aij элементтері анықтама бойынша ai төбесінен шығып aj төбесіне кіретін доғалардың санына тең (i,j{1,…,n}). Графтармен операциялар туралы ұғымдарды келтіріңіз. Анықтама 4. Егер М1М және R1R∩(M1)2 болса, яғни G1 графының төбелер жиыны G графы төбелер жиынына, ал G1 қабырғалар жиыны G графының қабырғалар жиынына жатса G1- G бөлігі деп аталады. Анықтама 5. Айталық. G=,G1=1,R1> графтары берілсін. Егер М1М және R1=R∩(M1)2 болса, яғни G1 графының төбелер жиыны G-ң төбелер жиынында жатса ал G1-ң доғалары екі жағымен де G графына жатса G1–G графының ішкі графы деп аталады. Анықтама 6. Егер Н графының төбелер жиыны V(H) мен қабырғалар жиыны E(H) G графының сәйкесінше төбелері мен қабырғалар V(G), E(G) жиындарында жатса және , онда Н графы G графының бөлігі деп аталады . Анықтама 7. Егер , G графының бөлігі Н суграф деп аталады. Егер G графының кез келген төбесі Н графының ең болмаса бір қабырғасына инцидентті болса , онда бағытталмаған Н графы G графын жабады дейміз. Эйлер циклдары және шынжырлар туралы түсініктер беріңіз. Байланысты бағытталмаған мультиграфтың әр төбесінің дәрежесі жұп сан болса ғана Эйлер циклы болады. Анықтама 1. Мультиграфтың барлық қабырғалары болатын цикл Эйлер циклы деп, ал Эйлер циклы бар граф Эйлер графы деп аталады. Жоғардағы суреттегі мультиграфта Эйлер циклы жоқ, себебі онда дәрежесі тақ төбе бар. Айталық ондай цикл бар деп жориық. Олай болғанда бұл циклдың бойымен жүре отыра графтың кез келген төбесіне одан шығу қанша болса сонша рет кіреміз. Демек, G графының әр төбесінің дәрежесі жұп болуы керек. G графында керісінше барлық төбелер тақ дәрежелі. Бұл тұжырым кез келген бағытталған G графына да жарамды. Сонымен бағытталмаған G графында оның барлық қабырғалары арқылы өтетін цикл бар болу үшін G графының төбелерінің дәрежесі жұп болуы қажетті. Анықтама 2. Бағытталмаған (бағытталған) G графындағы цикл оның барлық қабырғалары арқылы өтсе, ол- Эйлер циклы деп аталады. Бағытталмаған графта Эйлер циклы бар болу үшін бұл графтың байланысты болуы қажетті. Анықтама 3. Кез келген х,уV(G) төбелерін қосатын жол бар болса бағытталмаған G графы байланысты граф деп аталады. Анықтама 5. Айталық G(V,E) байланысты бағытталмаған граф. G графының барлық төбелері арқылы өтетін, басталуы мен аяқталуы әр түрлі төбелерде болатын қарапайым цикл Гамильтон циклы деп аталады.Графтарда Гамильтон циклдары мен шынжырлары бар болудың жеткілікті шартын келтірейік. Айталық дәр. v–vV төбесінің дәрежесі болсын. Теорема 2. Егер G (V, E), мұндағы |V|=n графында кез келген төбелер vi және vj жұбтары үшін дәр.vi +дәр.vj≥n-1, орындалса, графта гамильтон шынжыры бар, ал егер дәр.vi +дәр.vj≥n немесе дәр.vi≥n/2 графта Гамильтон циклы бар. Графтар саны: цикломатикалық, хроматикалық дегеніміз не? Цикломатикалық сан. Ұйғарым. G(X) графтың n төбесі, т қабырғасы және r байланысты компонентасы болсын. санды G графтың цикломатикалық саны деп атайды. Бұл санның физикалық мағынасы зор. Электр шынжырларын есептеудегі байланыссыз контурлар санын анықтауда қолданылады. жүктеу/скачать 134,63 Kb. Достарыңызбен бөлісу:
|