УМКД

Мәліметтерді сұрыптауда

Қазақстан Республикасы білім және ғылым министрлігі
Семей қаласының Шәкәрім атындағы мемлекеттік университеті

3 деңгейдегі СМК құжаты

ПОӘК

ПОӘК
042.39.1.ХХ/01-2013

ПОӘК
<<Мәліметтерді өңдеудің құрылымдары мен алгоритмдері>> пәні бойынша оқу - әдістемелік материалдар
__.__.20__ж
№__ басылым

<<Мәліметтерді өңдеудің құрылымдары мен алгоритмдері>>
пәнін оқыту-әдістемелік кешен

5В011100 - <<Информатика>> мамандығына арналған

оқу - әдістемелік материалдар

Семей
2013

МАЗМҰНЫ

*
Глоссарий

*
Дәрістер

*
Зертханалық сабақтар

*
Студенттердің өздік жұмыстарының жоспары

1. Глоссарий

Мәліметтер дегеніміз - дербес компьютерде өңдеуге болатын, кез келген ақпаратты сипаттайтын мәнді немесе мәндер жиыны.
Мәліметтердің логикалық құрылымы дегеніміз - сәйес құрылымның моделі, берілу схемасы (екі өлшемді массив, тік бұрышты матрица).
Мәліметтердің физикалық құрылымы дегеніміз - құрылымды компьютер жадысына орналастыру немесе сақтау схемасы (жады ұяшықтарының тізбегі).
Динамикалық құрылым мәліметтері дегеніміз - ішкі жасалуы қандай да бір заң бойынша қалыптасқан, бірақ элементтер саны олардың өзара орналасуы, өзара байланысы программаның орындалу барысында динамикалық түрде өзгере алатын мәліметтер.
Сызықтық құрылым мәліметтер типтері - орналасуы бойынша реттелген элементтер тізімін анықтайды.
Сызықтық емес құрылым мәліметтер типтері - позициялық реттеусіз элементтерді анықтайды.
Тікелей кіру дегеніміз - элементті тікелей таңдау және тізімдегі алдыңғы элементтерге байланыссыз таңдауды айтады.
Массив дегеніміз - мәліметтердің бүтін санды индекс көмегімен кіруге болатын бір ғана типтен тұратын құрылымы.
Реттелген сызықтық тізімде - мәліметтер бір-біріне қатысты реттеліп орналасады.
Стек дегеніміз - элементтері тізімнің төбесі деп аталатын бір жағынан ғана қосылатын немесе өшірілетін сызықтық тізімді айтамыз (соңғысы келсе біріншісі кетеді).
Шірет (очередь) дегеніміз - тізімнің басынан немесе аяғынан ғана кіруге болатын сызықтық тізім. Элементтер тізімнің соңына қойылады да басынан өшіріледі.
Очередь приоритеті дегеніміз - очередь немесе шірет типті тізім, тізімдегі объектіні өшірген кезде ең жоғары приоритетке ие объект анықталады.
Файл дегеніміз - байттар тізімі. Ол бір ағымға теңеледі, яғни, бір құрылғыдан екінші құрылғыға ауысып отыратын байттар тізбегі. Тек қана дисктік файлға тікелей кіруді жүзеге асыруға болады.
Иррархиялық құрылым - бұл деңгейлері бойынша бөлінетін элементтер жиынындағы, яғни, бір деңгейдегі элемендеңгейде бірнеше ұрпағы болуы мүмкін.
Тармақ (дерево) - бұл түпкі немесе тамыр деп аталатын бір ғана көзден тарайтын элементтері бар мәліметтер құрылымы.
Пирамида дегеніміз - тармақтың ерекше түрі. Мұнда ең үлкен элемент үнемі түпкі деңгейде тұрады.
Топ (группа) дегеніміз - элементтері ешқандай реттеусіз орналасқан сызықтық емес құрылым.
Жиын дегеніміз - мәліметтер реттеусіз болғанда және мәліметтердің әрбір элементі өз алдына қайталанбайтын болғанда қолданылатын мәліметтер құрылымы.
Граф дегеніміз - төбелер жиынынан және сол төбелерді қосатын байланыстар жиынынан тұратын мәліметтер құрылымы.
Желі (сеть) дегеніміз - графтың ерекше формасы. Мұнда әрбір байланыстың өз салмағы болады.

2. Дәрістер
Дәріс 1.
Кіріспе, мәліметтер типтері
Мақсаты: Мәліметтердің өңдеудің құрылымдары мен алгоритмдеріне кіріспе. Негізгі ұғымдары. Мәліметтер типтерімен танысу. Кіру әдістері.
Соңғы 20-30 жылда құрылымдалған программалау идеялардың кең таралуы программалаудың теориясы мен практикасына үлкен әсер етіп, сәйкес алгоримдер мен программаларды жасаудағы мәліметтердің типі мен құрлымдарының ролі қайта қарауға алып келді. Осыған байланысты соңғы он жылдықта электронды есептеуіш машиналарды (ЭЕМ) программалық қамтамасыз ету саласында мамандар даярлайтын оқу орындарында мәліметтердің типтері мен құрылымдары пәні пайда болды. Бұл пән ақпараттық технологиялар саласында соған сәйкес программалық қамтамасыз етуге жоғары сапалы мамандар даярлауға мүмкіндік беретін компьютер ғылымы информатиканың фундаментальды (негізгі, түпкі) бөлімі болып саналады. Бұл курстың идеялық мазмұны программалық тілге тәуеді емес, бірақ мәліметтер құрылымын көрнекі түрде белгілеуге болатын Турбо Паскаль тілі қолданылады. Мәліметтер құрылымын кез келген программаның немесе программалық бөлімнің бөлінбес саласы болып саналады. Программаны жасауда нақтылы есепті сипаттайтын мәліметтер жиынын анықтап, есепті шешудің алгоритмін құру керек. Программаның мақсатына қарай мәліметтер әртүрлі күрделі деңгейде болуы мүмкін. Яғни жай типтерден бастап, жеткілікті типтегі күрделі құрылымдарға дейін.
Мәліметтер дегеніміз - дербес компьютерде өңдеуге болатын, кез келген ақпаратты сипаттайтын мәнді немесе мәндер жиыны. Мәліметтердің маңызды мінездемесін беретін тип болып саналады. Ол мәліметтерді компьютер жадысына беруде қолданылады және осы мәндерге орындауға болатын амалдар жиыны мен мәліметтер мәндері жиынын анықтайды. Мәліметтерді ұйымдастырудың логикалық және математикалық моделі Мәліметтер құрылымы деп аталады. Мәліметтердің логикалық құрылымы және физикалық құрылымы ұғымы бар.
Мәліметтердің логикалық құрылымы дегеніміз - сәйес құрылымның моделі, берілу схемасы (екі өлшемді массив, тік бұрышты матрица). Мұнда әрбір элементте индекс болады.
Мәліметтердің физикалық құрылымы дегеніміз - құрылымды компьютер жадысына орналастыру немесе сақтау схемасы (жады ұяшықтарының тізбегі).
Мәліметтердің барлық жиынын екіге бөлуге болады: Статикалық және динамикалық құрылым мәліметтері.
Статикалық құрылым мәліметтері - жай және күрделі болуы мүмкін. Олар қандай да бір заңдылық бойынша жай құрылымдарда қалыптасады. Құрылым элементтерінің өзара орналасуы мен өзара байланысы әрқашан тұрақты болып қалады.
Динамикалық құрылым мәліметтері дегеніміз - ішкі жасалуы қандай да бір заң бойынша қалыптасқан, бірақ элементтер саны олардың өзара орналасуы, өзара байланысы программаның орындалу барысында динамикалық түрде өзгере алатын мәліметтер.

Стандартты типтер мәліметтері
файлдар
Байланыспаған динамикалық құрылым
Байланысқан дин. құрылым
Сызықтық
Мәліметтер
Статикалық құрылым мәліметтері
Динамикалық құрылым мәліметтері
Программалаушы.анықтайтынмәлімет
массив
құрылым
бірігу
айналмалы
Тармақталған құрылым

Мәліметтердің типтерін сызықтық құрылымды мәліметтер типтері және сызықтық емес мәліметтер типтері деп бөлуге болады.
Сызықтық құрылым мәліметтер типтері - орналасуы бойынша реттелген элементтер тізімін анықтайды.
Сызықтық емес құрылым мәліметтер типтері - позициялық реттеусіз элементтерді анықтайды.
Тікелей кіру дегеніміз - элементті тікелей таңдау және тізімдегі алдыңғы элементтерге байланыссыз таңдауды айтады.

Индукциялық кіру
Тізбектей кіру
Топтаса кіру
жиын
Мәліметтер типтері
Сызықтық құрылым мәліметтер типт.
Сызықтық емес құрылым мәлім.тип.
Тікелей кіру
массив
құрылым
файл
графиктік
Сөздік
FLASH таблица
Тізім
Стек
шірет
тармақталған
пирамида

Массив дегеніміз - мәліметтердің бүтін санды индекс көмегімен кіруге болатын бір ғана типтен тұратын құрылымы.
А[0], А[1], А[2], ..., А[n]
Массивтермен жұмыс жасауда элементтерге кіруді ұйымдастыру маңызды әрекет болып саналады.
Элементке логикалық деңгейде кіру үшін - массив аты мен элемент индексі керек. Ал физикалық деңгейде жұмыс жасауда элемент адресін массив атымен ізделіп отырған элемент индексі мен оның ұзындығына қарай есептеп шығару қажет болады.
Индексті кіру мәліметтері типтері үшін - жазуға кіруге қолданылатын қандай да бір кілт байланыстырады.
FLASH кесте - кілтпен байланысты мәліметтерді сақтайды. Кілт - мәліметтерді табу үшін қолданылатын бүтін санды индекске трансформацияланады. Кілт бүтін болуы мүмкін емес.
Сөздік деп аталатын мәліметтер құрылымы ассоциация деп аталатын кілт және мән жұптарының жиынынан тұрады. Мысалға, кілт сөз болуы мүмкін, ал мән сөздің анықтамасын көрсететін сөйлем болуы мүмкін.
Сызықтық құрылым мәліметтер типтері - мәліметтерге тізбектей кіруді пайдаланғанда мәліметтердің динамикалық құрылымы болып табылады да, келесі қасиеттерге ие болады:
* өлшемнің тұрақсыздығы ;
* жадыдағы элементтер құрылымдарының физикалық реттілігінің жоқтығы.
Сызықтық тізім - элементтердің кез келген санына ие болады, тізімнің өлшемі тізімдегі элементтерді қосуға және алып тастауға байланысты өзгеріп отырады. Бірінші элементі басында орналасады, соңғы элементі аяғында орналасады және әрбір елемент (соңғысынан басқа) алдында бір элементке ие болады.
Реттелген сызықтық тізімде - мәліметтер бір-біріне қатысты реттеліп орналасады. Стек дегеніміз - элементтері тізімнің төбесі деп аталатын бір жағынан ғана қосылатын немесе өшірілетін сызықтық тізімді айтамыз (соңғысы келсе біріншісі кетеді).
Шірет (очередь) дегеніміз - тізімнің басынан немесе аяғынан ғана кіруге болатын сызықтық тізім. Элементтер тізімнің соңына қойылады да басынан өшіріледі.
Очередь приоритеті дегеніміз - очередь немесе шірет типті тізім, тізімдегі объектіні өшірген кезде ең жоғары приоритетке ие объект анықталады.
Файл дегеніміз - байттар тізімі. Ол бір ағымға теңеледі, яғни, бір құрылғыдан екінші құрылғыға ауысып отыратын байттар тізбегі. Тек қана дисктік файлға тікелей кіруді жүзеге асыруға болады.
Иррархиялық құрылым - бұл деңгейлері бойынша бөлінетін элементтер жиынындағы, яғни, бір деңгейдегі элемендеңгейде бірнеше ұрпағы болуы мүмкін.
Тармақ (дерево) - бұл түпкі немесе тамыр деп аталатын бір ғана көзден тарайтын элементтері бар мәліметтер құрылымы.
Пирамида дегеніміз - тармақтың ерекше түрі. Мұнда ең үлкен элемент үнемі түпкі деңгейде тұрады.
Топ (группа) дегеніміз - элементтері ешқандай реттеусіз орналасқан сызықтық емес құрылым.
Жиын дегеніміз - мәліметтер реттеусіз болғанда және мәліметтердің әрбір элементі өз алдына қайталанбайтын болғанда қолданылатын мәліметтер құрылымы.
Граф дегеніміз - төбелер жиынынан және сол төбелерді қосатын байланыстар жиынынан тұратын мәліметтер құрылымы.
Желі (сеть) дегеніміз - графтың ерекше формасы. Мұнда әрбір байланыстың өз салмағы болады.

Дәріс 2.
Мәліметтер құрылымдарымен жасалатын әрекеттер
Мақсаты: Мәліметтер құрылымдарымен жасалатын әрететтермен танысу. Алгоритмдер анализі және программаларды орындау уақыты ұғымдары.

Құрылымдағы мәліметтер қандай да бір әрекеттер көмегімен өңделеді. Мәліметтер құрылымдарын таңдау осы әрекеттер орындайтын жиілікке тәуелді болады. Мәліметтерді өңдеуде келесі әрекеттер маңызды рольге ие болады:
* Құрылымды тексеру. Яғни құрылымның әрбір элементін оны кейін өңдеуге болатындай мақсатта кіру мүмкіндігі.
* Іздеу. Яғни берілген мәні бар элементтердің орнын табу.
* Қыстырып қою. Яғни құрылымға жаңа элементтер кіргізу.
* Өшіру . Құрылымдағы элементті алып тастау.

Алгоритмдер анализі және программаларды
орындау уақыты

Бір есепті шешуге арналған әртүрлі алгоритмдерді салыстыру үшін программаның орындалу уақытын жуық мөлшерде анықтау үшін алгоритмдердің математикалық анализі қолданылады. Қолданбалы есептерді шешу процесінде есеп шығарудың неғұрлым жақын алгоритмін таңдау керек болады. Мұнда алгоритм келесі талаптарды қанағаттандыруы керек:
* Түсінуге жеңіл, программалық кодқа және орындауға, аударуға жеңіл болуға тиіс.
* Компьютер ресурстарын тиімді пайдалану және орындалу жылдамдығы неғұрлым тез болуы керек.
Программаның орындалу уақытына келесі факторлар әсер етеді:
* Алғашқы ақпаратты программаға енгізу.
* Орындалып жатқан программаның компилияцияланған кодының сапасы.
* Программаның орындалуында пайдаланылып жатқан жатқан машиналық инструкциялар.
* Сәйкес программа алгоритмінің уақытша күрделілігі.

Алгоритмнің Уақыт бойынша күрделілігі дегеніміз - жоспарланған нәтижеге жету үшін алгоритмге орындау қажет болатын қадамдармен өлшенетін алгоритмнің орындалу уақыты. Бұл терминнің синонимі ретінде, көбінесе алгоритмнің орындау уақыты сөзі пайдаланылады.
Программаның орындалу уақыты алғашқы мәліметтердің мөлшеріне тәуелді. Мысалға, массивтегі ең кіші элементті табу бұл мәліметтер элементтерін салыстыруға негізгі операция немесе амал. N элементтерін массиві үшін алгоритмге N-1 салыстыру қажет болады және оның орындалу уақыты Т-ге пропорционал. Алгоритмдердің уақыт бойынша күрделілігін 0 символика деген қолданылады. Мысалы, егер қандай да бір программаның орындалу уақыты Т(n) О(n2) ретке ие болса, бұл дегеніміз қандай да бір С әлде n0 константалар болып, n0-дан үлкен немесе тең болатын n константалар үшін Т(n)<=cn теңсіздігі орындалады. Яғни, орындалу уақыты ең аз дәрежеде өсетін программаларды таңдап алуы керек. Бұл дегеніміз, неғұрлым өсу дәрежесі аз болса, компьютердің шығарып отырған есептің өлшемі соғұрлым көп болады деген сөз. Программаның орындалу уақытын теориялық түрде табу күрделі математикалық есеп, оның шешілу үшін бірнеше базалық принциптерді білу керек. Алдымен 3 маңызды ережелерді қарастырамыз:
- Тұрақты көбейткіштер уақыт бойынша күрделі реттік анықтау үшін маңызды емес, яғни О(k*f)=0.
- Көбейткіштер ережесі: екі функцияның уақыт бойнша күрделі реттің көбейткіштері олардың күрделіліктің О(f*g)=O(f)*O(g).
- Қосындылар ережесі: функцияның уақыт бойынша күрдел реттің қосындылары қосылғыштардың ең үлкенінің ретіне тең болады. О(n+n+n)=O(n).

