Алгоритмнің қолданбалы теориясы пәнінен емтихан сұрақтары 25 сұрақ деңгей
Белгілі бір Тьюринг машинасын анықтау үшін оның келесі компоненттерін сипаттау қажет
жүктеу/скачать 0,9 Mb.
|
- Бұл бет үшін навигация:
- Ішкі алфавит.
- Үстелге секіру.
- ЕТжәне БҚ кафедрасы мәжілісінде талқыланып, бекітілді. хаттама №5, 29.12.2020ж.
| Белгілі бір Тьюринг машинасын анықтау үшін оның келесі компоненттерін сипаттау қажет:
Сыртқы алфавит.Ақырлы жиын (мысалы, А), оның элементтері әріптер (таңбалар) деп аталады. Бұл алфавиттің әріптерінің бірі (мысалы, 0) бос таңба болуы керек. Ішкі алфавит.Бас (автомат) күйлерінің ақырлы жиыны. Күйлердің бірі (мысалы, q 1) бастапқы болуы керек (бағдарламаны іске қосу). Күйлердің екіншісі (q 0) түпкілікті болуы керек (бағдарламаны аяқтау) - тоқтату күйі. Үстелге секіру.Машинаның (бастың) күйіне және оқылған сипатына байланысты мінез-құлқын сипаттау. Тьюринг машинасының автоматы жұмыс барысында келесі әрекеттерді орындай алады: Сыртқы алфавиттің таңбасын ұяшыққа жазыңыз (соның ішінде бос), ішіндегісін (соның ішінде бос) ауыстырыңыз. Бір ұяшықты солға немесе оңға жылжытыңыз. Ішкі күйіңізді өзгертіңіз. Тьюринг машинасының бір пәрмені осы үш құрамдастың нақты комбинациясы болып табылады: ұяшыққа қандай таңбаны жазу керек (автомат оның үстінде орналасқан), қайда жылжыту керек және қай күйге бару керек нұсқаулар. Команда барлық құрамдастарды қамтымаса да (мысалы, таңбаны өзгертпеңіз, жылжытпаңыз немесе ішкі күйін өзгертпеңіз). 3 деңгей f(x,y)=x&y функциясы берiлген (1,1), (1,0) аралықта мәнiн тапыңыз. Жауабы: & бұл амал конъюнкция амалын (көбейту) білдіреді. Яғни f1(1,1)=1&1=1; f2(1,0)=1&0=1 және бейнелеулер берiлсiн. композицияны табыңыз: және бейнелеулер берiлсiн. композицияны табыңыз: А қаласынан В қаласына 2 жолмен, ал В қаласынан С қаласына 3 жолмен баруға болады. В қаласы арқылы А қаласынан С қаласына қанша әдiспен жетуге болады? Жауабы: Біз бұл есепте қосымша айнымалылар енгіземіз. A қаласынан B қаласына 2 жолмен баратындықтан біз оларды (x1,x2) деп аламыз. Ал B қаласынан С қаласына 3 жолмен баратын болғандықтан біз оларды (y1, y2, y3) деп аламыз. Шешуі: (x1,y1); (x1,y2), (x1,y3); (x2,y1); (x2,y2); (x2,y3) Жауабы: 6 әдіспен баруға болады. А қаласынан В қаласына 3 жолмен, ал В қаласынан С қаласына 5 жолмен баруға болады. В қаласы арқылы А аласынан С қаласына қанша әдiспен жетуге болады? Шешімі: Біз бұл есепте қосымша айнымалылар енгіземіз. A қаласынан B қаласына 3 жолмен баратындықтан біз оларды (x1,x2,x3) деп аламыз. Ал B қаласынан С қаласына 5 жолмен баратын болғандықтан біз оларды (y1, y2, y3, y4, y5) деп аламыз. Шешуі: (x1,y1); (x1,y2); (x1,y3); (x1,y4); (x1, y5); (x2,y1); (x2,y2); (x2,y3); (x2,y4); (x2, y5); (x3,y1); (x3,y2); (x3,y3); (x3,y4); (x3, y5) Жауабы: 15 әдіспен баруға болады. А қаласынан В қаласына 2 жолмен, ал В қаласынан С қаласына 3 жолмен баруға болады. А қаласынан С қаласына В дан өтпейтiн 2 жол бар. А қаласынан С қаласына қанша ´дiспен жетуге болады? Шешімі: Біз бұл есепте қосымша мән енгіземіз. A қаласынан B қаласына 2 жолмен баратындықтан біз оларды (x1,x2) деп аламыз. Ал B қаласынан С қаласына 3 жолмен баратын болғандықтан біз оларды (y1, y2, y3) деп аламыз. A қаласынан C қаласына B дан өтпейтін 2 жол болғандықтан оларды z1, z2 деп белгілейміз. Шешуі: (x1,y1); (x1,y2); (x1,y3); (x2,y1); (x2,y2); (x2,y3); z1; z3. Жауабы: 8 әдіспен баруға болады. А қаласынан В қаласына 3 жолмен, ал В қаласынан С қаласына 5 жолмен баруµа болады. А қаласынан С қаласына В дан өтпейтiн 4 жол бар. А қаласынан С қаласына қанша әдiспен жетуге болады? Шешімі: Біз бұл есепте қосымша мән енгіземіз. A қаласынан B қаласына 3 жолмен баратындықтан біз оларды (x1,x2,x3) деп аламыз. Ал B қаласынан С қаласына 5 жолмен баратын болғандықтан біз оларды (y1, y2, y3, y4, y5) деп аламыз. A қаласынан C қаласына B дан өтпейтін 4 жол болғандықтан оларды z1, z2, z3, z4 деп белгілейміз. Шешуі: (x1,y1); (x1,y2); (x1,y3); (x1,y4); (x1,y5); (x2,y1); (x2,y2); (x2,y3); (x2,y4); (x2,y5); (x3,y1); (x3,y2); (x3,y3); (x3,y4); (x3,y5); z1; z2; z3; z4. Жауабы: 19 әдіспен баруға болады. А – 30 дан үлкен емес, 3 ге бөлiнетiн натурал сандар жиыны. мәнін есептеңіз Жауабы: 3, 6, 9, 12, 15, 18, 21, 24, 27, 30 А – 15 тен үлкен емес, 3 ге бөлiнетiн натурал сандар жиыны. мәнін есептеңіз Жауабы: 3, 6, 9, 12, 15 А – 12 ден үлкен емес жұп натурал сандар жиыны. мәнін есептеңіз Жауабы: 2, 4, 6, 8, 10, 12 , . дәлелдеңіз, табыңыз. есептеңіз. Жауабы: 7*7*7=343 Айталық болсын. табыңыз. Жауабы: A мен В ның бірігуі: 1,2,3,4,5,6,7,8 B∩C={2,4} A\C={7} B дельта С: {1,3,5,6,8} формулаға пара-пар тек және амалдары көмегімен құрылған формуланы табыңыз. 1, 1, 2, 3, 3 цифрлардың көмегiмен қанша бес таңбалы сан жазуға болады? Бұл есепті n! формуласымен шығарамыз. Бұл жерде n деп отырғанымыз Шешуі: 5!/2!*1!*2!=120/4=30 болады теңдік дұрыс екеніне көз жеткізіңіз. 3, 3, 3, 8, 8 цифрлардың көмегiмен қанша бес таңбалы сан жазуға болады? «Математика» сөздiң әрiптерiн ауыстыра отырып қанша сөз алуға болады? Жауабы: Біз бұл есепте комбинаториканың орын ауыстыру формуласын пайдаланамыз. P(n1,n2,n3..nk)=n!/n1!n2!n3!...nk! Бұл жерде n деп отырғанымыз әріптердің жалпы саны. Ал n1 дегеніміз сөзде кездескен м әріпінің жалпы саны, n2 дегеніміз а әріпінің жалпы саны, т.с.с. Шешуі: P(2,3,1,1,1)=10!/(2!*3!*2!*1!*1!*1!)=604800/2*2!=302400/2=151200 Топта 25 студент оқиды, олардың ішінде 13 – ағылшын тілін, 12 – неміс, 13 – француз, 4 студент ағылшын және француз, 6 – ағылшын және неміс, 5 – неміс және француз тілдерін біледі. Қанша студент үш тілді біледі? (8 бал) тепе-теңдікті дәлелдеңіз. , . , , табыңыз. Жауабы: = {1,2,4,5,6,8,9,10} ={2,6} тепе-теңдікті дәлелдеңіз Жауабы: Айталық болсын. табыңыз. формулаға пара-пар тек және амалдары көмегімен құрылған формуланы табыңыз. жиыны А = {1, 2, 3, 4, 5, 6} жиынындағы қатынасты анықтайды. Оған жататын барлық реттелген жұптарды табыңыз. ДНФті табыңыз: (x~y) ( zT ). A(G) матрица берілген. Графты салыңыз. ; Ақиқат кестесін құрыңыз: Жауабы: B(G) матрица берілген. Графты салыңыз. ; 30 . Ақиқат кестесін құрыңыз: 31. есептеңіз. 32. Ықшамдаңыз: 33. 5 бояудан 3 мәртүрлі бояуды неше тәсілмен таңдауға болады? 34. формуласының конъюктивті формасын табыңыз. 35. Көрермен залында 120 орын бар. Ол жерге 120 адамды; 80 адамды неше тәсілмен орналастыруға болады? 37. жиындары берілсін. Бұл жиындар үшін тура көбейтінділерін табыңыз. 38. Де Морган заңын (қосалқы принципі) теңдігін дәлелдеңіз. 39. жиыны берілсін. А жиынының бүркеуін есептеңіз. Жауабы: {1,2};{2,3};{3,1}. 40. жиыны берілсін. А жиынының бөлікшесін есептеңіз. Жауабы: {1};{2};{3};{4};{5} 41. 2, 3, 4 сандарының образы мен прообраздарын табыңыз.. 42. A={a,b,c}; B={1,2,3} жиындары берілсін. Олардың элементтерінің арасындағы 43. P1={(a,2),(b,1),(c,2)} қатынасын суретпен кескіндеңіз. 44. Келесі тепе-теңдікті дәлелдеңіз. а bab; 45. Графтың сыбайластық матрицасымен берiлген графты салыңыз. ЕТжәне БҚ кафедрасы мәжілісінде талқыланып, бекітілді. хаттама №5, 29.12.2020ж. жүктеу/скачать 0,9 Mb. Достарыңызбен бөлісу:
|