1. 1Жиын ұғымы. Шекті және шексіз жиындар. Жиындарды анықтау тәсілдері.Ішкі жиындар. Берілген жиынның барлық жиынтығы. К- элемент жиындарының саны туралы n- элемент жиынтығы
жүктеу/скачать 336,61 Kb.
|
1. 1Жиын ??ымы. Шекті ж?не шексіз жиындар. Жиындарды аны?тау т?с
| Дейкстра Алгоритмі
Дийкстра алгоритмі – графиктің бір төбесінен екіншісіне ең қысқа жолды табатын әдіс. График - бұл жиектер-сегменттермен байланысқан нүкте-төбелердің құрылымы. Оны жол картасы немесе компьютерлік желі ретінде қарастыруға болады. Жиектер - қосылыстар, олардың бойымен бір шыңнан екіншісіне өтуге болады. Ең қысқа жолды табудың мысалын қарастырыңыз. Қаланың аймақтарын байланыстыратын автомобиль жолдарының желісі берілген. Кейбір жолдар бір жақты. Қала орталығынан аудандағы әрбір қалаға дейінгі ең қысқа жолдарды табыңыз. Бұл мәселені шешу үшін 1959 жылы голланд ғалымы Э.Дейкстра ойлап тапқан Дийкстра алгоритмі – графиктер бойынша алгоритмді қолдануға болады. Графиктің бір төбесінен барлық басқаларына дейінгі ең қысқа қашықтықты табады. Теріс салмақтың жиектері жоқ графиктер үшін ғана жұмыс істейді. 1- ші шыңнан қалғандарына дейінгі ең қысқа қашықтықтарды табу талап етілсін. Графиктегі ең қысқа жолдарды табуға арналған көптеген алгоритмдердің ішінен Хабреде мен Флойд-Уоршалл алгоритмінің сипаттамасын ғана таптым. Бұл алгоритм графиктің барлық шыңдары мен олардың ұзындығы арасындағы ең қысқа жолдарды табады. Бұл мақалада мен Дийкстра алгоритмінің жұмыс принципін сипаттайтын боламын, ол оңтайлы маршруттарды және олардың бір нақты шыңы (көзі) және графиктің барлық басқа шыңдары арасындағы ұзындығын табады. Бұл алгоритмнің кемшілігі, егер графикте теріс салмақты доғалар болса, ол дұрыс жұмыс істемейді. Есеп: 1) Банкте 10 салымшының салым мөлшері туралы деректер берілген: 300,380,480,350,450,560,250,400,500,200 (мың тг.). Салым көлемін тең аралыкты 3 топка белiп, салымшыларды белудің интервалды вариациялық қатарын құрыңдар. Әрбір топ бойынша салымдардың жалпы мөлшерін есептендер. 2) у=х2 болатын кездейсоқ шаманын мәндерiн табыныз 3) Тиын 5 рет лақтырылды. Х дискретті кездейсоқ шамасы елтаңбаның түсу санының үлестірім кестесін құрастырыңдар және үлестірім гистограммасын құрастырыңдар. 4) Ойын суйегiн 6 рет лактырганда 6 турлi сан тустi. Олардың қосындысын 3-ке бөлгенде шығатын белiндiнiн мәнiн табыңыз. (Ойын суйегі: жактары 1-ден 6-ға дейiн нөмірленген кубик) 3.1. Сыртқы терістеулері бар мәлімдемелер. Сыртқы терістеу мәлімдемесі - белгілі бір жағдайдың жоқтығы расталған мәлімдеме (үкім). Көбінесе «бұл дұрыс емес...» немесе «бұл дұрыс емес...» деген тіркестермен басталатын сөйлем арқылы айтылады. Сыртқы терістеу «ù» таңбасымен белгіленеді, терістеу белгісі деп аталады. Бұл белгі келесі ақиқат кестесімен анықталады: Сыртқы терістеулері бар мәлімдемелерде А-дағы жағдай теріске шығарылады.Мысалы, А: «Еділ Қара теңізге құяды» десе, ùА: «Еділ Қара теңізге құяды деген дұрыс емес». конъюнктивтік сөйлемдер. Конъюнктивтік мәлімдемелер - бұл екі жағдайдың бір мезгілде болуы расталған. Конъюнктивтік сөйлемдер «және», «а», «бірақ» одақтарының көмегімен екі мәлімдемеден жасалады. Конъюнктивті айтылым түрі: (A&B). А және В мәлімдемелерінің әрқайсысы «ақиқат» мәнін де, «жалған» мәнін де қабылдай алады. Бұл мәндер қысқа болу үшін әріптермен белгіленеді мен, л. Конъюнктивтік мәлімдемелер үшін ақиқат кестесі келесідей: Конъюнктивтік сөйлемдерде А және В-де сипатталған жағдайдың бір мезгілде орын алатыны айтылады. Конъюнктивтік сөйлемдерге мысалдар: «Жер – планета, ал Ай – серік»; «Петров логиканы жақсы меңгерген, ал Сидоров логиканы нашар меңгерген»; «Сыртта қараңғы, аудиторияда шамдар жанып тұр»; «Петров шенеунікке қолма-қол пара берді, ал Сидоров оған бөтелке берді». ажыратқыш мәлімдемелер. Дизъюнктивтік мәлімдемелер А және В тармақтарында сипатталған екі жағдайдың кем дегенде біреуінің бар екенін растайтын мәлімдемелер болып табылады. Дизъюнкция V таңбасымен белгіленеді және табиғи тілде «немесе» одағының көмегімен көрсетіледі. Дизъюнкция белгісінің кестелік анықтамасы келесідей: Дизъюнктивтік сөйлемге мысал: «Роман Сергеевич Иванов - оқытушы, немесе Роман Сергеевич Иванов - аспирантура». Қатаң дизъюнктивтік мәлімдемелер. А және В тармақтарында сипатталған екі жағдайдың дәл біреуінің бар екендігін дәлелдейтін қатаң дизъюнктивтік мәлімдемелер. Мұндай мәлімдемелер көбінесе «немесе ..., немесе ...» («немесе ...» немесе ...» одағының көмегімен сөйлемдер арқылы жүзеге асырылады. ..., немесе ...»). Қатаң дизъюнкция V* белгісімен белгіленеді («не... немесе...» оқыңыз). Қатаң дизъюнкция белгісінің кестелік анықтамасы келесідей: Қатаң дизъюнктивтік сөйлемнің мысалы: «Не сыртта күн ашық, не жаңбыр жауады». 3.2. Ақиқат кестесі - кірістер мен олардың сәйкес шығыстары үшін мәндердің барлық комбинацияларының кестелік көрінісі . Бұл факті деп саналатын барлық ықтимал сценарийлерден болатын барлық ықтимал нәтижелерді көрсететін математикалық кесте, демек, атау. Ақиқат кестесінде не бар? Ақиқат кестесі - бұл функция қол жеткізе алатын барлық мүмкін мәндерді тізімдеу арқылы логикалық функцияның бөлінуі . Мұндай кестеде әдетте бірнеше жолдар мен бағандар болады, жоғарғы жол логикалық айнымалылар мен комбинацияларды білдіреді және соңғы функцияға әкелетін күрделілікті арттырады. Ақиқат кестелерінің мәні неде? Ақиқат кестесі — сценарийдің ықтимал нәтижелерін бейнелейтін логикалық негізделген математикалық кесте. Ақиқат кестесі берілген сценарийде орын алатын ақиқат мәндерін қамтиды. Нәтижеде кесте аргументтің сценарийде логикалық (шын) екендігін визуализациялауға көмектеседі. Ақиқат кестесі нені түсіндіреді? Ақиқат кестесі — логикада қолданылатын математикалық кесте, атап айтқанда, логикалық алгебрамен, логикалық функциялармен және болжамдық есептеулермен байланысты — ол логикалық өрнектердің функционалдық мәндерін олардың әрбір функционалды аргументіндегі , яғни қабылданған мәндердің әрбір комбинациясы үшін белгілейді. олардың логикалық айнымалылары бойынша. Ақиқат кестесінің оңай анықтамасы дегеніміз не? Ақиқат кестесі, логикада, құрамдастарды құрайтын ұсыныстардың ақиқат мәндерінің әрбір мүмкін комбинациясы үшін бір немесе бірнеше құрама ұсыныстардың ақиқат мәнін көрсететін диаграмма . Оны аргументтердің дұрыстығын тексеру үшін пайдалануға болады. Ақиқат кестесі оқу құралы – Дискретті математикалық логика Ақиқат кестесінің басқа аты қалай аталады? ақиқат кестесінің басқа атауы - ақиқат функциясы . Шындық кестелері өмірде қалай қолданылады? Логикалық аргумент құрылымы дұрыс екенін анықтау үшін ақиқат кестелерін пайдалана аламыз. Логикалық аргументтің құрылымы дұрыс екенін анықтау үшін алдымен аргументімізді әріптер мен логикалық жалғауларды пайдаланып жазылған логикалық мәлімдемелер қатарына аударуымыз керек. Шындық кестелеріндегі V нені білдіреді? Бұл « бір немесе екіншісі» немесе екеуі де дегенді білдіреді. НЕМЕСЕ немесе логикалық ажырату операторын көрсету үшін қолданылатын таңба ∨болып табылады. Ол әліпбидегі V әрпіне ұқсайды. Ақиқат кестесі дегеніміз не және оның маңызы? Ақиқат кестесі - бұл функция қол жеткізетін барлық мәндерді тізімдеу арқылы логикалық функцияның бөлінуін беретін математикалық кесте . Логикалық қақпалардың ақиқат кестесі бізге логикалық операция үшін кірістер мен олардың сәйкес шығыстарының комбинациясы туралы барлық ақпаратты береді. Буль логикасында қандай 3 заң бар? Қосу және көбейту орнын өзгертуге мүмкіндік беретін ауыспалы заңға, қосу және көбейтуге жақшаларды алып тастауға мүмкіндік беретін Ассоциативті заңға , сондай-ақ өрнектің факторингіне рұқсат беретін үлестіру заңына қатысты Буль алгебрасының негізгі заңдары мыналар болып табылады. кәдімгідей... 0 шын ба, жалған ба? Нөл жалғанды көрсету үшін қолданылады , ал One шынды көрсету үшін қолданылады. Түсіндіру үшін Нөл жалған деп түсіндіріледі және нөлден басқа кез келген нәрсе ақиқат деп түсіндіріледі. Өмірді жеңілдету үшін C бағдарламашылары әдетте сәйкесінше 1 және 0 мәндері болуы үшін «шын» және «жалған» терминдерін анықтайды. Екі өтірік шындықты жасайды ма? Ақиқат кестелері ЖӘНЕ, НЕМЕСЕ және ЕМЕС негізінде екі логикалық шартты қалай біріктіретінімізді қорытындылайды. Логика бізге екі нәрсе жалғасу үшін ақиқат болуы керек болса , шарт_1 ЖӘНЕ_2 шарттың екеуі де ақиқат болуы керек екенін айтады. Ақиқат болу үшін ол екі нәрсенің біреуін ғана алса, шарт_1 НЕМЕСЕ_2 шарты ақиқат болуы керек. Деморган теоремасы дегеніміз не? Де Морган теоремасы, T12, сандық дизайндағы ерекше қуатты құрал. Теорема барлық мүшелердің көбейтіндісінің толықтауышы әрбір мүшенің толықтауыштарының қосындысына тең болатынын түсіндіреді . ... Де Морган теоремасы бойынша NAND қақпасы кірістері инверттелген НЕМЕСЕ қақпасына эквивалентті. Ақиқат кестелеріндегі тавтология дегеніміз не? Тавтология «әрдайым ақиқат» формуласы --- яғни оның қарапайым компоненттеріне ақиқат мәндерінің әрбір тағайындалуы үшін ақиқат . Тавтологияны логика ережесі ретінде қарастыруға болады. Тавтологияға қарама-қайшылық, «әрқашан жалған» формула. ... және формуланың әрқашан ақиқат екенін көрсетіңіз. P → Q нені білдіреді? Шартты ұсыныстар . «p → q» түрінде ұсынылған «егер p болса, q» немесе «p q білдіреді» түріндегі ұсыныс шартты ұсыныс деп аталады. ... p ұсынысы гипотеза немесе антецедент деп аталады, ал q ұсынысы - қорытынды немесе нәтиже. p → q әрқашан ақиқат екенін ескеріңіз, егер p ақиқат болса, q жалған болса. Ақиқат кестесіндегі P және Q дегеніміз не? Олар енгізілген ұсыныстар үшін ақиқат-мәндердің барлық ықтимал нәтижелерін тізімдеу арқылы ұсыныс мәлімдемелерінің ақиқаттығын немесе жалғандығын анықтау үшін қолданылады. ... Берілген екі ұсыныс, p және q, «p және q» жалғаулықты құрайды . «p және q» конъюнкциясы тек p және q екеуі де ақиқат болса ғана дұрыс болады. P ∨ Q шын мәні неге тең? Дизъюнкция p және q ұсыныстар болсын. p ∨ q деп белгіленген p және q дизъюнкциясы «p немесе q» ұсынысы болып табылады. p ∨ q ақиқат мәні жалған болады, егер p және q екеуі де жалған болса . Әйтпесе, бұл рас. Ақиқат кестелерінде реттілік маңызды ма? Үй-жайға қалай тапсырыс берсеңіз де, қорытынды логикалық түрде орындалмайды . Сіздің ақиқат кестеңіз барлық шарттарда P бағалауының соңғы бағанын өткізіп алды. Әрине, P жалған болса, алдыңғы бағандарда не бар екеніне қарамастан, ол жалған болады. Шындықтың мәні қандай? Ақиқат мәні: мәлімдеменің ақиқат немесе жалған болу қасиеті . Барлық мәлімдемелер («мәлімдемелер» анықтамасы бойынша) ақиқат мәніне ие; Біз көбінесе ақиқат мәнін анықтауға, басқаша айтқанда, мәлімдеменің ақиқат немесе жалған екенін анықтауға мүдделіміз. Ақиқат кестесін пайдаланып аргументтің жарамды екенін қалай анықтауға болады? Жалпы, негізділігін анықтау үшін БАРЛЫҚ алғышарттар ақиқат және қорытынды жалған болатын жолды табу үшін ақиқат кестесінің әрбір жолын өтіңіз . Сіз осындай қатарды таба аласыз ба? Олай болмаса, аргумент жарамды. Егер бір немесе бірнеше жол болса, онда аргумент жарамсыз. Бульдік ақиқат кестесі дегеніміз не? Логикалық қақпа функциясының логикалық өрнегін көрсету үшін пайдаланылатын кесте әдетте шындық кестесі деп аталады. ... Логикалық қақпаның ақиқат кестесі осы кірістердің тіркесіміне байланысты нәтиже шығысы бар қақпаға немесе тізбекке әрбір ықтимал кіріс комбинациясын көрсетеді. NAND ақиқат кестесі дегеніміз не? NAND қақпасы ЖӘНЕ және ЕМЕС қақпасының тіркесімі болып табылады . Олар каскадты түрде қосылған. Оны теріске шығарылған және қақпасы деп те атайды. NAND қақпасы олардың шығыстары жоғары немесе ақиқат болғанда ғана жалған немесе төмен шығысты қамтамасыз етеді. XOR символы қандай? ⊕, Jpq және ⊻ логикалық таңбаларын алгебралық өрнектердегі XOR операциясын белгілеу үшін пайдалануға болады. С-тәрізді тілдер биттік XOR-ды белгілеу үшін ^ карет таңбасын пайдаланады. (Символ ұқсастығына қарамастан, каретка бұл тілдерде логикалық конъюнкцияны (ЖӘНЕ) білдірмейтінін ескеріңіз.) жүктеу/скачать 336,61 Kb. Достарыңызбен бөлісу:
|