Аға оқытушылар: Улжибаева Ғ. Ш., Кудышева Г. О., доцент, п.ғ. к
U көпшесін айтады (сур. 1.4, в). A \ Мысал. Егер , U
жүктеу/скачать 1,08 Mb. Pdf көрінісі
|
U көпшесін айтады (сур. 1.4, в). A \
, U } 2 , 1 , 0 { = A } 5 , 4 , 3 , 2 , 1 , 0 { = , онда =
U } 5 , 4 , 3 { \ = A . Сурет 1.3 – Көпшелермен әрекеттер: а) А және В көпшелерін айырымы; б) А көпшеcін әмбебап U көпшеcіне толықтыру Логика негіздері Математикалық логиканың негізін қалаған ағылшын математигі Джордж Буль (1815 – 1864). Ол алғашқы рет көпше теориясының логикалық түсіндірме идеясын айтты. Элементтері 0 және 1 болатын екі элементті В көпшесін қарастырайық. Мұндағы 0 және 1 сандары логикалық айнымалылар «ИЯ - ЖОҚ» немесе «АҚИҚАТ - ЖАЛҒАН» мәндерін түсіндіреді. Мысалы: бағдарламалау тілдерінде айнымалының арнайы түрі – логикалық айнымалы TRUE және FALSE енгізіледі. Осылай B={0,1} көпшесінің элементтерін сандар түрінде емес, формальды символдар ретінде қарастырамыз. В көпшесі және онымен жасалатын барлық әрекеттермен құрылған алгебраны логика алгебрасы немесе Бульдік алгебра деп атайды. Логика алгебрасының негізгі функциялары: Логикалық теріске шығару (инверсия) аргумент үстінде сызықшамен белгіленеді. Бұл бір айнымалының функциясы: f(x) = x; 0 =1; 1=0. Логикалық қосу (дизъюнкция). Бұл бірнеше айнымалының функциясы. Функция келесі түрде белгіленеді: f(x
1 ,x 2 ) = x 1 V x 2 V x
3 …
Екі айнымалы үшін ақиқаттық кестенің түрі болады: x 1 x 2 f(x 1 ,x 2 ) 0 0 0 0 1 1 1 0 1 1 1 1 Логикалық көбейту (конъюнкция). Бұл бірнеше айнымалының функциясы. Функция келесі түрде белгіленеді: f(x
1 x 2 ) = x 1 /\ x 2 /\ х
3 … Екі айнымалы үшін ақиқаттық кестенің түрі болады: x 1 x 2
f(x 1 ,x 2 ) 0 0
0 0 1
0 1 0
0 1 1
1 4. Шеффер функциясы – теріске шығарып көбейтуді орындайды. Бұл бірнеше айнымалының функциясы. Екі айнымалы үшін ақиқаттық кестенің түрі болады: x 1
x 2 f(x 1 x 2 ) 0 0
1 0 1
1 1 0
1 1 1
0 Функция келесі түрде белгіленеді: f(x 1
2 ) = x
1 ⏐x 2 = x 1 /\ x 2
Пирс функциясы теріске шығарып қосуды орындайды. Екі айнымалы үшін ақиқаттық кестесі былай анықталады: x 1 x 2 f(x 1 x 2 ) 0 0
1 0 1
0 1 0
0
1 1 0 Функция келесі түрде белгіленеді: f(x 1
2 ) = x
1
↓ x 2 = x
1
∨ x 2
Дизъюнкция және конъюнкция функциялары тек екі аргументтің функциялары ғана емес, жалпы алғанда еркін аргументтердің. 6. mod 2 бойынша қосу. XOR логикалық операциясын орындайды. Бұл бірнеше айнымалының функциясы. Екі айнымалы үшін ақиқаттық кестенің түрі болады: x1 x2 Y 0 0 1 1 0 1 0 1 0 1 1 0 Функция түрі болады Y =x 1
2 “N” айнымалыдағы кезкелген логикалық функция сол жағында айнымалылар мәндерінің барлық 2 n жиынтығы, ал оң жағында – осы жиынтықтардағы функция мәндері түгенделген кестемен берілуі мүмкін. Мысалы, 3 айнымалы үшін болады :
x
x 2 x 3 f 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 1 0 0 1 1 0 0 Фнкция f=1 болатын х жинақтарын(жолдарын) бірлі-жарым жинақтар, ал бірлі-жарым жинақтар көпшесін f-тің бірлі-жарым жинағы деп атайды. f=0 болатын х жинақтарын, f - тің нөлдік жинағы деп атайды. Кестедегі мәндерден логикалық функцияны құрайық. Ол үшін Функция бірге тең жолдардағы аргументтердің конъюнкциясын аламыз. Егер аргумент нөлге тең болса – ол инверсиямен алынады. Егер аргумент бірге тең болса – ол инверсиясыз алынады. Алынған конъюнкцияларды дизъюнкциялармен біріктіреміз. Біздің мысалда үш конъюнкция бар (функция мәні бірге тең болатын кестенің үш жолы) Логикалық функция түрі болады:
f = (X1 /\ X2 /\ X3) \/ (X1 /\ X2 /\ X3) \/ (X1 /\ X2 /\ X3) Инверсия аргумент үстінде сызықпен белгіленеді. Бірінші конъюнкцияда Х1, Х2 аргументтері инверсиямен алынған, үйткені кестенің екінші жолында олардың мәндері нөлге тең. Екінші конъюнкцияда Х2, Х3 аргументтері инверсиямен алынған, үйткені кестенің бесінші жолында олардың мәндері нөлге тең. Үшінші конъюнкцияда Х2 аргументі инверсиямен алынған, үйткені кестенің алтыншы жолында оның мәні нөлге тең. Алынған конъюнкциялар дизъюнкция операциясымен біріктірілген.
1. Орнын ауыстыру заңы. Коммутативтік (лат. – айырбастау, қайта айырбастау). X
1
∨ X 2 = X
2
∨ X 1 X 1
2 = X
2
∧ X 1
2. Үйлестіру заңы. Ассоциативтік (лат. – біріктіру). X 1
∨ (X 2
∨ X 3 ) = (X 1
∨ X 2 ) ∨ X 3
X 1
∧ (X 2
∧ X 3 ) = (X
1
∧ X 2 ) ∧ X 3
3. Тарату заңы. Дистрибутивтік. X 1
∧ (X 2
∨ X 3 ) = (X 1
∧ X 2 ) ∨ (X 1
∧ X 3 )
X 1
∨ (X 2
∧ X 3 ) = (X 1
∨ X 3 ) ∧ (X 1
∨ X 3 ) 4. Жұтыну заңы. X 1
∨ (X 1
∧X 2 ) = X 1 X
1
∧(X 1
∨ X 2 ) = X
1
5. Желімдеу заңы. X 1 X 2
∨ X 1 X 2 = X 1 (X 1
∨ X 2 )(X
1
∨ X 2 ) = X
1
6. де Морган ережесі. X
1
∨ X 2
∨ X 3 = X
1 X 2 X 3 ; X 1 X 2 X 3 = X 1
∨ X 2
∨ X 3
Логикалық операцияларды орындау келесі кестеде көрсетілген приоритетпен (басымдылықпен) жасалады.
басымдылығы операция 1 2 3 4 инверсия конъюнкция дизъюнкция mod 2 бойынша қосу
Бір басымдылықтағы операциялар солдан оңға қарай орындалады. Операциялардың орындалу ретін өзгерту үшін жақшалар қолданылады. Жақша ішіндегі операциялар бірінші ретте орындалады. Графтар мен ағаштар АҒАШТАР, БАҒЫТТАЛМАҒАН ЖӘНЕ БАҒЫТТАЛҒАН ГРАФТАР Граф құрылымы(синонимі ретінде «тармақ» термині қолданылады), нформатикада және жақын қолданбалы аймақтарда әртүрлі пайдаланымда, сондықтан графтар теорисының негізгі түсініктерімен танысып өтейік.
Граф G = (V, Е) V және Е соңғы көпшелері жұбымен беріледі. Бірінші көпше элементтері v1, v2,..., vM графтың шыңы деп аталады ал (графикалық көріністе оларға нүктелер сәйкес). Екінші көпше элементтері el, e2, ..., eN қабырғалар деп аталады. Әр қабырға шыңдар жұбымен анықталады (графикалық көріністе қабырғалар графтың екі шыңын қосады). Егер граф қабырғалары шыңдардың реттелген жұбымен анықталса, онда мұндай граф
қабырғаға оның бағытын анықтайтын стрелкалар қойылады). Бес шыңы және жеті қабырғасы бар бағытталған граф сур. 2.1 кескінделген.
Сурет 2.1 - Бағытталған граф мысалы
Егер екі шың екі немесе одан да көп қабырғалармен қосылса, онда мұндай қабырғалар параллельді деп аталады (мысалы, қабырғалар е4 және е5). Егер қабырғаның басы мен аяғы бір жерден шықса, онда мұндай қабырға ілмек (петля) деп аталады(мысалы, қабырға e7). Ілмексіз және параллельді қабырғаларсыз графтар қарапайым деп аталады. Егер ек қабырғасы vi және vj шыңдарымен анықталса (бұл фактіні келесідей белгілейміз: ек = (vi, vj), онда, қабырға ек vi, vj шыңдарына қақтығысты (инцидентті) деп атайды. Екі шың vi және vj шектес деп аталады, егер графта vi, vj қабырғалары болса). 1 vik, шыңдарының тізбегі граф G-дағы маршрут деп аталады. vil и vik шыңдарын _ маршруттың ақырғы шыңдары, оған кіретін басқа қалған шыңдарды – ішкі деп атайды. Анықталған барлық қабырғалары әртүрлі болатын маршрутты тізбек (цепь) деп атайды. Тізбек тұйықталған деп есептеледі, егер оның ақырғы шыңдары дәл түссе. Барлық шыңдары (ақырғыларынан басқасы) әртүрлі болатын тұйықталған тізбек цикл деп аталады. Барлық шыңдары әртүрлі болатын тұйықталмаған тізбек жол деп аталады. Егер бағытталған графта vi-дан vj-ға дейін жол болса, онда айтады, vj шыңына vi шыңынан қол жетімді деп. Екі шың vi және vj граф G-да байланған деп аталады, егер онда осы шыңдар ақырғы болатын жол болса. Граф G байланысшы деп аталады, егер ондағы әрбір екі шың байланысқан болса.. Сур. 2.2-де қарапайым бағытталмаған байланысшы граф кескінделген.
байланысшы графты айтады. Орман – бұл циклсыз кезкелген граф. Сур. 2.3 бес шыңды мүмкін ағаштар көрсетілген.
Сурет 2.2 - Бағытталмаған байланысшы граф мысалы
Сурет 2.3 - Ағаштар мысалы Келтірілген түсініктер мен анықтамаларды анализдеу араларында белгілі бір байланыстар, қатынастар бар қандай да бір обьектілер жүйесін қарастырғанда, жүйе құрылымын үйренуде, оның жұмыс істеу мүмкінділігінде графтарды модель ретінде қолдану ыңғайлылығын көрсетеді. Информатикада графтар операциондық жүйелер, алгоритмдеу, деректер құрылымы, ақпараттық модельдеу және т.б. бөлімдерде қолданылады. Графтардың әртүрлі мүмкін әдістерін қарастыра отырып, сәйкес ақпаратты компьютерге енгізу мұқтаждығын есте сақтау қажет. Осы жағдайда ақпаратты сандық түрде енгізу ең қолайлысы, дегенмен қазіргі техникалық құралдар графикалық ақпаратты да (кестелер, мәтіндер, графиктері суреттер) енгізуді мүмкіндейді, содан соң мұндай ақпараттарды өңдеу жүргізіледі. Шектес матрицасы. Егер граф G шыңдары vl, vl, ..., vn, таңбаларымен белгіленген болса, онда V х V өлшемдегі A(G) шектес матрицасының элементтері келесі түрде анықталады: A(i,J) = 1, егер vj-мен шектес болса; A(iJ) = 0 қарама-қарсы жағдайда (сур. 2.4, а). Қақтығыс матрицасы. Егер граф G шыңдары vl, vl, ..., vn, таңбаларымен белгіленген болса, ал қабырғалары - e1, e2, ..., en таңбаларымен, онда М х N өлшемдегі 1(G қақтығыс матрицасының элементтері B(I,J) = 1 ережесімен анықталады, егер vi қақтығысты ej; B(iJ) = 0, қарсы жағдайда (сур. 2.4, б . қараңыз). A(G):
1 2
1
0
1
0
1
Сур. 2.4, а. Шектес матрицасы I (G):
b
g
I
1
0
0
0
Сур. 2.4, б . Қақтығыс матрицасы
// - ді шыңдары бар бағытталған граф G үшін, N х N, өлшемдегі C(G) қол жетерлік матрицасының элементтері былай анықталады: С(1, /) = 1, егер vj шыңына vi-дан қол жетерлік болса; С(1, /) = 0 қарсы жағдайда. Төменде бағытталған граф және оның қол жетерлік матрицасының мысалы келтірілген, сур. 2.6
0 1 1 1 1 2
0 0 1 0 0 3
0 0 0 0 0 4
0 0 0 0 1 5
0 0 0 0 0
Сур. 2.6 Бағытталған граф және оның матрицасы
1.Көпше анықтамасын беріңіз? 2. Көпше қандай болады? 3.Көпшелердің қандай түрлерін білесіз? 4. Логиканы негіздеуші кім? 5.Ақиқаттық кестесі деген не? 6.Логиканың негізгі заңдарын атаңыз? 7.Граф деген не? 8.Ағаш деген не ?
1.Функциялар, қатынастар және көпшелер. 2. Логика негіздері. 3. Ақиқаттық кестелері 4. Логиканың негізгі заңдары 5.Бағытталмаған және бағытталған графтар. 6.Ағаштар. 7. Графтарды айналып өту стратегиясы.
1. Дискреттік математика негіздері. 2. Функциялар, қатынастар және көпшелер. 3. Логика негіздері 4. Ақиқаттық кестелері. 5. Логиканың негізгі заңдары 6. Бағытталмаған және бағытталған графтар. 7. Ағаштар . 8. Графтарды айналып өту стратегиясы.
3-бөлім. ЭЕМ архитектурасының негізгі түсініктері (2 сағат) 1-тақырып – Архитектура тарихы және жалпы шолу Жоспар:
Архитектура тарихы Архитектура түсінігі және ЭЕМ архитектурасының негізгі түрлері Компьютер жадында деректерді ұсыну.
Жоспар:
ЭЕМ-ді ұйымдастыру. Фон Нейман принциптері. ЭЕМ командалар жүйесі және оларға қатынасу әдістері Компьютер жадының құрылысы Енгізу-шығару құрылғысы
Компьютер – ол деректерді құруды, сақтауды және тасымалдауды автоматтандыруға арналған электрондық құрал. «Архитектура» сөзін ЭЕМ үшін қолданғанда, ол пайдаланушыға қажет компьютер сипаттамаларының жиынтығы деп түсінуге болады. Олар – ЭЕМ- нің негізгі құрылғылары мен блоктары және олардың арасындағы байланыстар құрылымы.
ЭЕМ құрудың жалпы принциптері: 1.
ЭЕМ жадының құрылысы, 2.
жадыға және сыртқы құрылғыларға жету жолы, 3.
компьютер конфигурациясын өзгерту мүмкіндігі, 4.
командалар жүйесі, 5.
деректер форматы, 6.
интерфейсті ұйымдастыру. Сонымен архитектура – ол ЭЕМ жұмысын бағдарламалық басқаруды және оның негізгі функционалды түйіндерінің бір-бірімен келіскен әрекетін іске асыратын ЭЕМ құрудың жалпы принципі. 60-ж. ортасынан бастап есептеуіш машиналарды жасау үшін, аппараттарды және
математикалық қамтамасыздандырудың кейбір құралдарын тәуелсіз құрастырудың орнына, аппараттық (hardware) және бағдарламалық (software) құралдардан тұратын жүйе жобалана бастады. Мұнда алдыңғы жоспарға олардың өзара әрекеттестік концепциясы қойылды. Осылай жаңа түсінік – ЭЕМ архитектурасы – пайда болды.
Фон Нейман принциптерінің негізіндегі ЭЕМ архитектурасы RAM
ROM
ЭЕМ архитектурасы деп сәйкес есептер класстарын шығару үшін, ЭЕМ- нің функционалдық мүмкіндіктерін анықтайтын, аппаратты-бағдарламалық құралдар мен
олардың сипаттамаларын ұйымдастырудың жалпы
принциптерінің жиынтығын айтады. ЭЕМ архитектурасы апараттық және бағдарламалық құралдар комплексін құру және көптеген факторларға көңіл қоюмен байланысты кең шеңбердегі проблемаларды қамтиды. Осы факторлар ішінде маңыздылары: бағасы, қолдану саласы, функционалдық мүмкіндіктері, пайдалануға ыңғайлылығы, ал архитектураның ең басты компоненттерінің бірі аппараттық құралдар болып табылады. ЭЕМ архитектурасының компоненттерін келесі суреттегі үлгідей көрсетуге болады. ОЗУ ОЗУ
ПЗУ ВЗУ
(ЖСҚ) (ТСҚ)
(ССҚ) Жүйелік шина Енгізу құрылғысы Шығару құрылғысы процессор АЛҚ
РОН БҚ
КЭШ Клавиатура дисплей
|