Программалар анализінің ережелері:
* Меншіктеу, оқу және жазу операторларының орындалу уақыты О(1) ретке ие болады.
* Операторлар тізбегінің орындалу уақыты қосындылар ережесі бойынша анықталады.
* Шартты оператордың орындалу уақыты шартты түрде орындалып отырған оператордың орындалу уақытынан тұрады. Логикалық өрнекті есептеу уақыты - жалпы О(1) ретке ие болады. Барлық шарт конструкциясының уақыты логикалық өрнекті есептеу уақытынан және логикалық өрнек, ақиқаты және жалған мәндерді қабылдауда жүзеге асатын операторларды орындауға қажет ең көп уақыттан тұрады.
* Циклдарды орындау уақыты - цикл денесі оператордың орындалу уақытынан және циклды тоқтату шартын есептеудің уақытынан тұратын барлық цикл итерацияларының уақытын қосқанға тең болады.

Сұрыптауға жататын элементтер саны кіретін мәліметтер көлемге өлшем бірлігі болып ткабылады. Мұндағы соңғы үш оператор О(1) орындалу ретіне ие болады. Қосындылар дәрежесіне сәйкес бұл операторлар топтары О(мах(1,1,1))=О(1).
Егер операторы үшін логикалық өрнекті тексеру О(1) уақыт ретіне тең болады. Соңғы 5 оператор тобының, яғни ішкі циклдің орындалу ретін қарастырамыз, бұл операторлар үшін әрбір итеракциядағы орындалу уақыты О(1)-ге ие болады. Цикл n-1 рет орындалады. Сондықтан, көбейткіш ережесі бойынша циклдің барлық орындалу уақыты: О((n-1)*1)=O(n*1).
Сыртқы циклді қарастырамыз: сыртқы цикл n-1 рет орындалады, сондықтан программаның жалпы қосынды орындалу уақыты формуламен анықталады және О(n2) ретке ие болады. Жалпы О функциясының мәні берілгендер құрылымы алгоритмдер үшін полиномдық, логорифмдік және экспоненциалдық функциялар ішінен таңдап алынады.

Дәріс 3.

Массивтерді сұрыптау алгоритмдері. Таңдау көмегімен сұрыптау. Ауыстыру арқылы сұрыптау.
Мақсаты: Массивтерді сұрыптау алгоритмдері ұғымдары, олардың түрлерімен танысу. Таңдау арқылы сұрыптау жүргізу. Ауыстыру арқылы сұрыптау әдісімен танысу.

Массивтерді сұрыптау алгоритмдері 4-ке бөлінеді:
* Таңдау арқылы сұрыптау.
* Ауыстыру арқылы сұрыптау (көпіршік әдіісі).
* Қою арқылы арқылы сұрыптау.
* Тез сұрыптау.

Сұрыптау немесе объектілер тізімін реттеу деп осы объектілердің қандай да бір сызықтық реттілікке қатысты өсуі мен кемуі бойынша орындауды айтамыз. Сұрыптаудың мәні сонда жазулар тізімінің реттілігін кілттік өріс мәндері кемімейтін тізбек құратындай етуіміз керек. Басқа сөзбен айтқанда R1, R2, .. , Rn жазулары кілттік мәндері K1, K2,...,Kn орналасуы керек. Ki1>. Егер салыстыру нәтижесінде сәйкестік бар болса, онда mid индексін кілтті табу үшін қолданамыз. Егер орталық элемент мәні кілттен кіші болса, онда қарастырылып отырған тізімнің оң жағындағы бөлігінде іздеу жүргіземіз. Егер керісінше үлкен болса, онда сол жақтағы бөлігінде іздеу жүргіземіз.
* Егер ізделіп отырған элемент тізімде жоқ болса, онда үзу индикаторын береміз.

Мысалға: Бүтін сандар тұратын А массиві берілсін. 33 кілті берілген элементі бар табу керек.
Мысал элементтері: А

0
1
2
3
4
5
6
7
8
-7
3
5
8
12
16
23
33
55

Low=0
High=8
mid=4
33>A(mid) 0 1 2 3 4 5 6 7 8
-7
3
5
8
12
16
23
33
55
mid

Low=5
High=8
mid=6
33>A(mid)

0 1 2 3 4 5 6 7 8
-7
3
5
8
12
16
23
33
55
mid
Low=7
High=8
mid=7
33=A(mid)

Сонда тізбектеліп іздеуде 8 салыстыру, ал бинарлық іздеуде 3 салыстыру жүргізіледі.

Дәріс 6.
Файлдар және сыртқы тасымалдаушылардағы мәліметтер мен операциялар.
Мақсаты: Файлдар және сыртқы тасымалдаушылардағы мәліметтер мен операциялар жүргізу ұғымын қалыптастыру. Балансталған көп жолдық бірігу, табиғи бірігу арқылы сұрыптау, сыртқы сұрыптау амалдарын түсіндіру.

Көптеген қосымшаларда дисктердегі файлдарда орналасқан мәліметтерге кіру қажет болады. Мәліметтердің ұлкен жиындары жадыға бір уақытта сыйғызуға мүмкін емес миллиондаған жазулардан тұруы мүмкін. Оларды басқару үшін сыртқы сұрыптау мен іздеу алгоритмдері қажет.
Аппаратты тұрғыдан алғанда файл жазулары дискте сақталатын, белгілі ұзындықтағы мәліметтер блоктарын құрайды. Логикалық тұрғыдан алғанда жазулар файлда тізбектеліп орналасады.
Файлдық жүйе жекелеген жазуларға, сондай-ақ, барлық файлға толығымен кіруді жүзеге асыруға мүмкіндік береді.
Сыртқы сұрыптау
Файлдар түрінде ұйымдастырылған мәліметтерді сұрыптау сыртқы сұрыптау деп аталады. Егер файл оперативті жадыда сыймайтындай үлкен болса, онда сұрыптау - өте үлкен проблема. Барлық мәліметтерді бір массивте сақтауға болмайтындықтан, оларды сақтау үшін уақытша файлдарды қолдану керек.
Тура біріктіру арқылы сұрыптау екі реттелген тізімді біріктіретін жай біріктіру әдісін қолданады. Басты идеясы біртіндеп үлкейетін элементтер түрінде файл ұйымдастырылатынында, яғни жазулар тізбегі r1<=r2<=...<=rn жазулар тізбегі. Мысалға, 3 деген ұзындықтағы сериялармен ұйымдастырылған бүтін сандар тізбегі:

7 15 29 7 11 13 16 22 31 5 12
Мұнда соңы 3 тен кем ұзындықта болуы мүмкін, бірақ оның жазулары да сұрыпталған.

Сұрыптау алгоритмі

FC 5,15,35,30,20,45,35,5,65,75,40,50,60,70,30,40,25,10,45,55

* Файлды екіге бөлеміз. Оның элементтерін сәйкесінше екіге бөлеміз. Осылайша, әрбір жаңа файлда элементтер тізімі пайда болады.
* Ішкі тізімдерді салыстырамыз. Яғни, FA файлынан және FB файлынан бір-бір элементтен таңдап алып, жай біріктіру алгоритмін пайдалана отырып, қайтадан FC файлына жазамыз. Осылайша, барлық элементе қайтадан FC файлға ауысқанша жалғастырамыз.

FА 5,35,20,35,65,40,60,30,25,45
FВ 15,30,45,5,75,50,70,40,10,55
FC 5,15,30,35,20,45,5,35,65,75,40,50,60,70,30,40,10,25,45,55

* Бір қадамды қайталап, FА және FВ файлдарына екі элементті серияларды жазып шығарамыз.
FА 5,15,20,45,65,75,60,70,10,25
FВ 30,35,5,35,40,50,30,40,45,55

* FА және FВ файлдарындағы екі элементті серияларды FC файлына 4 элементті серияға біріктіреміз. Мұнда реттелген тізімдерді біріктіру алгоритмін пайдаланамыз.
FC 5,15,30,35, 5,20,35,45
40 50 65 75 30 40 60 70 10 25 45 55

* FС файлын екіге бөлетін қадамды FА және FВ файлында сәйкесінше 4 8 т.с.с элементтер серияларын құрай отырып және сериялардың әрбір жұптарын біріктіре отырып қайталаймыз. Процесс FА және FВ файлдары бір-бір реттелген тізімнен тұрғанда және олар FC сұрыпталған файлына соңғы рет бірікенде аяқталады.
Түзу бірігу сұрыптау анализі.
Сұрыптау бір элементі ішкі тізімдердің жүрістер сериясынан тұрады, әрбір жүрісте ішкі тізімнің ұзындығы екі еселенеді. Ол үшін log2n жүріс қажет болады. Түзу бірігу арқылы сұрыптау 2n log2n мәліметтерді қарауды талап етеді, сондықтан оның күрделілік реті O(n log 2n).

Табиғи бірігу арқылы сұрыптау
Түзу бірігу арқылы сұрыптауда алғашқы ұзындығы бірге тең болатын реттелген сериялар пайдаланылады да, олар әрбір жүріс сайын екі еселеніп отырады. Ең аяғында сериялар файлдардың барлығын қамтиды да сұрыпталу аяқталады. Мұның бір кемшілігі қысқа сериялар мен жұмыста көп уақыт кетеді. Мұндай сұрыптауды салыстырмалы түрде ұзын сериялардан бастасақ, алгоритмнің тиімділігі неғұрлым артады. Әрбір ретте неғұрлым екі серия бірігетін сұрыпталу әдісі Табиғи бірігу деп аталады.
Сұрыптау алгоритмі
Алғашқыда FC алғашқы файлды және алғашқы ұзындықтағы реттелген серияларды жасау үшін оперативті жадыдағы буфер керек:
* Алғашқы файлдың мәліметтері буферге блок бойынша оқылады.
* Әрбір блок сұрыпталудың кез келген алгоритмі арқылы сұрыпталады да (мысалы, тез сұрыпталу), кезек-кезек FB және FA файлдарына көшіріліп отырады.
* FC файлы біткен кезде қайтадан уақытша FА және FВ файлындағы мәліметтер блоктары қайтадан біріге бастайды.
* Осылайша, сұрыптау жай бірігуге ұқсас жалғаса береді.
Алгоритм анализі:
Мұнда әрбір жүрістен сериялардың саны екі есе қысқарады. Сондықтан жіберулердің жалпы саны ең жаман жағдайда n log2n тең болады. Ал жалпы жағдайда одан да аз болады.

Балансталған көп жолдық бірігу
Тізбектелген сұрыпталуға кететін шығын жүрістің санына прорпорционал болады. Шығынды азайтудың бір жолы екі уақытша немесе одан да көп файлдарды пайдалану R сериялы бірігу n уақытша файлдарға бөлінгенде ішкі тізімдерден тұратын тізбек құрайды. Екінші жүріс бұл санды дейін қысқартады. Ал үшінші жүріс дейін қысқартады. Осылайша к жүрістен кейін бөлік қалады. n элементі N жүрісті бірігу мен сұрыптауда жүрістің жалпы саны k=logNn (N-жол, n-элементтер саны) тең болады. Әрбір жүрісте қайта жазудың n операциясы жүретін болғандықтан ең жаман жағдайда операцияның жалпы саны M=n logNn болады.

Дәріс 7.
Мәтіндерге тізбектеліп кіретін мәліметтердің сызықтық құрылымдық типтері.

Мақсаты: Мәтіндерге тізбектеліп кіретін мәліметтердің сызықтық құрылымдық типтері ұғымы. Байланған сызықтық тізімдер түсініктерін енгізу.

Байланған сызықтық тізімдер
Тізім дегеніміз - сандары өзгеруі мүмкін элементтердің жиынтығы. Ол шынжырдағы шығыршық іспеттес. Тізімнің ұзындығы жаңа шығыршықтар қосу арқылы көбеюі мүмкін. Жаңа элементтер тізімге тізімнің бір жерін үзіп, соған жаңа элемент қосып, қайтандан жалғау арқылы кіргізуі мүмкін. Элементтер тізіміне сол сияқты тізімді үзіп, бір шығыршықты алып қайта жалғап қойған сияқты алынып тасталады. Тізімдер үш түрлі болады:
1. Бір байланысты.
2. Циклық
3. Екі байланысты

* Бір байланысты сызықтық тізім.
Бір байланысты сызықтық тізім екі әдіспен жүзеге асуы мүмкін:
1-массивтер негізінде
2-көрсеткіштер көмегімен
Тізімді массив негізінде жүзеге асыруда тізім элементтері массивінің қатарлас ұяшықтарында орналасады. Бұлай берілуі тізімнің мазмұнын жеңіл қарап, оның аяғына жаңа элементтер қосуға мүмкіндік береді. Бірақ жаңа элементті тізімнің ортасына қосу қажет болғанда оған арнап кейінгі элементтердің барлығын массивтің аяғына қарай бір позиция жылжытып, бір орын ашу керек. Сол сияқты массив элементін алып тастау үшін де босаған ұяшықты жою үшін элементтің барлығын солға қарай жылжыту керек болады. Бірақ бұлай істеудің бірнеше кемшіліктері бар:
* Тізімді массив негізінде жүзеге асыру орындалмас бұрын тізімнің максималды өлшемін көрсетуді талап етеді.
* Массив негізіндегі тізімдерді жүзеге асыру компьютер жадысының үлкен көлемін қажет етеді. Тізімді жүзеге асыру үшін тізімнің ең үлкен мүмкін мөлшеріне жететіндей етіп жады көлемін бөлу қажет.
Көрсеткіштер көмегімен жүзеге асыру. Тізімді сақтау үшін жадының үзіліссіз аймағын пайдаланудан босатады. Сондықтан бұл жағдайда элементтерді қосқанда немесе өшіргенде элементтер ары-бері жылжытуды қажет етпейді. Алайда, бұл жағдайда көрсеткіштерді сақтайтын қосымша жады керек болады. Тізімнің әрбір бөлігі - мәліметтер өрісінен және тізімдегі келесі элементтерді көрсететін көрсеткіштен тұрады.
Байланған тізімнің құрылымы келесі түрде берілуі мүмкін:

head
ptr rear NULL
Dann1
Next

Dann2
Next

Dann N-1
next

dannN
next

Мұндағы тізбектегі соңғы элементтің көрсеткіш өрісі 0 деген мәнге ие болады. Тізімдә сипаттау үшін үш түрлі көрсеткіш пайдаланған. Тізбектің бірінші элементінің көрсеткіші - head. Тізбектің соңғы элементінің көрсеткіші - rear. Тізбектің ағымдағы элементінің көрсеткіші - ptr. Head деген көрсеткіші бар элементсіз тізім 0 деген мәнге ие болады, себебі тізбектің кез келген элементіне кіру үшін басынан бастап қарау қажет.

Тізімдермен жүргізілетін операциялар
Тізімді қалыптастыру. Бұл жағдайда тізімге элементті қосу аяғынан басталады немесе аяғында жүргізіледі.

* Байланған тізімнен өту.
* Тізімді тазалау.
* Элементті енгізу схемасы.

Реттелген тізімді жасау
Көптеген қосымшаларда мәліметтердің реттелген тізімін қолдану қажет болады. Оның элементтері өспелі немесе кемімелі ретте орналасқан болуы тиіс. Жаңа элементтің дұрыс орнын анықтау үшін қыстыып қою алгоритмі тізімді сканерлеп өтеді. Одан кейін барып қою жүзеге асады. Мысалы: 60,65,74,82 тізімі берілген.

60
65
74
82
1. head Null

осы тізімге 50,70,90 сандарын қою керек.

* 50 санын тізімге енгіземіз.
60
65
74
82
50
head Null

