ДӘРІСТЕР

АЗАҚ СТАН РЕСПУБЛИКАСЫНЫҢ БIЛIМ ЖӘ НЕ Ғ ЫЛЫМ МИНИСТРЛIГI

СЕМЕЙ қ аласының ШӘ КӘ РIМ атындағ ы МЕМЛЕКЕТТIК УНИВЕРСИТЕТI

«Іріктеу жә не іздеу ә дістері» пә нінің

5В070400-

«Есептеу техникасы жә не бағ дарламалық қ амсыздандыру» мамандығ ына арналғ ан

ОҚ У-Ә ДІСТЕМЕЛІК КЕШЕН

Семей

МАЗМҰ НЫ

1 ГЛОССАРИЙ

2 ДӘ РІСТЕР

3 ПРАКТИКАЛЫҚ САБАҚ ТАР

4 СӨ Ж ЖӘ НЕ СОӨ Ж

ГЛОССАРИЙ

1.1 Іріктеу – «анық талғ ан реті» бойынша элементтерді орналастыру процессі.

1.2 Басқ алардан ертерек адамдармен танылатын ә діс, оның қ арапайымдылығ ының арқ асында, кө піршік сұ рыптауы деп аталады (bubble sort), бұ л ә дісте келесі амалдар жү ргізіледі: берілген ретті бұ затын кө рші элементтерді орындармен ауыстыру. Бұ л процесс толық файл сұ рыпталғ ан жағ дайда ғ ана аяқ талады.

1.3 Гномдардың сұ рыптауы (ағ ылш. Gnome sort) — қ осулары бар сұ рыптауғ а ұ қ сағ ан алгоритм, бірақ керекті орынғ а элемент кө піршік ә дісі бойынша орналастырылады.

1.4 Табиғ и іріктеу (ағ ылш. Natural sort) — қ осуы бар сұ рыптаудың қ арапайым жә не тиімді модификациясы, мұ нда элементтер сұ рыпталып қ ойғ ан болуы мү мкін.

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

1.6 Кілт - файлды іріктеу ережелерінде қ олданылатын шаманы сақ тайтын ө ріс.

1.7 Жұ птасқ ан алмастыру ә дісі жұ п жә не тақ қ арастырулардың ә ртү рлі сандардан тұ рады.

1.8 Тез сұ рыптау – ә дістің тиімділігіне ә сер ететін критикалық мә нді алуғ а арналғ ан ә ртү рлі тә сілдердің алгоритмдерінің жалпы аталуы.

1.9 Кірістік рекурсия - егер процедурада рекурсивті шақ ыру соң ғ ы болмаса, онда мұ ндай рекурсия кірістік деп аталады.

1.10 Рекурсияның терең дігі – бағ дарламаның жұ мыс барысында компьютердің жадысында сақ талатын бастапқ ы процедураның аяқ талмағ ан копияларының саны.

1.11 Массив – бір типті деректердің жиыны, ә р элементтің ө з индексі болады.

1.12 Массивтерді қ осу – А массивті В массивына қ осқ анда С массиві пайда болады, яғ ни C[i]=A[i]+B[i]. Алу аналогтық тү рде ұ йымдастырылады.

1.13 Сыртқ ы сұ рыптау – сыртқ ы сақ тау қ ұ ралдарында орналасқ ан деректерді сұ рыптау.

1.14 Ішкі сұ рыптау – компьютердің оперативті жадында орналасқ ан деректерді сұ рыптау.

ДӘ РІСТЕР

Дә ріс № 1. Кіріспе. Іріктеу ә дістері.

Дә рістің мақ саты – іріктеу жә не іздеу ә дістерінің негізгі ұ ғ ымдарымен таныстыру, пә ннің негізгі терминдерімен таныстыру.

Ағ аштармен байланысты ұ ғ ымдар кең таралғ ан жә не интуитивті тү сінікті. Ағ аштың бірнеше мү мкін анық тамалары бар.

Мысалы, графтар кө зқ арасы жағ ынан, ағ аш деп жиі жағ дайда бағ ытталмағ ан ұ шы белгіленген, циклдары болмайтын, графты атайды. Бізді тек бағ ытталғ ан ағ аштар қ ызық тыратын болады, бағ дарламаушылар кө зқ арастары жағ ынан. Сондық тан біз келесі рекурсивті анық тамамен қ олданамыз: Т базалық типті R ағ ашы – бұ л немесе (a) бос ағ аш (бір де бір ұ шы жоқ), немесе (b) T типті кейбір ұ ш (ағ аштың тү бі) соң ғ ы (мү мкін, нө льдік) Т базалық ағ аштармен байланысқ ан санмен (Бұ л ағ аштар R ағ ашының ішіндегі ағ аштар деп аталады). Бұ л анық тамадан келесіні тү сінуге болады, біржақ ты бағ ытталғ ан тізім ағ аш болып аталады. Сур. 1.

Рис. 1

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

сур. 2

Ағ аштардың ішіндегі ағ аштардың байланыстарын бұ таұ тар деп атаймыз, ал ә р ағ аштың тү бін ұ шы деп атаймыз. Реттелген деп бұ тақ тары реттелген ағ аштарды атаймыз. Мысалыр, 3 суретте екі реттелген ағ аштар айырылады.

Рис.3

Ұ штар саны немесе бұ тақ тар саны x ұ шына жолы деп аталады. Биіетігі немесе терең дігі деп ұ штың максималды ұ зындығ ын атаймыз.

№1 дә рісіне бақ ылау сұ рақ тары

1. «Іріктеу жә не іздеу ә дістері» пә нінің мақ саттары.

2. Ағ аштардың мү мкін болатын анық тамаларын атаң ыз.

3. Граф деген не?

4. Ұ шқ а апаратын жолдың ұ зындығ ы деген не?