Ж. Жөғары және дискреттік математика Тақырыбы: Графтар мен желілерді қолдану

Желілер кең практикалық қолданысты алды, себебі олар табиғи және бейнелеудің ыңғайлы тәсілі және одан әрі әртүрлі күрделі жүйелерді талдау болып табылады. Желелік бейнені бірінші қолданудың бірі АҚШ әскери-теңіз флотының атомды су асты қайықтарын жарақтау үшін «Пларис» баллистикалық ракеталарды пмерикандық ғалымдар жасады. Осы ұлы жобаны іске асыруға 48 штаттан 600 фирма қатысқан. Желілік графтың өзі 10 000 оқиғаны қатысты. Жоспарлау және басқару жүйесінің негізінде АҚШ-тағы «Перт» жүйесі жатады, ал біздің елемізде – «СПУ», кең және табысты қолданылатын графтар, себебі оларды ЭЕМ-де оқиғаның үлкен санымен өңдеуге мүмкіндік берді.

Граф-ағаштар көмегімен жоспарлау есептерін шешеді (мақсаттар ағашы, нұсқаларды артық алу ағашы). Графтарды күрделі жүйелердіің иерархиялық құрылымдарын салу кезінде білімнің әртүрлі саласындағы жіктеулер иллюстрациясы үшін қолданылады.

Мысалды қараймыз. Кейбір объектінің жіктелімі үшін кәсіпорын. (оның атауын таңдаймыз — ------------------------= ---------- ) объектінің өзін оқулық ағаштың тамыры ретінде таңдаймыз (2.23-сурет). Осы объектілердіғ тұратын жиынтық графтың бірінші деңгейінде (жікқабатта) оорналастырамыз: г зауыт цехтары„ / ч , бұл — 1 -------------------------- -— болады. Графтың екінші деңгейі (жікқабат) кітап бөлімдері

Себебі иерархиялық құрылымдар бағынысты қатынастарды (кіші жиындар) білдіреді, онда оларды графикалық не граф-ағаш түрінде не Эйлер шеңберінің көмегімен бейнелеуге болады (2.24-сурет).

Осындай түрдегі құрылым, мысалы, кәсіпорын (оның құырылымды бөлігі: цехтар, бригадалар, учаскелер және т.б.), оқу орындары (колледж, факультеттерден тұрады, өз кезегінде олар курстан, курстар – топтан тұрады). Осындай тәуелділіке армиялық құралымдар бағынысты (дивизия, полк, тальон, рота, взвод, бөлімше, жекелеген солдаттар) тұрады. Осыған ұқсас кез келген әкімшілік-аумақтық құрылым құрылған: республика, облыс, аудан, елді мекендер. Осы ағаштың жолы бойынша ақпараттың ағындар жүріп өтеді: жоғарыдан тӛмен - өкім, басшылық нұсқаулар, төменнен жоғары – жұмыс туралы есеп, жедел ақпарат. Себебі жаырақтан тамырға жол жалғыз, онда оны жүйлердің жиынтығын тану үшін қолдануға болады. Мысалы, пошталық мекенжай «шежіреге жол» білдіреді, осыған ұқсас әкімшілік-аумақтық. «Кімге» бөлімінде ел, республикасы, облысы, ауданы, елді мекені, көшесі, үй, пәтер көрсетіледі. Осыған ұқсас объектілер кез келген ғылымда жктелеі. Алынатын сынгыптама иерархиялық құрылымның мысалы болып табылады. Мысалы, биологияда: сынып, жасақ, тұқымдастар, тегі, түрі. Тиісті граф әртүрлі деңгейлердің элементтерін қамтиды, тамыр – сыып, ал жапырақ – жануарлардың жекелеген түрі.