Тізімдегі бірінші элемент - 60. Оның мәні 50-ден үлкен, сондықтан жаңа элемент тізімнің басына қойылады.

* 70 санын тізімге енгізу керек. Мұнда 74 саны 70-тен үлкен тізімдегі бірінші элемент. Сондықтан қыстырып қою мына брйынша жүзеге асырылады:
head

60
65
74
82
50
70
Null

* 90 санын тізімге енгіземіз. Тағы барлық тізім тексеріледі. Онда элементтің ішінде мәні 90-нан кіші элемент жоқ. Сондықтан 90 тізімнің ең соңына қоыслады.

60
65
74
82
50
90
head Null Null

Дәріс 8.
Циклдық тізімдер. Стектер.
Мақсаты: Стектер ұғымы енгізу. Стектердің амалдарын, қолданылу аймақтарын беру.
Циклдық тізімдер ұғымын енгізу. Олармен жүргізілетін амалдармен танысу.

Осы уақытқа дейін біз тізімнің соңғы элементін көрсеткіш мәнін 0 деген сызықтық тізімді қарастырдық. Егер тізімнің соңғы элементінің көрсеткіш мәні тізімнің басының адресіне ауыстыратын болсақ, циклдық тізім аламыз. Көптеген кәсіби програмистер байланған тізімдерді жүзеге асыру үшін келесі циклдік модельді қолданады:
Dann1
next
Dann2
next
dannN
next
head

Циклдық тізімнің бір жетістігі бұл элементтерге кез келген жерде элементтерге кіруге болатындығында. Ал кемшілігі тізіммен жүрген кезде байқамаса ақырсыз циклге кіріп кетуге болады. Циклдық тізім сызықтық тізімге қарағанда құрылымы неғұрлым иілгіш болып келеді. Ол тізімде жүруді кез келген жағдайда бастауға мүмкіндік береді және оны бастапқы позицияға дейін жалғастыруға болады.

Екі байланысты сызықтық тізім
Кейбір есептерде тізім бойымен екі бағытты қозғалыс жасау керек болады. Бұл дегеніміз - тізімнің әрбір эелементіне бір өрістің орнына екі байланыс өрісін енгізгенде мүмкін болады. Бұл өрістерде жаңағы элемент алдыңғы және артқы элементтердің адрестері болады.
Сызықтық тізім екі байланысы бар немесе екі байланысты сызықтық тізім деп аталады. Егер бұл тізімнің әрбір элементі екі көрсеткішіне ие болса, яғни алдыңғы және артқы элементке арналған көрсеткіштер. Екі байланысты тізімді графиктік түрде былай көрсетуге болады.
null
val
next
prev
val
next
prev
vall
next
prev
null
vall
beg

2 байланысты тізімнен элементті алып тастау схемасы:
rex
prev
Val 1
next
prev
Vall 2
next
prev
next
Vall 3

Стектер

Стек дегеніміз ұзындық айнымалысының тізбектелген тізімі. Ондағы элементтерді алып тастау немесе қосу тек қана бір жағынан жүргізіледі. Стектерді кейде магазиндер деп те атайды. Стектерді белгілеу үшін көбінесе LIFO деген абревидуоа қолданылады. LIFO - Last in /first out (соңғы кіргенде бірінші шығады). Стектер тізімнің төбесінде кіруге болатын элементтерді сақтау үшін қолданылады. Стектің құрылымы полкадағы (сөредегі) кітаптар жиынына ұқсас болады. Мысалға: мұнда ең жоғарғы затты алуға болады немесе жаңа затты ең үстіне қосуға болады. Стек құрылымында элементтерді қосу және алып тастау операциялары маңызды орын алады.
В
В
А
А
С
А
В
А
А
Д
А
Push операциясы стектің төбесіне немесе ең жоғарғы жағына элемент қосады. Ал Pop операциясы элементті өшіреді. Сонда мына құрылымдарды сызамыз:

pushA pushB pushC Pop Pop PopD

Стектер екі әдіспен жүзеге асуы мүмкін:
* массив негізінде
* көрсеткіштер көмегімен

Стекті бір өлшемді массив негізінде жүзеге асыруды - стек өлшемі массивті максимальды элементтер санымен шектестіреді. Ал стекті көрсетулер көмегімен жүзеге асыруды - стек мөлшері - бос жадының кіруге болатын көмегімен шектеледі.
Стек құрылымын келесі графиктік түрде беруге болады:
Стек төбесі
N мәлімет
Көрсеткіш
n-1 мәлімет
Көрсеткіш
Көрсеткіш
2 мәлімет
Көрсеткіш
1 мәлімет

Стек операциялары
* Элементті стекке қосу.
* Элементті стектен өшіру (өшіріліп отырған элементтің мәнін берумен бірге)
* Жоғарғы элементтің мәнін беру.
* Стекті тазалау.
* Стек элементтің санын басып шығару.

Стектер қолданылады:
* Жадымен жұмыста. Мысалға, printf және scanf функциялары жұмысы стекті пайдалануға негізделген.
* Сөйлем поендром болатындығын немесе болмайтындығын анықтау үшін қолданылады. Полендром дегеніміз - түзу және кері бағытта бірдей оқылатын жол. Мысалға, 121, ара.
* Әртүрлі негіздегі мәліметтерді шығару үшін.
* Электронды калькуляторлар жасауда.

Дәріс 9.
Шіреттер (Очереди)
Мақсаты: Шіреттер ұғымын, шіреттердің қолданылу аймақтары, операциялары жайлы түсініктер қалыптастыру.

Шірет дегеніміз - ұзындық айнымалысының тізбектелген тізімі. Мұнда элементтерді қосу тізімнің бір жағынан жүргізіледі, ал элементтерді алып тастау келесі басынан жүргізіледі. Шіреттің принципі мынадай: FIFO - first in /first out. Бұл да аббревиатура.
Аббревиатура қысқарған сөздердің бас әрпін алып жазатын қысқарған сөздер. FIFO - соңынан кіру, басынан шығару. Мысалға, шіреттегі коиенттерге қызмет көрсетуді алуға болады. Шіреттермен жұмыс істегенде бастапқы және срңғы позицияларға арнайы көрсетулер қолданылады. Бұл көрсетулер шіретке элемент қосқанда және шіреттен элементті өшіргенде қолданылады. Шіреттің басы шіреттегі бірінші элементпен анықталады. (front) - алғашқы. Ал шіреттің соңы шіреттегі соңғы элементтен кейінгі орын (rear - соңғы).
Шіреттерде екі әдіспен жүзеге асады:
1. массивтер негізінде
2. көрсеткіштер көмегімен.
Шіреттер де стектер сияқты элементтің саны шектелмейді. Алайда, егер стекті жүзеге асыру үшін массив қолданса, онда толық шірет шарты пайда болуы мүмкін. Шіретті массивтер негізінде екі әдіспен жүзеге асыруға болады:
1. Сызықтық шірет (линейная)
2. Сақиналық шірет (кольцевая)
Жай ғана сызықтық шірет бір өлшемді массив негізінде жасалады. Шіреттегі бір элементті алып тастағанда қалған элементтің барлығы 1 позицияға алға жылжиды.
Элементті қосу:
А, В, С
А
В
С

С
front rear

Элементті өшіру
В
С

front rear

В элементін өшіру

front rear

С
D
E
F
DEF элементін қосу

front rear
Осындай модельмен жүргізіледі. Бұл модель тиімді емес. Мысалға, шіретте 1000 элемент болсын. Егер басынан 1 элемент өшірілсе (кетсе) онда 999 элемент солға қарай жылжуы керек. Мұндай жағдайда сақиналық шірет тиімді. Сақиналық шіреттің элементтері логикалық түрде шеңберге ұйымдастырылады (сақиналық). Front айнымалысы шіреттегі бір элементтің орыны болып табылады және ол өшірулерді орындаған сайын шеңбер бойымен оңға қарай жылжиды. Массив негізінде:

С В

С В
2. rear 1. rear front

front

A-ны өшіру
D E

С В
D

С В
rear

front front
rear
D-ны қосу Е-ні қосу

Шіреттерді көрсеткіштер көмегімен жүзеге асыруда шірет өлшемі кіруге болатын бос жадының көлемімен шектеледі. Оны графикпен келесі түрде беруге болады:

next
Val n
next
Val n-1
next
Val 2
next
Val 1
Front

Null

Шірет объектісімен жүргізілетін операциялар

oo Шіретке элементті қосу
oo Шіреттен элементті алып тастау (өшірілген элементтің мәнін беру)
oo Бірінші элементтің мәнін беру.
oo Шіретті тазалау
oo Шірет элементінің санын беру.
Шіреттер қолданылады:
- Компьютерлік модельдеуде (банктегі клиент шіретін модельдеу)
- Көп адамдар қолданылатын операциялық жүйелерде.
- Мәліметтерді сұрыптауда

Приоритеттер шіреті
Приоритеттер шіреті дегеніміз - бұл тзімнен жоғары приоритетті элемент өшірілетін шіреттің модификацияланған версиясы.
Шіреттегі элементтер кілт және мән жұбы ретінде қарастырылады. Мұнда кілт приоритеттің деңгейін көрсетеді. Приоритет қандай да бір сыртқы критерий бойынша бағаланады. Приоритет шіретіндегі элементті өшіруде приоритеті бірдей элемент қатар келсе, алдымен бірінші түскен элемент өшіріледі. 0 приоритеті жоғары болып саналады. Келесі элементтер тізімін және приоритетін қарастырсақ сақталу реті

Элемент 1
20
Элемент 2
0
Элемент 3
40
Элемент 4
30
Элемент5
20

Ең алдымен 2 өшіріледі.
2,1,5,4,3
орындалу реті

Элемент 1
20
Элемент 2
0
Элемент 3
40
Элемент 4
30
Элемент5
20

2,1,5,4,3

Элемент 1
0
Элемент 2
20
Элемент 3
20
Элемент 4
30
Элемент5
40

Пиоритеттер шіретін әрбір шіреттер приоритеті үшін қолданылатын бірнеше шіреттер түрінде беруге болады. Приоритеттер шіретін процестеп, тізімге жазатын және одан кейін приоритеттер реті бойынша орындайтын операциялық жүйеде қолдануға болады.
Дәріс 10.
Ағаштар. Тармақтар.
Мақсаты: Ағаштар немесе тармақтар ұғымын енгізу, негізгі түсініктерін беру, екілік тармақ құрылымымен таныстыру.
Тармақ дегеніміз - иеархиялық құрылым құратын элементтер мен қатынастардың жиынтығы.
Тармаќтыњ элементтері т%.йін деп аталады. Аѓаш тєрізді ќ+-рылым т%.пкі деп аталатын алѓашќы бір т%.йіннен басталатын кuптеген т%.йіндер жиынтыѓын ќ+-райды.
А
E
D
F
С
В
G
H
I
J

0-дењгей 1-дењгей 2-дењгей 3-дењгей

М+-нда аѓаштыњ т%.бірі дегеніміз - ары ќарай т%.бірі болмайтын тuбесі, яѓни м+-ндаѓы А. Єрбір тармаќтыњ бір ѓана т%.бірі болады. Тармаќтыњ ењ тuменгі т%.йіндері E, F, G, H жапыраќ деп аталады. Егер тармаќтыњ элементі жапыраќ болмаса, онда оны тармаќтыњ ішкі т%.йіні немесе тuбесі деп аталады. Бос тармаќ дегеніміз - ешќандай тuбесі жоќ тармаќты атаймыз. Балалыќ тuбесі деп - тармаќта орналасќан uзініњ ата-аналыќ тuбесінен тuмен ќарай т+-рѓан жєне онымен тікелей байланысќан тuбені атаймыз. Мысалѓа, егер i тuбесі F тuбесіне ќатысты балалыќ тuбесі болса, онда F тuбесі I тuбесіне ќатысты ата-аналыќ тuбе деп аталады.
Балалыќ т%.йіндер жєне олардыњ балалыќ т%.йіндері +-рпаќ деп аталады. Мысалѓа, E, F жєне I, J B - т%.йінініњ +-рпаќтары.
Тектері б+-л т%.йінніњ ата-аналары немесе ата-єжелері.
Тармаќтыњ єрбір т%.йіні осы т%.йіннен жєне барлыќ +-рпаќтарынан т+-ратын б+-таќтыњ т%.бірі болып табылады. Мысалы, В тuбесі E,F,I,J дењгейініњ т%.йіні. Мысалѓа, F т%.йіні F,I,J т%.йіндерінен т+-ратын б+-таќтыњ т%.бірі болып табылады. G т%.йіні +-рпаќсыз б+-таќтыњ т%.йіні. А т%.йіні uзі тармаќ болып табылатын б+-таќтыњ т%.бірі.
Кез келген т%.йіннен т%.йіннен бастап оныњ +-рпаќтарына ќарай ж%.ру белгілі бір жол бойымен ж%.зеге асады. Мысалѓа, А т%.бірінен бастап F т%.йініне дейінгі жол A,B,F тuбелерінен uтеді. Кез келген т%.йіннен оныњ +-рпаќтарына баратын жол жалѓыз ѓана болады. Т%.йінніњ дењгейі дегеніміз - ол т%.бірден осы осы т%.йінге дейінгі жолдыњ +-зындыѓы. Мысалѓа, А т%.бірініњ дењгейі 0-ѓа тењ. Т%.бірдіњ єрбір баласыныњ дењгейі 1-ге тењ. Мысалѓа F т%.йіні 2 дењгейдегі +-зындыѓы 2-ге тењ т%.йін болып табылады.
Тармаќтыњ терењдігі дегеніміз - оныњ кез келген т%.йінініњ максимальды дењгейі немесе тармаќтыњ терењдігі дегеніміз ол т%.бірден бастап т%.йінге дейінгі ењ +-заќ жолдыњ +-зындыѓы.

Тармақ тәрізді құрылымды беру әдістері
Тармақтарды берудің 4 түрлі әдісі бар:
* графтар
* кірістірілген жақшалар
* кірістірілген жиындар
* кесінді тізбектер.

1. Графтар. Бәрі А түйінінен тарайды

A
B
D
H
C
E
F
I
J
G

2. Кірістірілген жақшалар:

(A(B(E,F(I,J)), C(G),D(H)))

* Кірістірілген жиындар.
А
В
C
D
F
I
J
E
H
G

4. Кесінді тізбек.

A B E I
F J

C G
D H
Көбінесе тармақтарды бейнелеу үшін графтар қолданылады.

Дәріс 11.
Екілік бинарлық тармақтар. Екілік тармақтардың құрылымы.
Мақсаты: Екілік бинарлық тармақтар ұғымын қалыптастыру . Екілік тармақтардың құрылымы беру.

Программалауда екілік тармақтар кең қолданылады. Екілік тармақтар келесі қасиеттерге ие:
* екілік тармақта әрбір төбенің екіден артық балалық түйіні болмайды.
* кез келген төбенің балалық төбелері оң жақ балалық төбе және сол жақ балалық төбе болып бөлінеді. (Бұл тармақтардың графтық берілуіне қатысты айтылады. Кез келген тармақтарды оған сәйкес екілік тармақ ретінде беруге болады)
Екілік тармақ рекурсивті құрылымды болды. Себебі әрбір түйіні өзінің астындағы бұтақтың тамыры немесе түбірі болып табылады. Оны өздері де (бұтақтың) сол жақ және оң жақ бұтақтардың түбірлері болып табылатын балалары бар. Сондықтан тармақтарды өңдеу процедуоамы көбінесе рекурсивті болып табылады. Екілік тармақ дегеніміз - үш қиылыспайтын ішкі жиындарға бөлінетін түйіндер жиыны. Мұнда {R} - түбірлі түйін, {L1,L2,...,Ln} - R сол жақ бұтақ, {R1, R2,...,Rn} - R оң жақ бұтақ. Яғни оны былай бейнелеуге болады.

R
L
R
L
L
L
R

Оң жақ бұтақ

Сол жақ бұтақ

Екілік тармақ кез келген n деңгейде бірден бастап 2n түйіндерге дейін болуы мүмкін. Тармақтардың тығыздығы дегеніміз - тармақтың түйіндерінің оның тереңдігіне қатысты саны.
Мәліметтер құрылмы ретінде жоғары тығыздықтағы тармақтар маңызды болып табылады. Яғни, тығыз тармақ мәліметтің көп құрылымын сақтай алады және элементтерге кіруді тиімді жүзеге асыра алады.
Туындаған тармақтар, аяқталған тармақтар тығыздық шеткі шаралары немесе өлшемдері болып табылады. n тереңдіктегі аяқталған 2-к тармақ дегеніміз - 0-дан бастап n-1 - ге дейінгі әрбір деңгейі түйіндерінің толық жиыны бар және n деңгейіндегі барлық жапырақтары сол жағынан орналасқан екілік тармақтарды айтамыз. Толық тармақ дегеніміз - бұл n деңгейді 2n түйіндерде тұратын аяқталған бинарлық тармақ.

Туындалған тармақ Аяқталған тармақ
(4-деңгей) (3-деңгей)

Толық тармақ
(2-деңгей)

Тармақтың тереңдігі дегеніміз - оның түбірінен ең шеткі түйініне дейінгі ең ұзын жолдың ұзындығы болады. Мысалға, n түйіні бар туындалған тармақ үшін ең ұзақ жол ұзындығы n-1-ге тең болады. Сонда 5 түйіні бар тармақтың максимальды тереңдігі 4-ке тең болады. N түйіні бар аяқталған тармақ үшін log2n-ң бүтін бөлігіне тең болады. Мысалы, егер тармақтың 10000 элементі болса, n=10000, онда тереңдігі - int(log21000)= int(13,28)=13.

Екілік тармақтың құрылымы.
Екілік тармақты компьютер жадысына берудің екі түрлі жолы бар.
- Кәдімгі массивті пайдалана отырып тізбектеп беру
- Динамикалық құрылым ретінде беру.
Массивті пайдалана отырып тізбектеп беруде екілік тармақ бір өлшемдік массивке қапталады. Мұндай беруде тек бір ғана TREE сызықты массиві қолданылады. Тармақтың түбірі массивтің бірінші элементі TREE[0] - де орналасады. Келесі екі балалық төбелері көршілес элементтерде орналасады. Т.с.с.
Егер n түйіні массивтің TREE[k] элементін алатын болса, онда оның сол жақтағы балалық түйіні TREE[2K+1], ал оң жақтағы блалық түйіні - TREE[2K+2].
Кемшіліктері:
1. Тармақтың өлшемі массив өлшемімен шектелетін болады.
2. Тығыздығы көп емес тармақты сақтау үшін көп бөлігі пайдасыз қалатын үлкен массив керек болады.
Екілік тармақтарды жүзеге асыру үшін көбінесе мәліметтердің динамикалық құрылымдары пайдаланылады. Тармақтың әрбір түйінінде мәліметтер өрісі және көрсеткіштері бар 2 өріс болады.
Көрсеткіштер өрістері - сол жақ көсеткіш және оң жақ көрсеткіш деп аталады. Себебі, олар сәйкес сол және оң тармаққа көрсетеді.
Жапырақтық түйін - сол және оң жақ түйін көрсетуде Null болады.

А
В
F
С
D
E
G
H

Left
A
Right
Left
B
Right
Null
C
Right
Null
D
Null
Left
E
Null
H
Null
Null
G
Null
Null
F
Null
Right

Айталық, бізге n түйіні бар минимальды биіктікпен тармақ салу керек. Ол үшін барлық деңгейлердегі түйіндердің ең жоғарғы мүмкін санын, ең төменгісін санамағанда білуіміз керек. Идеал балансталған тармақ - бұл ең төменгісін санамағандағы барлық деңгейлердегі түйіннің ең жоғарғы мүмкін саны бар тармақ. Идеалды балансталған тармақта әрбір түйін үшін түйіндер саны оң және сол жақ бұтақта айырмашылығы бірге ғана тең болады. N түйіні берілгенде идеалды балансталған тармақты жасаудың алгоритмі:
oo түбір ретінде бір түйінді алу.
oo nl=n/2 түйіні бар сол жақ бұтақ салу (осы алгоритм көмегімен)
oo nr=n-nl-1 оң жақ бұтақ салу (алгоритм көмегімен)
Мысалы, 1,2,3,4,5,6,7,8,9,0 сандар тізбегі үшін идеалды балансталған тармақ келесі түрде болады:
1
2
0
7
3
5
4
6
8
9

Өрнектердің екілік тармақтары
Екілік тармақтар типіндегі құрылыстар матрицалық өрнектерді беруде көп қолданылады. Мысалға, 2+3 өрнегін мына түрде жазуға болады (екілік тармақ ретінде):

2 3
7+(6*4) өрнегін келесі түрде:

7 *
6 4
Тармақтардың мұндай типтері өрнектер тармақтары деп аталады. Мұндай тармақтардың әрқайсысы қөандай да бір өрнектерді сипаттайды. Тек қана екілік амалдарды сипаттайтын екілік тармақтар өрнектердің екілік тармақтары деп аталады. ( амалдар дегеніміз - бұл тек қана операндасы бар амалдар).
Өрнектің екілік тармақтары келесі қасиеттерге ие болады:
- Әрбір жапырақтық төбе бір ғана операндқа ие болады (операнд - сандар), ал жапырақ емс төбе - амалға ие болады.
- Әрбір бұтақ қандай да бір туындыны құрайды.
- Сол жақ немесе оң жақ бұтақтың түбіріне сәйкес амалды орындамас бұрын есептеліп шыққан болуы керек.
Өрнектер тармақтары өрнектер симантикасы анализіне арналған компелятор мен импетаторларда көп қолданылады. Ал оның жалпыланған ұғымы программалар синтаксисі анализі үшін компиляторларда қолданылады.

Дәріс 12.
Екілік іздеу тармақтары
Мақсаты: Екілік іздеу тармақтары ұғымы. Екілік тармаќтармен жүргізілетін амалдар. Байланған сызықтық тізімдер түсініктерін енгізу.

Екілік іздеу тармақтары программалауда кең таралған. Екілік іздеу тармақтарының әрбір төбесінің мәні:
oo Оның сол жағындағы бұтақ төбесінің кез келген мәнінен үлкен немесе тең.
oo Оның оң жақ бұтағының төбесінің кез келгенінің мәнінен кіші.

5 7
2 8 5 8
0 7 0 6
9 9
6 2

Программада екілік іздеу тармағының таралуы бұл тармақтарда іздеу әдістерінің тиімділігінің нәтижесі болып табылады.
Сызықтық құрылғылар үшін тізбектеліп іздеу алгоритмінің күрделілігі - О(n) - ға тең. Мұндағы n-құрылым элементтер саны. Ал аяқталатын бинарлық тармақ үшін күрделілігі - О(log2n)-ға тең.
Мысалға: 10000 элементтен тұратын тізімде тізбектеп іздеуде салыстырудың максимальды саны 10000-ға тең болады. Ал аяқталған тармақта іздеу 14 салыстырудан аспас еді.
Екілік іздеу тармағына элементті осу алгоритмі (тармақты қарау үнемі түбірден басталады):
- тармаққа қосылатын мән ағымдағы түйін мәніне салыстырылады.
- Егер тармаққа қосылтын мән ағымдағы түйін мәнінен кіші болса, онда келесілер тексеріледі:
а) егер ағымдағы түйінде ұрпақтар жоқ болса, онда жаңағы мәні бар түйінді сол жақ ұрпақ ретінде бекітеміз.
б) әйтпесе, (егер ұрпақ болса) тармақтың сол жақ бұтағы арқылы бір деңгейге төмендетеміз.
- Егер тармаққа қосылатын мән ағымдағы түйін мәнінен үлкен немесе тең болса, келесілер тексеріледі:
а) егер оң жақтағы ағымдағы түйінде ұрпақтар жоқ болса, онда мәні бар түйінді оң жақ ұрпқ ретінде бекітеміз.
б) әйтпесе, оң жақ бұтақ бойымен бір деңгейге төмендетеміз.

Екілік тармаќтармен ж%.ргізілетін амалдар

* Тармаќты толыѓымен ќарап uту алгоритмі
Тармаќтыњ тuбелерін с+-рыптау алгоритмі - тармаќты толыѓымен ќарап uту алгоритмі деп аталады. М+-ндай алгоритмдер т%.йінде %.ш т%.рлі єрекет жасайды: т%.йінге кіреді, сол жаќ б+-таќпен рекурсивті т%.рде тuмендейді, рекурсивті т%.рде оњ жаќ б+-таќпен тuмендейді.
Тармаќты ќарап шыѓудыњ 3 т%.рлі негізгі єдісі бар:
* Тура єдіс;
* Симметриялы єдіс;
* Кері єдіс;
Тармаќты толыѓымен ќарап шыѓу алгоритмі олардыњ түйініндегі uздерініњ єрекеттерімен байланысты реттерімен ажыратылады.
* Тура єдіс (жоѓарыдан тuмен ќарай):
- т%.йінге кіру;
- сол жаќ б+-таќтан uту;
- оњ жаќ б+-таќтан uту;

(1) 7
5 8
0 6 9
2
Екілік тармаќ берілген. Б+-л тармаќтаѓы т%.йінге кіру реті келесідей болады:
7 5 0 2 6 8 9

* Симметриялыќ єдіс (солдан оњѓа ќарай):
- сол жаќ б+-таќтан ж%.ріп uту;
- т%.йінге кіру;
- оњ жаќ б+-таќтан ж%.ріп uту;
Берілген (1) тармаќ %.шін симметриялыќ ќарап шыѓу келесі т%.рде болады:
0 2 5 6 7 8 9
Екілік тармаќты симметриялыќ ќарап шыѓу єдісі элементтерді uсу ретімен орналастырды. Осылайша, с+-рыптаудыњ таѓы бір алгоритмін +-сынуѓа болады:
А) массив негізінде с+-рыптау;
В) тармаќты симметриялыќ ќарап шыѓу єдісі ж%.зеге асады;
М+-ндаѓы ењ жаќсы жаѓдайда алгоритмніњ тиімділігі O(n log2n) болады.

* Тармаќты кері ќарай ќарап шыѓу єдісі (тuменнен жоѓарыѓа ќарай):
- сол жаќ тармаќтан ж%.ріп uту;
- оњ жаќ тармаќтан ж%.ріп uту;
- т%.йінге кіру;
Осы єдіс %.шін тармаќты ж%.ріп uтудіњ жолы:
2 0 6 5 9 8 7
¤рнектіњ екілік тармаќтарын ќарап uтуде жоѓарыда берілген %.ш єдіспен мынаны аламыз:
* Ќарап шыѓудыњ тура єдісі. ¤рнектерді жазудыњ префиксті форматына (жоѓарыдан тuменге ќарай) сєйкес келеді.
* Ќарап шыѓудыњ симметриялыќ єдісі uрнектерді жазудыњ инфиксті форматина сєйкес келеді.
* ќарап шыѓудыњ кері єдісі uрнектерді жазудыњ постфиксті форматына сєйкес келеді.

* Екілік іздеу тармаѓынан элементті алып тастау.
Тармаќтан элементті алып тастау алгоритмі тармаќтаѓы осы элементтіњ орналасќан орнына тєуелді болады жєне келесі тuрт жаѓдайды ќамтиды:
* Мєні х-ке тењ болатын элемент жоќ.
* Мєні х-ке тењ болатын элемент терминальды т%.йін болып табылады.
* Мєні х-ке тењ болатын элемент бір ѓана +-рпаќты болады.
* Мєні х-ке тењ болатын элемент екі +-рпаќты болады.

Бір ѓана +-рпаѓы болатын элементті алып тастауда ешќандай к%.рделілік жоќ. М+-ндай єрекеттер сызыќтыќ тізімдегі элементті алып тастауѓа +-ќсас болады.
2
3
7
0
5
6
4
9
8
3
2
0
7
5
9
4
8
6

Егер элемент екі +-рпаќты болса, онда екі баѓытта бір ѓана сілтемемен кuрсетуге келмейді. Б+-л жаѓдайда uшірілетін элементті ауыстыруѓа тура келеді. Ауыстыратын элемент %.шін оныњ сол жаќтаѓы ењ оњ жаќќы элемент, ал оњ жаќтаѓы ењ сол жаќќы элемент тањдап алынады (6 жєне 8 uшірілетін элементке мєндері жаѓынан жаќын элементтер).
2
3
7
0
5
6
4
9
8

Элементі uшіру алгоритмі. Алгоритм жоѓалѓанда ќарастырылатын 4 жаѓдайды ќамтиды:
1-жаѓдай: uшірілетін т%.йін табылѓан жоќ. Яѓни uшірук алгоритмі uз ж+-мысын тоќтатады.
2-жаѓдай: т%.йінніњ +-рпаќтары жоќ. Яѓни жапыраќ болып табылады. Б+-л жаѓдайда ата-аналыќ т%.йінді оныњ б+-таѓы бос болатындай етіп жањарту керек.
3-жаѓдай:
1. Т%.йінніњ сол жаќ +-рпаѓы бар, оњ жаќ +-рпаѓы жоќ. Яѓни сол жаќ б+-таќты оныњ ата-анасына жалѓастыру керек.
2. Т%.йінніњ оњ жаќ +-рпаѓы бар, сол жаќ +-рпаѓы жоќ. Яѓни т%.йінніњ оњ жаќ б+-таѓын оныњ ата-анасына жалѓастыру керек.
4-жаѓдай: екі +-рпаѓы бар т%.йінді алып тастау немесе uшіру. М+-нда uшірілетін т%.йінді ауыстыру ќажет. Ауыстыру %.шін сол жаќ б+-таѓы ењ оњ жаќтаѓы т%.йінді тањдаймыз.

Келесілерді аныќтаймыз:
D - uшірілетін т%.йін
P - uшірілетін элементтіњ ата-анасы
R - ауыстыратын т%.йін
PR - R т%.йінніњ ата-анасы.

* D т%.йінініњ сол жаќ б+-таѓына кuшеміз. Себебі, R ауыстыратын т%.йін uшірілетін D т%.йінінен кіші болады.
* R ауыстыратын т%.йін D т%.йінініњ сол жаќ б+-таѓындаѓы максимальды т%.йін болып табылады. Оњ жаќ б+-таќ бойынша тuмен жылжып, P ауыстыратын т%.йінді іздейміз. Жылжу барысында RR ата-аналыќ т%.йінді баќылап отырамыз. М+-нда екі м%.мкін жаѓдай бар:
* Оњ жаќ б+-таќ бос. R ауыстытылатын т%.йін uшірілетін т%.йінніњ сол жаќ баласы болып табылады. Ал PR сєйкесінше D т%.йініне кuрсетіледі. М+-ндай жаѓдайда келесі єрекеттерді орындаймыз:
А) D т%.йінініњ оњ жаќ б+-таѓын R т%.йініне ќосамыз.
Б) ¤шірілетін т%.йінніњ P ата-анасын R т%.йініне ќосамыз.
C
A
E
D
B
A
C
D
E

P P
D R
R PR=D
Оњ жаќ б+-таќ оњ жаќ б+-таќ

* Оњ жаќ б+-таќ бос емес. М+-ндай жаѓдайда ауыстыратын т%.йін жапыраќтыќ т%.йін болады немесе тек ќана сол жаќ б+-таѓы бар т%.йін болады. Келесі єрекеттерді орындаймыз:
А) R т%.йінін тармаќтан бuліп аламыз.
Б) R т%.йінініњ +-рпаќтарын оныњ ата-аналыќ РR т%.йініне жалѓаймыз. (R-діњ сол жаќ б+-таѓы РR-ѓа оњ жаќ б+-таќ болып жалѓанады).
С) ¤шірілетін D т%.йіні R т%.йінімен ауыстырылады. Яѓни D т%.йінініњ +-рпаќтары R т%.йінініњ +-рпаќтары болып жалѓанады, ал R т%.йіні ата-аналыќ P т%.йініне жалѓанады.

Дәріс 13.
Массивтермен берілген бинарлыќ тармаќтар
Мақсаты: Массивтермен берілетін бинарлық тармақтар ұғымын енгізу. Турнирлік сұрыптау, пирамидалар түсініктерін енгізу.