Кейбір уақытта объектілер арасындағы байланыс ағаш емес, оларды граф ретінде де білдіруге болады. Бұл мысалы, бір ғана еме, бірнеше тәуелсіз қызметтерге бағыну болады (өзара қосымша бағыну). Информатикада иерархиялық құрылымдар деректер базаларын, есептеу желілерін, байланыс желілерін, ұйымдастырушылық жүйелерді сипаттау кезінде қолданылады. Графтың көмегімен графикалық шежірені бейнелеуге болады (генеалогиялық шежіре).

Граф Лев Николаевич Толстойдың генеалогиялық шежіресі 2.25-суретте бенеленген түрі. Бинарлық іздеу. Бинарлық ағаштар информатикада операцияның қолданбалы ғылымдарының бірі – іздеуде қолданылады. Оған, кейбір реттелген массивте (жиында) белгілі бір ақпаратты табу қажет болғанда жүгінеді. Мысалы, телефон анықтамалығында – қандайжда бір абоненттің нөірі, сөздікте – белгілі бір сөз, файлда – кейбір кәсіпорынның қызметкерлерінің жалақысы туралы мәлімет, жекелеген қызметкердің жалақысы туралы мәлімет және т.б. Бірізді немесе желілік іздеу қызғышулық білдіретін ақпаратты анықтаудың жалпы және қарапайым әдісі болып табылады: жиынның әрбір элементі берілген шарттардың сәйкестігіне тексеріледі. Егер жиын реттелмесе, онда осындай процесс кездейсоқ сипақта ие болады. Егер жиын алдын ала реттелген болса, (телефон анықтамасында тектері, сөздіктегі өздер әліпби бойынша бөлінген, кәсіпорынның қызметкерлерін ақпараттағы, жалақы туралы табельді нӛмірлер бойынша бөлу), онда басқаны қолдану оңай, біршама тиімді әдіс – бинарлық іздеу.

Бинарлық іздеу жартылай бөлу әдісіне негізделген. Іздеу жиынның ортасынан басталады. Егер бірінші элемент шартты қанағаттандырса, онда іздеу процесі аяқталды, егер қанағаттандырмаса, онда процесс кез келген жартысынан жалғасады. Егер қалаулы элемент табылмаса, онда берілген шарттардың табылған элементіне сәйкестігі табылғанға дейін екінші жартысы талданады. Бинарлы ағаштар екіден баламалы бірін таңдау жасалғанда қажет.

Кейбір тізімде барлық андардың телнұсқаларын табу қажет болсын. Әрбір санды алдағы болған «болды – болған жоқ» деген мәнмен салыстыруды қолдануға болады. Бірақ онда салыстырудың үлкен қажет болады. Бинарлық ағаштарды қолдану (БА) салыстыру рәсімін қысқартады. Жаңа сан есептеледі және торапқа орналастырылады – жаңа БА болашақ түбіріне. Егер осы мәндер сәйкес келсе, онда телнұсқа табылады, егер сан түбірден аз болса, онда процесс оң жақ кіші ағашта жалғасады, егер кӛп болса – сол кіші ағашта жалғасады.

Графтар мен ағаштардың әртүрлі түрі оқу процесінде кең қолданады. Сондықтан, олар туралы бастапқы мәлімет әртүрлі салада табысты оқу үшін қажет, себебі олардың көегімен жиі оқу ақпараты беріледі. Мысалы, ЭЕМ-нің негізгі сыныптары граф түрінде бейнелеуге болады (2.2-сурет, б).

Граф-ағашты қолдана отырып, бинарлық іздеу рәсімінде деректер базасымен ЭЕМ жұмысы негізделген. База туралы ақпарат бірнеше тәсілмен, оның матрицалы тәсілмен ұсынылуы мүмкін. Релациялық базалар деп аталатындар кесте түрінде әртүрлі ақпаратты сақтайды, дегенмен, жолдар мен бағандардың тәртібі деректерді енгізген кезде беріледі. Базаларда ақпаратпен, оны ұйымдастырумен және жаңартумен ұзақ жұмыс болуы мүмкін. Деректерді автоматты іздеу көмегімен белгілі бір сипатты белгілері бойынша сұра усалу негізіне іріктелген.