Массивтермен берілген бинарлыќ тармаќтар екіге бuлінеді:
* Турнирлік с+-рыптау.
* Пирамидалар.

Егер бинарлыќ мєліметтер элементтерде саќталса, онда мєліметтерге тура кіруді ж%.зеге асыруѓа болады. Массивтіњ 0-элементі б+-л тармаќтыњ тамыры немесе т%.бірі. n элемент массиві %.шін ai т%.йінніњ +-рпаќтарын келесі формуламен есептеуге болады. Сол жаќтаѓы индекс - 2i+1, ал оњ жаќтаѓы индекс - 2i+2-ге тењ, ал ата-анасыныњ индексін - (i-1)/2 формуласымен аныќтаймыз. Тармаќталѓан массивті пайдалану беруді аяќтаѓалѓан бинарлыќ тармаќ %.шін ќолдану ќолайлы. Біраќ тыѓыздыѓы аз болатын тармаќты саќтаѓанда массивте пайдаланылмайтын элементтер болады да массивпен ж+-мыс істеуде бірќатар ќиындыќтар туѓызуы м%.мкін. Мысалы:
A[]=(5,1,3,9,6,2,4,7,0,8)

5
1
4
3
9
6
7
0
2
8

Турнирлік с+-рыптау
Бинарлыќ тармаќтар шешімдер ќабылдау термаќтары ретінде кuп ќолданылады. Мысалы, спорттыќ турнирді алайыќ. М+-нда єрбір ішкі т%.йін екі ойыншыныњ кездеріндегі жењімпазѓа сєйкес келеді.
Турнирлыќ m, n элементтен m массивті с+-рыптауѓа ќолданылуы м%.мкін. Турнирлыќ с+-рыптауды келесі мысалда ќарастырайыќ:
A[8]=(35, 25, 50, 20, 15, 45, 10, 40)
Осы массивті uсу ретімен с+-рыптау ќажет.
1. Массив элементтері бинарлыќ тармаќ к дењгейінде болады. М+-ндаѓы: 2[k]>=n n - массив элементтер саны. Б+-л жаѓдайда 2[3]=8, яѓни k=3 болады.

35
40
10
45
15
20
50
25

2. Ата-аналыќ т%.йінге ж+-птарѓа элементтердіњ кішісі орналасады, ењ соњѓы салыстыру нєтижесінде массивтіњ ењ кіші элементі 0-дењгейіне (тамырына) т%.седі.

10
20
16
25
20
15
16
35
40
10
45
15
20
50
25

3.
10

15
20
15
25
20
15
40
35
40
25
45
25
10
30
25
Бір элемент алынып тасталады.

4. 15
20
15
25
20
15
40
35
40
45
15
20
50
25

10
15

50
50
50

50
5.

10
15
20
25
35
40
45
50

Осы процесс барлыќ жапыраќтары алынып тасталѓанша ж%.ргізіліп ж%.ре береді. Ењ соњѓы т%.йін (ењ %.лкен элемент) барлыѓын %.нсіз келісім бойынша шыѓады.

Дәріс 14.
Пирамидалар
Мақсаты: Пирамидалар, негізгі түсініктерін беру. Пирамидаларда түрлендірулер жүргізу, амалдар қолдану.

Пирамида дегеніміз - дењгейлер бойынша т%.йінтік реттілігі бар бинарлыќ тармаќ. Пирамидаларды максимальды пирамидалар жєне минимальды пирамидалар деп бuледі.
Максимальды пирамида - ата-аналыќ т%.йін uзініњ балаларыныњ єрќайсыснан %.лкен немесе тењ болады. Т%.бірде ењ %.лкен элемент жатады.
Минимальды пирамида - ата-аналыќ т%.йін uзініњ балаларыныњ єрќайсысынан кіші немесе тењ болады. Ал т%.бірде ењ кіші элемент жатады.
Мысалѓа, минимальды пирамидаѓа:
5
10
55
50
11
20
25
22
52

60
50
50
55
30
10
25
20
52
Мысалѓа, максимальды пирамидаѓа:

Пирамидалар клиентке минимальды элементке тура кіру жаѓдайында ќолданылады. Пирамида тізім болып табылады. Онда мєліметтер бинарлыќ тармаќ т%.рінде саќталады. Пирамидаларды uњдейтін барлыќ алгоритмдер uздері тармаќты жањартып, пирамидалыќ реттеуді ж%.зеге асырып отырулады ќажет.

Массивті пирамидаѓа т%.рлендіру
Пирамиданыњ соњѓы элементініњ индексі n-1-ге тењ. Оныњ ата-анасыныњ индексі n-2-ге тењ. Жєне ол пирамидалардыњ соњѓы жапыраќтыќ емес т%.йін болып табылады. Осы индекс массивті т%.рлендіру %.шін бастапќы индекс болып табылады. Мынадай б%.тін санды массив берілсін:
А(10)=(9,12,17,30,50,20,60,65,4,19)
Оны пирамида т%.рінде былай жазамыз:

17
12

20
50
30
60

19
4
65

М+-ндай жапыраќтардыњ индекстары 5,6,7,8,9 болады. Ата-анасының индекстары - 0,1,2,3,4.

50
19

* қарастырамыз.

А(4)=50 ата-анасы өзінің А(9)=19 деген ұрпағынн үлкен болып табылады. Сондықтан А(9) бен А(4) орындарын ауыстырамыз:

9
12
60
17
30
19
65
4
20
50

А(3)=30 ата-анасы А(8)=4 деген өзінің ұрпағынан үлкен. Сондықтан А(3) пен А(8) орындарын ауыстырамыз. (егер екі ұрпақтың екеуі де кіші болса, ең кіші баласымен орын аыстырамыз).

9
12
60
17
4
19
65
30
20
50

Екі деңгейдегі А(2)=17 ата-анасы пирамиданың шартн қанағаттандырады. Сондықтан ауыстырулар жүргізілмейді. Ал А(1)=12 өзінің А(3)=4 деген баласынан үлкен болып тұр. Сондықтан олардың орындарын ауыстырамыз:
9
4
60
17
12
19
65
30
20
50

Осы процесс түбірлік түйінде аяқталады. А(0)=9 ата - анасы өзінің А(1)=4 деген ұрпағымен орын ауысады.

4
9
60
17
12
19
65
30
20
50

Нәтижелік тармақ осы пирамида болады.

Пирамидаға элемент қосу
1. Жаңа элемент тізімнің соңынан қосылады:
5
10
55
50
11
20
25
22
52
8

2. Егер жаңа элемент өзінің ата-анасына қарағанда кіші мәнге ие болса, онда түйіннің орнын ауыстырамыз.
5
10
55
50
11
20
25
22
52
8

5
10
55
50
11
20
25
22
52
8
3. Жаңа ата-ана бала ретінде қарастырылады да одан да ата-ана үшін пирамидада шарт тексеріледі.

4. Осы процесс ата-ананың жолын қайталап, жаңа элементтен кіші ата-ананы кезіктіргенде немесе түбірлі түйінге келгенде тоқтайды.

Элементтерді пирамидадан өшіру

Мәліметтер қанашанда тармақтың түбірінен өшіріледі.
5
10
55
50
11
20
25
22
52

- Түбірлік түйінді өшіріп, оны соңғы түйінмен алмастыру.
- Егер жаңа түбірлік түйін өзінің ұрпақтарының кез келгенінен үлкен болса, онда оны өзінің кіші ұрпақтарымен орын ауыстыру керек.

22
10
55
50
11
20
25

52
10
22
55
50
11
20
25

10
11
55
50
20
20
25

52
3. Кіші ұрпақтар бойынша жүргізілетін осы жол элемент ата-ана ретінде дұрыс позицияға келгенше немесе тізімнің соңына жеткенше далғасады.

Пирамидалық сұрыптау
oo Массивті пирамидаға түрлендіру.
oo 20
25
75
35
50
А(0)-ді тізбетеп жоққа шығару және оны А(n-1), А(n-2) т.с.с А(1)-ге дейін қосу. Пирамидалық сұрыптау процесінде кезекті ең кіші элементтер өшіріліп отырады да, тізбекті түрде массивтің соңғы жағына орналасады. Осылайша, кему реті бойынша сұрыпта жүргізіледі. Мысал: А(5)=(50,20,75,35,25).

Мысалға А(5)=(50,20,75,35,25)

1. 20-ны өшіріп, А(4)-ке сақтаймыз:
25
35
75
50
20

2. 25-ті өшіріп, А(3)-ке қоямыз:
35
50
75
25
20

3. 35-ті өшіріп, А(2)-ге қоямыз:
50
75
35
25
20

4. 50-ді өшіріп, А(1)-ге қоямыз:
75
50
35
25
20

Сонымен, түбірі ғана қалғандықтан, массив сұрыпталды.

Есептеу тиімділігі.
n элементтен тұратын массив тереңдігі k=log2n болатын аяқталған бинарлық тармаққа сәйкес келеді. Массивті пирамидаға түрлендіру n/2 операциядан тұрады. Олардың әрқйсысы k салыстырудан артық салыстыруды қажет етпейді. Сұрыптаудың екінші фазасы n-1 операциясын қажет етеді. Олардың әрқайсысы k салыстырудан тұрады. Пирамидалық сұрыптаудың ең жаман жағдайдағы күрделілігі k*n/2+k*(n-1)=((3n/2)-1) log2n тең болады. Алгоритмнің күрделілігі мынадай ретке тең: O(n log2n).
Пирамидалық сұрыптау қосымша жадыны қажет етпейді. Ал мысалға турнирлық сұрыптауға қосымша жаңа массив жасалу қажет.

Дәріс 15.
Балансталған тармақтар. Графтар.
Мақсаты: Балансталған тармақтар ұғымын енгізу. AVL тармақтары, балансталған тармақтарға қосу, алып тастау әрекеттерін түсіндіру. Графтар. Негізгі ұғымдары мен анықтамаларын беру. Көршілестік матрицасы, инцидиенттік матрицасы түсініктері.

Негізгі ұғымдар. Бинарлық тармақтар алпы мәліметтерге қол жеткізуге арналған. Идеалды яғни ең жақсы жағдайда тармақ балансталған болады және реттілік биіктігі O(nlog2n)-ға тең болады. Алайда, кейбір мәліметтер үшін тармақ туындаған болуы мүмкін. Онда оның биіктігі O(n)-ға тең болады және мәліметтерге кіру әжептәуір ақырындайды.
Тармақ балансталған болады сонда тек сонда ғана егер әрбір түйін үшін оның екі бұтағының биіктігі бір-бірінен бірге ғана айырмашылығы болса. Балансталған тармақтарды AVL тармақтар деп атайды (Ойлап тапқандардың фамилиялары бойынша - Адельсон-Венский-Ландис).

Іздеудің бинарлық тармағы:

1
5
3
4
1
2
5
4
3
2

AVL тармақтар берілуі іздеудің бинарлық тармағына ұқсас болады. Барлық операциялар ұқсас тек қана тармаққа қою және тармақтан алып тастау операциялары өзгеше. Сол жақ және оң жақ бұтақтың арақатынасы туралы ақпаратты сақтау үшін түйіннің типі анықтамасына ө р і с қосылады. Ол өріс сол жақ және оң жақ бұтақтың айырмасын көрсететін баланстық көрсеткіш. Егер баланс - 1-ге тең болса, онда түйіннің сол жағы басады. Себебі, сол жақ бұтақтың биіктігі көп. Ал, баланс оң болса, онда түйін оңға қарай тартады. Жалпы биіктігі бойынша балансталған тармақ баланс -1-ге тең болады. Ал AVL тармақтары [-1;1] араларында тербеледі.

Балансталған тармаққа қосу

AVL тармақтардың артықшылығы сәйкес қосу және алып тастау алгоритмдермен қамтамасыз етілген олардың баланстылығында болады. Элемент қосу іздеудің бинарлық тармағына ұқсас. Яғни, сол жақ және оң жақ ұрпақтары бойынша рекурсивті түсу жүргізіледі. Бос бұтақ кезіккенше жүргізіледі. Одан кейін осы жерде жаңа түйінді қосу жүзеге асды.
- Тармақта кілт жоқ болғанша іздеу жолымен жүре беру.
- Жаңа түйін қосу және баланыстылықтың жаңа көрсеткішін анықтау.
- Іздеу жолымен қайтадан жүру және әрбір түйін үшін баланстылық көрсеткішін тексеру.
Үш жағдай болуы мүмкін. Алғашқы екеуінде түйін баланстылықты сақтайды. Бұтақтар реоргинизациясы қажет емес. Тек қана берілген түйіннің баланстылық көрсеткішін корректілеу керек. Үшінші жағдайда тармақты қайта баланстау түйіннің бірлік немесе екілік айналымын қажет етеді.
1-жағдай. Іздеу бағытындағы түйін басынан бастап балансталған деп есептейміз. Яғни балнс 0-ге тең. Бұтаққа жаңа элементті қосқаннан кейі, түйін қосу қай жақ бұтаққа жүргізілгеніне байланысты солға немесе оңға тарта бастайды. Егер элемент сол жақ бұтаққа қосылған болса, онда баланстық көрсеткіш -1-ге тең, ал оң жақ бұтаққа қосылған болса, баланстық көрсеткіші +1-ге тең болады.
40
0
20
1
45
0
30
0
50
0
60
0

Осы балансталған тармаққа 55 деген түйінді қосамыз:
40
0
20
1
45
0
30
0
50
0
60
0
55
0

2-жағдай. Түйіннің бұтағының біреуінің бір жағы басым және жаңа элемент жеңіл бұтаққа қосылады да, түйін балансталған болып өзгереді.
40
-1
20
1
45
0
30
0
50
0
60
0
15
0
25
0
32
0

55 түйінін қосқаннан кейін:
40
0
20
1
45
0
30
0
50
0
60
-1
15
0
25
0
32
0
55
0

3-жағдай. Түйіннің бұтақтарының бір жағы басым, жаңа элемент неғұрлым ауыр жағына қосылады. Ал олай болса, баланстылық шарты бұзылады. Себебі, баланс [1;1] шегінен аспуы тиіс. Ал тепе-теңдікті сақтау үшін бұрылыс жасау қажет.

Графтар

Граф дегеніміз - G= жұбы. Мұндағы V-төбелердің құр емес жиыны. E - қабырғалар жиыны. Яғни, төбелер жұбы немесе қабырғалары жиыны деп аталатын мәліметтер элементтері жиынынан тұрады. Төбелер қалаларды көрсететін болса, қабырғалар арасындағы жолдарды көрсетеді.

Москва
Томск
Новосибирск

1250 900

450

Егер е жұптары реттелмеген болса, яғни жолдардағы қозғалыс екі бағытта да жүретін болса, онда граф бағдарланбаған әйтпесе бағдарланған деп аталады. Егер қабырғалардың бір бөлігі бағытталған немесе бағдарланған болса, мұндай графтар аралас графтар деп аталады.
V1, V2, ..., Vn төбелерінің тізімі жол деп аталады. Мұндағы барлық i үшін 1<=i<=n, Vi,Vi+1 қабырғалары болады.
Бағдарланған графта V1, V2, ..., Vn төбелердің тізімі.
V1V2, V2 V3,...,Vn-1 Vn бағытталған доға түрінде болады. Графтардағы жол қарапайым деп аталады, егер графтардың төбелері әртүрлі болса. Жолдың ұзындығы осы жолды құрайтын қабырғалардың санына тең болса.
Vi және Vj төбелері байланған деп аталады егер, осы төбелер үшін Vi+1,Vi+2,.., Vj жолы бар болса. Граф байланысшы граф деп аталады егер, оның кез келген төбелер жұптары үшін оларды қосатын қарапайым жол болса.
Цикл дегеніміз - ұзындығы бірден кем болмайтын бір төбеден басталып сол төбеден аяқталатын қарапайым жол.
Графтардағы тармақ дегеніміз - бұл циклсыз графтар. Графтар өлшенген деп аталады егер, графтың әрбір қабырғасына мәні немесе салмағы жазылса.
Мысалға, салмақ ретінде қалалардың арасындағы арақашықтық немесе қандай да бір жұмыстың жүргізілу уақыты алынады.
Графтарды берудің келесідей әдістері бар:
* Инцидиенттік матрицасы.
* Көршілестік матрицасы.
* Салмақтық матрицасы.
* Қабырғалар тізімі.
* Көршілестік тізімі.
Қандай да бір нақтылы есепті шығару үшін қолдану қолайлылығына қарай осы әдістердің кез келгенін пайдалануға болады.
Инцидиенттік матрицасы дегеніміз - размері nm болатын матрица. Мұндағы n-төбелер саны, m-қабырғалар саны. Бағытталған граф үшін х,у қабырғаларына сәйкес келетін баған, у төбесіне сәйкес келетін жолда 1 болады. Ал х төбесіне сәйкес келетін жолда -1 болады, қалған жолдарда 0 болады. Тұзақ жағдайында басқа сан берілуі мүмкін. Яғни, хх болғанда 2 деген сан беріледі. Мысалы,

1 2 4 5

3 6

граф берілген, оның инцидиентті матрицасын жазамыз:

(1,2) (1,3) (3,2) (3,4) (5,4) (5,6) (6,5)

Бағытталған граф үшін х,у қабырғасына сәйкес келетін баған х,у төбесіне сәйкес келетін жолда 1 болады да, қалған жолдарда 0 болады.
2 4
1 6

+ 5

(1,2)(1,3)(1,5)(2,3)(2,5)(3,4)(4,5)(4,6)(5,6)

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

Көршілестік матрицасы
Көршілестік матрицасы дегеніміз - өлшемі nМ болатын және егер i-ші төбесі j-ші төбесімен көршілес болса мәні бірге тең болатын, әйтпесе 0-ге тең болатын матрица.
Бағытталмаған графтар үшін х, у қабырғасы у,х қабырғасына тең болады. Сондықтан олар үшін көршілестік матрицасы әрқашан симметриялы. Оларда алдыңғы граф үшін матрица мынадай:
1 2 4 5

3 6

Бағытталмаған граф үшін көршілестік матрица:
2 4
1 6
5
3 5

Көршілес матрица симметриялы болып табылады, сондықтан ЭЕМ-ға енгізіп, өңдеуге қолайлы.

3 Зертханалық сабақтар
Зертханалық жұмыс №1
Тақырыбы: Сызықты байланысқан мәліметтер құрылымдарын ұйымдастыру және олармен жүргізілетін амалдар.

Жалпы мәлімет
Массив дегеніміз мәліметтердің құрылымдалған жиыны. Ол жалпы аты бар, бір типті элементтердің белгіленген санының реттелген жиынтығын сипаттау үшін қолданылады. Массив элементтерін белгілеу үшін массив айнымалысы аты және индексі қолданылады. Жұмысты орындамас бұрын массив типті айнымалыларды қолдануды және сипаттау ережелерін үйрену керек.
Мысалы: Екі өлшемді массив берілген. Әрбір жолда оның нольге тең емес элементтерін ретін сақтай отырып, жолдың басына жазу керек, ал барлық нольге тең элементтерін жол соңына жазу керек. Жаңа массив жасауға болмайды.
Есепті шешу этаптары:
* Бұл есепті шешудің алгоритмдерінің біреуінің мәні массивті жол бойынша қарап, әрбір жолда (0:сан) жұбын тауып, содан кейін олардың өзара орынын ауыстырып, осылайша жолда мұндай жұптар қалмағанға дейін жалғастыруда.
* Программаның паскальда жазылуы:
* program маs_1;
var
V: array[1..100,1..100] of integer;
m,n, i,j, c: integer;
flag: boolean;
begin
<массив өлшемін енгізу m*n>
<массив ұяшықтарын толтыру>
for i:=1 to m do
repeat
flag:= true;
for j:=1 to n-1 do
if (v[i,j]=0) and (v[i,j+1]<>0) then begin
<олардың орынын ауыстыру>
flag:= false;
end;
until flag;
<массивты басып шығару>
readln;
end.

4. Алгоритмнің блок-схемасы

Бірінші жолды реттейміз:

Блок-схеманың алгоритмы бүтіндей:

5. Паскальдағы программа:
program mas_1;
var
V:array[1..100,1..100] of integer;
m,n, i,j, c: integer;
flag: boolean;
begin
write('Массив өлшемін енгіз m-n> '); readln(m,n);
for i:= 1 to m do
for j:= 1 to n do begin
write('V[',i,',',j,']= '); readln(V[i,j]);
end;
for i:=1 to m do
repeat
flag:= true;
for j:=1 to n-1 do
if (v[i,j]=0) and (v[i,j+1]<>0) then begin
c:=v[i,j]; v[i,j]:=v[i,j+1]; v[i,j+1]:=c;
flag:= false;
end;
until flag;
for i:= 1 to m do begin
for j:= 1 to n do write(V[i,j]:2);
writeln
end;
readln;
end.

Бақылау сұрақтары:

* Массив типті айнымалылар қалай анықталады?
* Бір өлшемді, екі өлщемді массивтің жекелеген элементіне кіру қалай жүзеге асырылады?
* Массивтың элементтері экранға қалай шығарылады?
* Екі өлшемді массивты экранға матрица түрінде шығаратын программа фрагментін келтір.
* X : Array[0..1, 0..1, 0..1, 0..1, 0..1, 0..1] of Integer алты өлшемді массивына неше сан жазуға болады?

Тапсырмалар:
* а1,а2,а3 бұтін сандары берілген. Бүтін санды [bij]i,j=1,2,3 матрицасын алу керек, мұнда bij=ai-3aj.
* [aij]i=1,...10; j=1,...12 - бүтін санды матрицасын алу керек, aij=i+2j.
* N өлшемді квадрат матрица берілген. Бас диагональдан жоғары, төмен орналасқан нольдік элементтер санын тап.
* n * m өлшемді матрица берілген. b векторын алу керек, онда элементтер былай есептеледі: - сәйкес жолдардың элементтерінің көбейтіндісі; - сәйкес бағандардың арифметикалық ортасы; сәйкес жолдардың ең үлкен және ең кіші элементтерінің айырмасы; - бағандағы алғашқы теріс элементтердің мәндері.
* A[1..m,1..n] екі өлшемді массив берілген. Элементтері тең болатын B[1..m] бір өлшемді массивын жасау: - жолдардың элементтер қосындысына; - жолдардың элементтер көбейтіндісіне; - жолдардың элементтерінің арифметикалық орталарынына.
* Берілген массивте жұп орында тұрған элементтерді тақ орында тұрған элементермен орынын ауыстыру.
* Берілген массивтің элементтерін кері ретпен орналастыр (бірінші элементті соңғымен, екіншісін оның алдыңғысымен, т.с.с., егер, массив элементтерінің саны тақ болса, ортаңғысы өзгеріссіз қалады).

Зертханалық жұмыс №2
Тақырыбы:Ағаш типті мәліметтер құрылымдарын ұйымдастыру.

Жалпы мәлімет
Тармақ дегеніміз - иеархиялық құрылым құратын элементтер мен қатынастардың жиынтығы.
Тармақтың элементтері түйін деп аталады. Ағаш тәрізді құрылым түпкі деп аталатын алғашқы бір түйіннен басталатын көптеген түйіндер жиынтығын құрайды.
А
E
D
F
С
В
G
H
I
J

0-деңгей 1-деңгей 2-деңгей 3-деңгей

Мұнда ағаштың түбірі дегеніміз - ары қарай түбірі болмайтын төбесі, яғни мұндағы А. Әрбір тармақтың бір ғана түбірі болады. Тармақтың ең төменгі түйіндері E, F, G, H жапырақ деп аталады. Егер тармақтың элементі жапырақ болмаса, онда оны тармақтың ішкі түйіні немесе төбесі деп аталады. Бос тармақ дегеніміз - ешқандай төбесі жоқ тармақты атаймыз. Балалық төбесі деп - тармақта орналасқан өзінің ата-аналық төбесінен төмен қарай тұрған және онымен тікелей байланысқан төбені атаймыз. Мысалға, егер i төбесі F төбесіне қатысты балалық төбесі болса, онда F төбесі I төбесіне қатысты ата-аналық төбе деп аталады.
Балалық түйіндер және олардың балалық түйіндері ұрпақ деп аталады. Мысалға, E, F және I, J B - түйінінің ұрпақтары.
Тектері бұл түйіннің ата-аналары немесе ата-әжелері.
Тармақтың әрбір түйіні осы түйіннен және барлық ұрпақтарынан тұратын бұтақтың түбірі болып табылады. Мысалы, В төбесі E,F,I,J деңгейінің түйіні. Мысалға, F түйіні F,I,J түйіндерінен тұратын бұтақтың түбірі болып табылады. G түйіні ұрпақсыз бұтақтың түйіні. А түйіні өзі тармақ болып табылатын бұтақтың түбірі.
Кез келген түйіннен түйіннен бастап оның ұрпақтарына қарай жүру белгілі бір жол бойымен жүзеге асады. Мысалға, А түбірінен бастап F түйініне дейінгі жол A,B,F төбелерінен өтеді. Кез келген түйіннен оның ұрпақтарына баратын жол жалғыз ғана болады. Түйіннің деңгейі дегеніміз - ол түбірден осы осы түйінге дейінгі жолдың ұзындығы. Мысалға, А түбірінің деңгейі 0-ға тең. Түбірдің әрбір баласының деңгейі 1-ге тең. Мысалға F түйіні 2 деңгейдегі ұзындығы 2-ге тең түйін болып табылады.
Тармақтың тереңдігі дегеніміз - оның кез келген түйінінің максимальды деңгейі немесе тармақтың тереңдігі дегеніміз ол түбірден бастап түйінге дейінгі ең ұзақ жолдың ұзындығы.

1. Графтар. Бәрі А түйінінен тарайды

A
B
D
H
C
E
F
I
J
G

2. Кірістірілген жақшалар:

(A(B(E,F(I,J)), C(G),D(H)))

* Кірістірілген жиындар.
А
В
C
D
F
I
J
E
H
G

4. Кесінді тізбек.

A B E I
F J

C G
D H
Көбінесе тармақтарды бейнелеу үшін графтар қолданылады.

Тапсырмалар: Реттелген екілік тармақ жасап, оны экранға шығаратын бағдарлама құру керек.

Зертханалық жұмыс №3

Тақырыбы: Граф типті мәліметтер құрылымдарын ұйымдастыру.

Жалпы мәлімет
Граф дегеніміз - G= жұбы. Мұндағы V-төбелердің құр емес жиыны. E - қабырғалар жиыны. Яғни, төбелер жұбы немесе қабырғалары жиыны деп аталатын мәліметтер элементтері жиынынан тұрады. Төбелер қалаларды көрсететін болса, қабырғалар арасындағы жолдарды көрсетеді.

Москва
Томск
Новосибирск

1250 900

450

1 2 4 5

3 6

граф берілген, оның инцидиентті матрицасын жазамыз:

(1,2) (1,3) (3,2) (3,4) (5,4) (5,6) (6,5)

+ 5

(1,2)(1,3)(1,5)(2,3)(2,5)(3,4)(4,5)(4,6)(5,6)

3 6

Бағытталмаған граф үшін көршілестік матрица:
2 4
1 6
5
3 5

Көршілес матрица симметриялы болып табылады, сондықтан ЭЕМ-ға енгізіп, өңдеуге қолайлы.
Тапсырмалар: Инцидиенттік матрицасы, көршілестік матрицасы, салмақтық матрицасы, қабырғалар тізімі, көршілестік тізімі әдістерінің кез-келген біреуін қолдана отырып есеп шығару мысалын көрсет.

Зертханалық жұмыс №4
Тақырыбы:Іздеу есебін шешу.

Жалпы мәлімет
Массивтер көбінесе статистикалық мәліметтер, анықтамалық баслымдар, сөздіктер дайындауда қолданылады. Ақпаратты іздеудің ең қарапайым әдісі бұл жағдайда массивтың барлық элементтерін тізбектеп қарап шығу болып табылады. Іздеуді жеңілдету мақсатында массив мазмұны белгілі әдістермен сұрыпталып, реттеледі.

Мысалы: Реттелген массивте керекті элементті іздеу есебін және оны шешу алгоритмін қарастырайық.
N элементтен тұратын нақты сандардың А реттелген массивы берілген. Массивте В саны бар ма, егер бар болса оның массивтегі номерін анықтау керек.
А массивында В - ға тең элемент бар болып, A[p]=B болатындай қандай да бір p индексі бар болсын. Кез-келген салыстырудың A[s]> мағынасына келеді.

Бақылау сұрақтары:
* Ортасынан бөлу әдісімен элементті іздеу идеясы неменеге негізделген?
* Ортасынан бөлу әдісімен массив элементін іздеу алгоритмін жасаудағы әрекеттер тізбегін сипатта.

Тапсырмалар варианттары:
* 15 элементті массивті клавиатурадан енгізген бүтін сандардан сақтау программасын жаса. Массивтың мазмұны өсу реті бойынша сұрыпталады. Осыдан кейін, клавиатурадан бақылау саны енгізіледі де, массивте бар-жоғы тексеріледі. Бар болса, массивтің элементі номері монитор экранына шығарылады.
* Массивте 10 әртүрлі бүтін сандарды сақтауды ұйымдастыратын программа жаса. Массивтың мазмұны өсу реті бойынша сұрыпталады. Осыдан кейін, клавиатурадан бақылау саны енгізіледі де, массивте бар-жоғы тексеріледі. Бар болса, массивтың бақылау санына тең элементі нольмен ауыстырылады да, массив монитор экранына шығарылады.
* Массивте 15 әртүрлі бүтін сандарды сақтауды ұйымдастыратын программа жаса. Массивтың мазмұны кему реті бойынша сұрыпталады. Осыдан кейін, клавиатурадан бақылау саны енгізіледі де, массивте бар-жоғы тексеріледі. Бар болса, экранға бақылау санына дейінгі массив мазмұны шығарылады.

Зертханалық жұмыс №5
Тақырыбы: Іздеу есебін шешу. Толық іздеу: тармақтар және шекаралар әдістері. Динамикалық программалау.

Тапсырмалар варианттары:
* 10 бүтін сан массивы беріледі. Оны сұрыптап, ондағы бақылау санын тап. Бақылау санына дейінгі барлық элементтерді қарама-қарсыға өзгерт.
* 20 символдан тұратын массив берілген. Сұрыптап, ондағы бақылау символын тап. Экранға бақылау символынан бастағандағы элементтерді шығар.
20 саннан тұратын А массивы берілген. Оны кему реті бойынша орналастыр. Клавиатурадан 2 a және b бақылау сандарын енгіз. Сандар массивында a мен b аралығында жатқан сандардың бар-жоғын тексер. Бар болса, табылған сандар мен индекстерін экранға шығар.

Зертханалық жұмыс №6
Тақырыбы: Жылдам іздеу

Жалпы мәлімет
Екілік іздеу тармақтары программалауда кең таралған. Екілік іздеу тармақтарының әрбір төбесінің мәні:
oo Оның сол жағындағы бұтақ төбесінің кез келген мәнінен үлкен немесе тең.
oo Оның оң жақ бұтағының төбесінің кез келгенінің мәнінен кіші.

5 7
2 8 5 8
0 7 0 6
9 9
6 2

Екілік тармақтармен жүргізілетін амалдар

Тармақты толығымен қарап өту алгоритмі
Тармақтың төбелерін сұрыптау алгоритмі - тармақты толығымен қарап өту алгоритмі деп аталады. Мұндай алгоритмдер түйінде үш түрлі әрекет жасайды: түйінге кіреді, сол жақ бұтақпен рекурсивті түрде төмендейді, рекурсивті түрде оң жақ бұтақпен төмендейді.
Тармақты қарап шығудың 3 түрлі негізгі әдісі бар:
* Тура әдіс;
* Симметриялы әдіс;
* Кері әдіс;
Тармақты толығымен қарап шығу алгоритмі олардың түйініндегі өздерінің әрекеттерімен байланысты реттерімен ажыратылады.
* Тура әдіс (жоғарыдан төмен қарай):
- түйінге кіру;
- сол жақ бұтақтан өту;
- оң жақ бұтақтан өту;

(1) 7
5 8
0 6 9
2
Екілік тармақ берілген. Бұл тармақтағы түйінге кіру реті келесідей болады:
7 5 0 2 6 8 9

* Симметриялық әдіс (солдан оңға қарай):
- сол жақ бұтақтан жүріп өту;
- түйінге кіру;
- оң жақ бұтақтан жүріп өту;
Берілген (1) тармақ үшін симметриялық қарап шығу келесі түрде болады:
0 2 5 6 7 8 9
Екілік тармақты симметриялық қарап шығу әдісі элементтерді өсу ретімен орналастырды. Осылайша, сұрыптаудың тағы бір алгоритмін ұсынуға болады:
А) массив негізінде сұрыптау;
В) тармақты симметриялық қарап шығу әдісі жүзеге асады;
Мұндағы ең жақсы жағдайда алгоритмнің тиімділігі O(n log2n) болады.

* Тармақты кері қарай қарап шығу әдісі (төменнен жоғарыға қарай):
- сол жақ тармақтан жүріп өту;
- оң жақ тармақтан жүріп өту;
- түйінге кіру;
Осы әдіс үшін тармақты жүріп өтудің жолы:
2 0 6 5 9 8 7
өрнектің екілік тармақтарын қарап өтуде жоғарыда берілген үш әдіспен мынаны аламыз:
* Қарап шығудың тура әдісі. ¤рнектерді жазудың префиксті форматына (жоғарыдан төменге қарай) сәйкес келеді.
* Қарап шығудың симметриялық әдісі өрнектерді жазудың инфиксті форматина сәйкес келеді.
* қарап шығудың кері әдісі өрнектерді жазудың постфиксті форматына сәйкес келеді.

Екілік іздеу тармағынан элементті алып тастау.
Тармақтан элементті алып тастау алгоритмі тармақтағы осы элементтің орналасқан орнына тәуелді болады және келесі төрт жағдайды қамтиды:
* Мәні х-ке тең болатын элемент жоқ.
* Мәні х-ке тең болатын элемент терминальды түйін болып табылады.
* Мәні х-ке тең болатын элемент бір ғана ұрпақты болады.
* Мәні х-ке тең болатын элемент екі ұрпақты болады.

Бір ғана ұрпағы болатын элементті алып тастауда ешқандай күрделілік жоқ. Мұндай әрекеттер сызықтық тізімдегі элементті алып тастауға ұқсас болады.
2
3
7
0
5
6
4
9
8
3
2
0
7
5
9
4
8
6

Егер элемент екі ұрпақты болса, онда екі бағытта бір ғана сілтемемен көрсетуге келмейді. Бұл жағдайда өшірілетін элементті ауыстыруға тура келеді. Ауыстыратын элемент үшін оның сол жақтағы ең оң жаққы элемент, ал оң жақтағы ең сол жаққы элемент таңдап алынады (6 және 8 өшірілетін элементке мәндері жағынан жақын элементтер).
2
3
7
0
5
6
4
9
8

Элементі өшіру алгоритмі. Алгоритм жоғалғанда қарастырылатын 4 жағдайды қамтиды:
1-жағдай: өшірілетін түйін табылған жоқ. Яғни өшірук алгоритмі өз жұмысын тоқтатады.
2-жағдай: түйіннің ұрпақтары жоқ. Яғни жапырақ болып табылады. Бұл жағдайда ата-аналық түйінді оның бұтағы бос болатындай етіп жаңарту керек.
3-жағдай:
1. Түйіннің сол жақ ұрпағы бар, оң жақ ұрпағы жоқ. Яғни сол жақ бұтақты оның ата-анасына жалғастыру керек.
2. Түйіннің оң жақ ұрпағы бар, сол жақ ұрпағы жоқ. Яғни түйіннің оң жақ бұтағын оның ата-анасына жалғастыру керек.
4-жағдай: екі ұрпағы бар түйінді алып тастау немесе өшіру. Мұнда өшірілетін түйінді ауыстыру қажет. Ауыстыру үшін сол жақ бұтағы ең оң жақтағы түйінді таңдаймыз.

Келесілерді анықтаймыз:
D - өшірілетін түйін
P - өшірілетін элементтің ата-анасы
R - ауыстыратын түйін
PR - R түйіннің ата-анасы.

* D түйінінің сол жақ бұтағына көшеміз. Себебі, R ауыстыратын түйін өшірілетін D түйінінен кіші болады.
* R ауыстыратын түйін D түйінінің сол жақ бұтағындағы максимальды түйін болып табылады. Оң жақ бұтақ бойынша төмен жылжып, P ауыстыратын түйінді іздейміз. Жылжу барысында RR ата-аналық түйінді бақылап отырамыз. Мұнда екі мүмкін жағдай бар:
* Оң жақ бұтақ бос. R ауыстытылатын түйін өшірілетін түйіннің сол жақ баласы болып табылады. Ал PR сәйкесінше D түйініне көрсетіледі. Мұндай жағдайда келесі әрекеттерді орындаймыз:
А) D түйінінің оң жақ бұтағын R түйініне қосамыз.
Б) ¤шірілетін түйіннің P ата-анасын R түйініне қосамыз.
C
A
E
D
B
A
C
D
E

P P
D R
R PR=D
Оң жақ бұтақ оң жақ бұтақ

* Оң жақ бұтақ бос емес. Мұндай жағдайда ауыстыратын түйін жапырақтық түйін болады немесе тек қана сол жақ бұтағы бар түйін болады. Келесі әрекеттерді орындаймыз:
А) R түйінін тармақтан бөліп аламыз.
Б) R түйінінің ұрпақтарын оның ата-аналық РR түйініне жалғаймыз. (R-дің сол жақ бұтағы РR-ға оң жақ бұтақ болып жалғанады).
С) ¤шірілетін D түйіні R түйінімен ауыстырылады. Яғни D түйінінің ұрпақтары R түйінінің ұрпақтары болып жалғанады, ал R түйіні ата-аналық P түйініне жалғанады.

Зертханалық жұмыс №7
Тақырыбы:Іздеу есептерінде ағаштарды қолдану: бинарлық, кездейсоқ бинарлық, оптималды және балансталған іздеу ағаштары.

Жалпы мәлімет
Іздеу (поиск) екіге бөлінеді:
* Тізбектеліп іздеу.
* Бинарлық іздеу.

* Тізбектеліп іздеу. Тізбектеліп іздеудің мағынасы элементтерді тізбекпен таңдап алуды және элементтерді кілт мәнімен салыстырудан тұрады.

Функция парамертлер ретінде массивті, элементтер санын және кілт мәнін алады. Сәйкес элементтің индексін қайталайды, егер іздеу сәтсіз болса, -1 мәнін береді. Тізбектеліп іздеу кез келген тізбек үшін қолайлы, тізбектеліп іздеудің орталық тиімділігі O(n) тең болады.

* Бинарлық іздеу.
Бинарлық іздеулер тек қана реттелген тізімдер үшін ғана қолданылады. Мысалы элементтер тұратын массив берілсін. Тізімнің басындағы және соңындағы элементтердің индекстері мынадай low=0 high=n-1 дейін болады. Бинарлық іздеудің алгоритмі:
* Массивтің ортаңғы элементінің индексін табу: mid=(low+high)/2.
* Орталық элементтің мәнін кілтпен салыстыру <>. Егер салыстыру нәтижесінде сәйкестік бар болса, онда mid индексін кілтті табу үшін қолданамыз. Егер орталық элемент мәні кілттен кіші болса, онда қарастырылып отырған тізімнің оң жағындағы бөлігінде іздеу жүргіземіз. Егер керісінше үлкен болса, онда сол жақтағы бөлігінде іздеу жүргіземіз.
* Егер ізделіп отырған элемент тізімде жоқ болса, онда үзу индикаторын береміз.

0
1
2
3
4
5
6
7
8
-7
3
5
8
12
16
23
33
55

Low=0
High=8
mid=4
33>A(mid) 0 1 2 3 4 5 6 7 8
-7
3
5
8
12
16
23
33
55
mid

Low=5
High=8
mid=6
33>A(mid)

0 1 2 3 4 5 6 7 8
-7
3
5
8
12
16
23
33
55
mid
Low=7
High=8
mid=7
33=A(mid)

Сонда тізбектеліп іздеуде 8 салыстыру, ал бинарлық іздеуде 3 салыстыру жүргізіледі.

Зертханалық жұмыс №8
Тақырыбы:Сұрыптау есебін шешу. Ішкі және сыртқы сұрыптаулар.
Жалпы мәлімет
Қарапайым таңдау әдісімен сұрыптау келесі қадамдарға келтіріледі:
* Массивтың ең үлкен элементінің номерін орнату.
* Массивтың ең үлкен және соңғы элементтерінің орындарын ауыстыру.
* Соңғы элементті жайына қалдырып, 1 мен 2 пунктты массивтың қалғандарына (соңғы элементсіз) қайта орындау.
* 3 пунктты массивтың қалдығы бір элементке дейін қысқарғанша қайталау.

Мысалы: сұрыптау процедурасын программаларды жобалаудың тілінде (псевдокодта) сипаттаймыз.

For i := n downto 2 do
Begin
Максимальды элементті табу а[1], ..., a[i];
Оның индексын k айнымалысында сақтау;
егер i<>k болса, a[i] мен a[k] орындарын ауыстыру;
End;

Бес элементтен тұратын массивтың мәндері былайша өзгереді: (30,20,10,50,40)

30 20 10 50 40
30 20 10 40 50
30 20 10 40 50
10 20 30 40 50
10 20 30 40 50

Ең үлкен элементті іздеу аймағының асты сызылған.

Бақылау сұрақтары:

1. Массивты сұрыптау деген не?
2. Кему реті бойынша сұрыптаудың өспелі рет бойынша сұрыптаудан айырмашылығы неде?
3. Қарапайым таңдау әдісімен сұрыптау арқылы массив элементтерін сұрыптау идеясын сипатта.
4. Бір қадамды орындау уақыты массивтың реттелмеген бөлігінің өлшеміне неліктен тура пропорционал?

Тапсырмалар варианттары:

Енгізілетін мәліметтер (алғашқы массив) пен шығатын мәліметтерді (сұрыпталған массив) бүтін сандардан тұратын текстік файл ретінде қалыптастыру керек.

* Сұрыптау процедурасын сұрыптау элементтердің кему реті бойынша жүргізілетіндей етіп өзгерт.
* Бүтін сандардың берілген тізбегі кему реті бойынша сұрыпталған ба, тексер. Егер жоқ болса, ретте.
* Массивты сұрыпта, массивтегі қайталанбайтын сандардың санын есепте.
* Сұрыптау процедурасын I параметры мәні әрбір қадамда өсетіндей етіп өзгерт.
* Қарапайым таңдау әдісі көмегімен массивтың жұп элементтерін сұрыпта.
* Қарапайым таңдау әдісі көмегімен массивтың тақ орындарда тұрған элементтерін сұрыпта.
* Қарапайым таңдау әдісі көмегімен массивтың оң элементтерін сұрыпта.
* Қарапайым таңдау әдісі көмегімен массивтың теріс элементтерін сұрыпта.
* n*m матрицасында бағандарды өсу реті бойынша сұрыпта.
* Футбол командаларының тізімі және чемпионатта әрбір команда алған ұпайлар саны берілген. Ұпайлар саны бірдей командалар жоқ екендігі белгілі. Жүлдегерлерді басып шығар.
* Реттелмеген массивте қайталанатын элементтер болуы мүмкін. Бірдей элементтер тобының ішінен біреуін ғана қалдыру керек.
* Жарсытың турнирлік кестесі А квадрат матрицасы арқылы берілген. Aij әрбір элементі i командасының j командасының қақпасына соққан голдар саны. Диагональ бойымен әрбір команданың орынын орналастыру керек (жеңілістерінің санын алып тастағандағы жеңістер саны бойынша, тең түскен жағдайда соғылған гол мен жіберілген голдардың айырмасы бойынша).

Зертханалық жұмыс №9
Тақырыбы:Сұрыптау есебін шешу. Сұрыптау алгоритмдері.

Жалпы мәлімет
Алдыңғы алгоритм сияқты бұл алгоритм де жекелеген қадамдардан тұрады. Әрбір қадамда массивты басынан аяғына дейін көршілес элементтер жұптарын салыстыра отырып, жүріп өтеді. Егер кезекті жұп талап етілетін тәртіпті бұзатын болса, онда оның элементтерінің орындарын ауыстырады. Қадамдарды кезекті жүріс ешқандай ауыстыру шақырмайтындай болғанша қайталай береді.

Мысалы: 5 1 8 4 9 элементтерінен тұратын массивты қарапайым ауыстыру әдісімен өспелі түрде реттейміз. Массивтың ағымдағы бөлігінің ұзындығы n-k+i, k - қарап шығу номері, i - ізделетін жұптың номері, п - k соңғы жұптың номері.
.
Бірінші қарауда барлық массив қарастырылады.

i = l5 4 8 2 9
> ауыстырамыз
i = 24 5 8 2 9
< ауыстырмаймыз
i = 34 5 8 2 9
> ауыстырамыз
i = 44 5 2 8 9
<

9 өзінің орнында тұр.

Екінші қарау: массивты бірінші элементтен төртінші элементке дейін қарастырамыз.

i = 14 5 2 8 9
< ауыстырмаймыз
i = 24 5 2 8 9
> ауыстырамыз
i = 34 2 5 8 9
< ауыстырмаймыз

8 өзінің орнында тұр.
Үшінші қарау: массивтың қарастырылып отырған бөлігі алғашқы үш элементті қамтиды.
i = 14 2 5 8 9
> ауыстырамыз
i = 22 4 5 8 9
< ауыстырмаймыз

5 өзінің орнында тұр.

Төртінші қарау: соңғы жұпты қарастырамыз.

i = 12 4 5 8 9
< ауыстырмаймыз

4 өзінің орнында тұр.
Ең кіші элемент (2) үшін тек бірінші орын ғана қалады.
Сөйтіп, массив қарапайым ауыстыру әдісімен өсу ретімен орналастырылды. Бұл әдіс сондай-ақ, <<көпіршік әдісі>> деп аталады. Бұл атау неғұрлым <<жеңіл>> элементтер аз-аздап бетіне, жоғары жүзіп шығатын процестің бейнелік интерпретациясынан келіп шығады.

Бақылау сұрақтары:

1. Массивтың екі элементінің орынын қалай ауыстырады?
2. Кірістірілген циклдар деген не?
3. Қарапайым таңдау әдісі мен қарапайым ауыстыру әдісінің айырмашылығы қандай?

Тапсырмалар варианттары:
Енгізілетін мәліметтер (алғашқы массив) пен шығатын мәліметтерді (сұрыпталған массив) бүтін сандардан тұратын текстік файл ретінде қалыптастыру керек.
Барлық варианттарға <<көпіршік>> сұрыптау процедурасын қолдану керек.
1. Ең жақсы және ең жаман жағдайлардағы орындалған ауыстырулар мен салыстырулар санын есепте.
2. Берілген қатардың n алғашқы элементтерін өсу реті бойынша орналастыр. Осы элементтерді кему реті бойынша басып шығар.
3. Біздің мысалымызда соңғы екі элемент сұрыпталған болғандықтан элемнеттер ретіне ешқандай әсер етпейді. Сондықтан, біздің алгоритмді қандай бір жүрісте элементтер ауыстырылды ма, соны есте сақтау арқылы жақсартуға болады. Егер болмаса, сұрыптауды аяқтауға болады.

Зертханалық жұмыс №10
Тақырыбы:Сұрыптау есебін шешу. Сұрыптау алгоритмдері: таңдау арқылы сұрыптау, жылдам және таратпалы сұрыптау.

Жалпы мәлімет
Массивтерді сұрыптау алгоритмдері 4-ке бөлінеді:
* Таңдау арқылы сұрыптау.
* Ауыстыру арқылы сұрыптау (көпіршік әдіісі).
* Қою арқылы арқылы сұрыптау.
* Тез сұрыптау.

Сұрыптау немесе объектілер тізімін реттеу деп осы объектілердің қандай да бір сызықтық реттілікке қатысты өсуі мен кемуі бойынша орындауды айтамыз. Сұрыптаудың мәні сонда жазулар тізімінің реттілігін кілттік өріс мәндері кемімейтін тізбек құратындай етуіміз керек. Басқа сөзбен айтқанда R1, R2, .. , Rn жазулары кілттік мәндері K1, K2,...,Kn орналасуы керек. Ki1> сұрыптау процедурасын жазу керек.
3. Берілген қатардағы ең кіші элементтен үлкен екінші элементті табу керек.
Зертханалық жұмыс №11
Тақырыбы:Бинарлы ағаш негізінде сұрыптау. Топологиялық сұрыптау. Рекурсивті сұрыптау. Сұрыптау әдістерін салыстыру

Жалпы мәлімет
Қою арқылы сұрыптау
Қою арқылы сұрыптау - келесі процеске ұқсас. Карточкаларға аттарды жазып, карточкаларды алфавит бойынша өзіне керекті орынға қыстырып қою арқылы реттеу. Мысалға:
50,20,40,75,35 массивін қыстыру арқылы сұрыптау керек.
50 элементінен бастаймыз. 20-ны 0 позициясына қыстыру, 50-ді 1 позициясына жылжыту.
40-ты 1 позициясына қыстыру, 50-ді 2 позицияға жылжыту.
75-ті 3 позициясына қыстыру.
35-ті 1 позициясына қыстыру, қалғандарын оңға қарай жылжыту.
Есептеу күрделілігі: жалпы салыстырулар саны -ге тең. Ең жақсы жағдайда, яғни тізім реттелген жағдайда күрделілігі О(n)-ге , ал жаман жағдайда О(n2)-ге тең.

Бинарлық қоюлар арқылы сұрыптау.
Бұл жай енгізулермен сұрыптаудың жақсартылған варианты. Жаңа элементті қосуға қажетті дайын тізбек реттелген болып, енгізу орнын неғұрлым жылдам табуға негізделген. Ол үшін дайын тізбектің ортаңғы элементі ізделіп, ары қарай ортасынан бөлу қашан енгізу орыны анықталғанша жалғаса беретін бинарлық іздеу жүргізіледі.
Есептеу күрделілігі: Енгізу орыны табылады егер, al<=item<=ar болса. Соңында іздеу интервалы 1 ге тең болуы керек; бұл дегеніміз I элементтерден тұратын интервал ортасынан (log2i) рет бөлінеді деген сөз.

Салыстырулардың минимальды саны барлық элементтер кері ретпен орналасқанда, ал максимальды саны олардың осы кезде реттелген болғанында талап етіледі.

Тез сұрыптау

Тез сұрыптау әдісі - күнделікті тәжірибеден алынған.
Мысалы: Аттары бойынша алфавиттік карточкалар жиынын қандай да бір әріпке қатысты, мысалы К, екі кіші жиынға бөлуге болады. Барлық К-дан кіші немесе тең тең болатын бір жиынға, К-дан үлкен болатын бір жиынға бөлеміз. Одан кейін әрбір жиын тағы да екіге бөлінеді т.с.с. Тез сұрыптау алгоритмінде орталық элементті анықтап, сол арқылы бөлу әдісі қолданылады. Яғни, алғашқы массив екіге бөлінеді. Орталық элементтен үлкен және орталық элементтен кіші. Тура осы әрекет алынған массивтің 2 бөлігіне де жүргізіледі. Осылайша бөліне береді. Әрбір бөлікте бір ғана қалғанша жалғастырамыз.
Сұрыптау принципі:
Массивтің орталық элементі таңдап алынады. Массивтің барлық элементтері солдан оңға және оңнан солға қарай қарап өтіледі.
І. Солдан оңға қарай қозғалғанда A[scan up] деген элементті іздейміз және бұл элемент орталық элементтен үлкен болуы керек, оның позициясын есімізге сақтап аламыз. Оңнан солға қарай қозғалғанда A[scan down] деген элементті іздейміз. Ол элемент орталық элементтен кіші немесе тең болады. Позициясын есте сақтаймыз. Табылған элементтердің орындарын ауыстырамыз және scan up және scan down индекстері қиылысқанша іздеуді жалғастырамыз.
1-этапты орындап болғаннан кейін алғашқы масситің элементтері орталық элементке бөлінеді.
2-этапта 1-этаптың әрекеттері массивтің оң жақ және сол жақ бөліктері үшін жеке-жеке орындалады.
3-этапта осы әрекеттердің барлығы 4 бөлігі үшін жеке-жеке орындалады.
4-этапта 4 бөлігі жеке-жеке орындалады.
Есептеу күрделілігі. Тиімділік анализі кей жағдайда ғана мүмкін болады. Айталық, массив элементтер саны n=2 (K=log2n) 1-сканерлеуде n-1 салыстыру жүргізіледі. Оның нәтижесінің өлшемі өлшемді ішкі тізім пайда болады. Өңдеудің келесі фазасында әрбір ішкі тізім үшін n/2 салыстыру қажет болады. Осылайша, бөлу процесі табылған ішкі тізімдер тек бір ғана элементтер тұрғанша К жүрістен кейін аяқталады. Мұндағы салыстырулардың жалпы саны мына формуламен анықталады: n*k=n*log2n. Жалпы түрдегі тізім үшін есептеу күрделілігі - О(n log2n) тең болады. Ал ең нашар жағдайда орталық элемент ең кіші элемент болғанда есептеу күрделігі O(n2) тең болады.

Сұрыпталған тізбектерді біріктіру

Екі А жіне В реттелген тізімдер берілген. Оның ұзындықтары сәйкесінше m және n. Біріктіру нәтижесінде ұзындығы m және n болатын С реттелген тізімін алу қажет. әрбір элемент бойынша біріктіру жүргізіледі. Ағымдағы өткізу нүктесі әрбір тізімнің басына орналасады. Ағымдағы нүктедегі мәндер салыстырылады. Нәтижесінде солардың кішісі массивке көшіріледі. Тізбектегі мән өңделіп болғаннан кейін келесі санға бір қадам жасалады да, салыстыру жалғастырылады.
Тізімдер алғашында реттелген болғандықтан элементтер шығатын массивке сұрыпталған ретпен көшіріледі. Тізбектің біреуі аяқталғаннан кейін келесі тізбектің қалған бөліктері яғни элементтері шығтын массивке көшіріле салады.

Сұрыпталған тізбектерді біріктіру алгоритмі

Бір тізбек немесе тізбектің екеуі де біткенше келесі әрекеттерді орындау керек. Яғни, егер 1-тізбектің 1-элементі 2-тізбектің элементіне тең немесе кіші болса, онда оны шығатын тізбекке жазып қойып, 1-тізбектің келесі элементіне көшу керек. Әйтпесе, шығатын тізбекке 2-тізбектің элементін жазып, 2-тізбектің келесі элементіне көшу керек. Одан кейін шығатын тізбектің келесі элементіне көшу керек.
Егер біреуі аяғына дейін өңделмесе, онда сол қалдықты шығатын тізбекке көшіру керек.
Тапсырмалар варианттары:
Енгізілетін мәліметтер (алғашқы массив) пен шығатын мәліметтерді (сұрыпталған массив) бүтін сандардан тұратын текстік файл ретінде қалыптастыру керек.
Өткен әдістерді есептерге қолданып көр:
1. Қатардың медианасын табу керек, яғни, элементтердің бір жартысындағы кез-келгенінен үлкен және екінші жартысындағы кез-келгенінен кішкентай болатын элемент (егер қатардың элементтер саны жұп болатын болса, онда көрсетілген қасиетке ие болатын екі мәннің орташа мәнін алу керек).
2. <<Көпіршік>> сұрыптау әдісінде, егер қандай да бір екі көршілес элемент реттелмеген болса (мысалы, a[4] пен a[5]), олар ауыстырылады, одан кейін алгоритм келесі жұпты a[5] пен a[6] салыстыруға көшеді. Оның орынына a[4] элементін ғана қарап, оның қатардың жоғарғы жағына жүіп шығуына мүмкіндік беруге болады. Ол үшін a[4] пен a[3] салыстырамыз. Егер a[3] үлкен болса, ауыстыру жүргіземіз де, a[3] пен a[2] салыстырамыз. Осы көрсетілген әдісті жүзеге асыр.
3. Бүтін санды массивте бірдей элементтердің ең үлкен санын тап.
4. N бүтін сан берілген, a мен b аралығында неше сан жатыр?

4.Студенттердің өздік жұмыстар жоспары
ОСӨЖ №1

Тақырыбы: Сұрыптау есептері. Сұрыптау алгоритмдері
Мақсаты: Программа құру және оны жүктеу
Бақылау формасы: Тапсырмаларды компьютерде орындап, оқытушыға электронды түрде тапсыру
ОСӨЖ №2

Тақырыбы: Сұрыптау есептері. Қою арқылы сұраптау
Мақсаты: Программа құру және оны жүктеу
Бақылау формасы: Тапсырмаларды компьютерде орындап, оқытушыға электронды түрде тапсыру

ОСӨЖ №3

Тақырыбы: Сұрыптау есептері. Таңдау арқылы сұрыптау
Мақсаты: Программа құру және оны жүктеу
Бақылау формасы: Тапсырмаларды компьютерде орындап, оқытушыға электронды түрде тапсыру
ОСӨЖ №4

Тақырыбы: Іздеу есептерінің шешілімі. іздеу: қайтару арқылы теріп алу.
Мақсаты: Программа құру және оны жүктеу
Бақылау формасы: Тапсырмаларды компьютерде орындап, оқытушыға электронды түрде тапсыру
ОСӨЖ №5

Тақырыбы: Іздеу есептерінің шешілімі.
іздеу: тармақтар және шекаралар әдісі, динамикалық программалау, тереңге іздеу
Мақсаты: Программа құру және оны жүктеу
Бақылау формасы: Тапсырмаларды компьютерде орындап, оқытушыға электронды түрде тапсыру
ОСӨЖ №6

Тақырыбы: Жылдам іздеу: массивтен бинарлық және кезекті іздеу, М-блоктық іздеу. Сызықты тізімнен таңдау.
Мақсаты: Программа құру және оны жүктеу
Бақылау формасы: Тапсырмаларды компьютерде орындап, оқытушыға электронды түрде тапсыру
СӨЖ №1

Тақырыбы: <<Ассоциативті тізімдер>>;

Мақсаты: Тізімдер. Тізім түрлерін қарастыру.
Бақылау формасы: Электронды нұсқа, А4 форматпен реферат өткізу

СӨЖ №2

Тақырыбы: <<Тізімдерді қайта ұйымдастыру>>;
Мақсаты: Тізімдерді ұйымдастыру
Бақылау формасы: Электронды нұсқа, А4 форматпен реферат өткізу

СӨЖ №3

Тақырыбы: <<Пирамидалы сұрыптау>>;
Мақсаты: Сұрыптау есебін қарастыру
Бақылау формасы: Электронды нұсқа, А4 форматпен реферат өткізу

СӨЖ №4

Тақырыбы: <<Мекен-жайды есептеу арқылы сұрыптау>>;
Мақсаты: Сұрыптау есебін қарастыру
Бақылау формасы: Электронды нұсқа, А4 форматпен реферат өткізу

БАҚЫЛАУШЫ - ӨЛШЕМДІК ҚҰРАЛДАР

* Мәліметтерді өңдеудің құрылымдары мен алгоритмдері түсінігі.
* Статикалық және динамикалық құрылым мәліметтері.
* Мәліметтер құрылымдарымен орындалатын амалдар. Мысал.
* Алгоритмдер анализы.
* Сұрыптау және іздеу.
* Массивтерді сұрыптау алгоритмдері.
* Таңдау арқылы сұрыптау.
* Ауыстыру арқылы сұрыптау.
* Қою арқылы сұрыптау.
* Жылдам сұрыптау.
* Іздеу есептері. Тізбектелген іздеу.
* Іздеу есептері. Бинарлық іздеу.
* Файлдар. Сыртқы тасымалдаушылардағы мәліметтермен амалдар орындау. Сыртқы сұрыптау.
* Файлдар. Сыртқы тасымалдаушылардағы мәліметтермен амалдар орындау. Табиғи бірігу арқылы сұрыптау.
* Байланған сызықтық тізімдер.
* Тізімдерде іздеу әректтерін жүргізу
* Мәтіндерге тізбекті қатынау арқылы мәліметтердің сызықтық құрылымдық типтері. Бір байланысты сызықтық тізім.
* Мәтіндерге тізбекті қатынау арқылы мәліметтердің сызықтық құрылымдық типтері. Реттелген тізімді жасау.
* Мәтіндерге тізбекті қатынау арқылы мәліметтердің сызықтық құрылымдық типтері. Циклдық тізімдер.
* Мәтіндерге тізбекті қатынау арқылы мәліметтердің сызықтық құрылымдық типтері. Екі байланысты сызықтық тізім
* Мәтіндерге тізбекті қатынау арқылы мәліметтердің сызықтық құрылымдық типтері. Стектер.
* Мәтіндерге тізбекті қатынау арқылы мәліметтердің сызықтық құрылымдық типтері. Кезектер ұғымы.
* Мәтіндерге тізбекті қатынау арқылы мәліметтердің сызықтық құрылымдық типтері. Басымдықтар кезегі.
* Ағаштар. Негізгі ұғымдар.
* Ағаш тәрізді құрылымды беру әдістері.
* Екілік бинарлық ағаштар.
* Екілік ағаштардың құрылымы.
* Өрнектердің екілік ағаштары.
* Екілік іздеу ағаштары.
* Екілік ағаштармен жүргізілетін амалдар.
* Екілік іздеу тармағынан элементті алып тастау.
* Массивтермен берілген бинарлық ағаштар.
* Массивтермен берілген бинарлық ағаштар.Турнирлік сұрыптау.
* Массивтермен берілген бинарлық ағаштар. Пирамидалар түсінігі.
* Массивті пирамидаға түрлендіру.
* Пирамидаға элементтерді қосу және одан элементтерді алып тастау.
* Пирамидалық сұрыптау.
* Балансталған ағаштар.
* Графтар, олармен жүргізілетін амалдар
* Графтар. Көршілестік матрицасы.

Пәндер

Іс жүргізу
Автоматтандыру, Техника
Алғашқы әскери дайындық
Астрономия
Ауыл шаруашылығы
Банк ісі
Бизнесті бағалау
Биология
Бухгалтерлік іс
Валеология
Ветеринария
География
Геология, Геофизика, Геодезия
Дін
Ет, сүт, шарап өнімдері
Жалпы тарих
Жер кадастрі, Жылжымайтын мүлік
Журналистика
Информатика
Кеден ісі
Маркетинг
Математика, Геометрия
Медицина
Мемлекеттік басқару
Менеджмент
Мұнай, Газ
Мұрағат ісі
Мәдениеттану
ОБЖ (Основы безопасности жизнедеятельности)
Педагогика
Полиграфия
Психология
Салық
Саясаттану
Сақтандыру
Сертификаттау, стандарттау
Социология, Демография
Спорт
Статистика
Тілтану, Филология
Тарихи тұлғалар
Тау-кен ісі
Транспорт
Туризм
Физика
Философия
Халықаралық қатынастар
Химия
Экология, Қоршаған ортаны қорғау
Экономика
Экономикалық география
Электротехника
Қазақстан тарихы
Қаржы
Құрылыс
Құқық, Криминалистика
Әдебиет
Өнер, музыка
Өнеркәсіп, Өндіріс

Қазақ тілінде жазылған рефераттар, курстық жұмыстар, дипломдық жұмыстар бойынша біздің қор #1 болып табылады.

Ақпарат

Жоба жайлы

ChatGPT

Авторлық құқық

Қолдану шарты

Төлем

База сатып аламыз

Тегін

Қосымша

Мақал-мәтелдер

Жаңылтпаштар

Жұмбақтар

Пікірлер

Файл қосу

Telegram

На русском

Email: info@stud.kz

since 2008 © Stud.kz | 0.006

Іздеу
Файл қосу
Презентациялар
Тегін
Кабинет
Баланс
Таңдаулы жұмыстар
Cатып алған жұмыстарыңыз
Менің файлдарым
Презентацияларым
Сатылым статистикасы