Қазақстан республикасының бiлiм және ғылым министрлiгi

жүктеу/скачать 1,23 Mb.

бет	1/5
Дата	31.07.2017
өлшемі	1,23 Mb.
	#22426

1 2 3 4 5

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

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

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

5В070400-

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

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

Семей

2014
МАЗМҰНЫ

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 Ішкі сұрыптау – компьютердің оперативті жадында орналасқан деректерді сұрыптау.

2 ДӘРІСТЕР
Дәріс № 1. Кіріспе. Іріктеу әдістері.
Дәрістің мақсаты – іріктеу және іздеу әдістерінің негізгі ұғымдарымен таныстыру, пәннің негізгі терминдерімен таныстыру.

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

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

Рис. 1

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

сур. 2

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

Рис.3

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

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

«Іріктеу және іздеу әдістері» пәнінің мақсаттары.
Ағаштардың мүмкін болатын анықтамаларын атаңыз.
Граф деген не?
Ұшқа апаратын жолдың ұзындығы деген не?

Дәріс № 2. «Көпіршік» әдісі.

Дәрістің мақсаты- студенттерді сұрыптаудың ең қарапайым түрімен таныстыру, сұрыптау алгоритмінің спецификасымен таныстыру.

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

n элементтер бар дейік, олар а₁ а₂, а₃, . . ., а_n, массив ұяшаларында орналасқан. Ыңғайлылық үшін элементпен кілт бір мәнге ие дейік. Алгоритм n-1 қадамдардың қайталануларынан тұрады, оның әрқайсысында қалған өндірілмеген жиында жұптасқан көрші элементтерді салыстырулары арқылы минималды элемент табылады.

Қадам 1. а_n –ді а_n_-1– мен салыстырамыз, және егер а_n < а_n_-1 онда оларды орындарымен ауыстырамыз, содан кейін а_n_-1 және а_n_-2салыстырамыз, мүмкін, олардың да орындарын ауыстырамыз, а_n_-2 және а_n_-3 және ары қарай жалғастыра береміз, а₂ және а₁ элементтеріне келгенше. Нәтижесінде бірінші орында ең минималды элемент тұрады , ол содан кейін сұрыптау процессіне қактыспайды

Қадам 2. Аналогты түрде а_n және а_n-1, а_n-1 және а_n-2 және...., а₃және а₂, нәтиже ретінде а₂ элементінің орнына екінші минималды элемент тұрады, ол а₁ элементімен бірге реттелген массивтің бастапқы бөлігін құрады.

Қадам 3.Ұқсас салыстырулар мен орын ауыстырулармен а₃, а₄, … , а_n элементтерінің арасында а₃ эелементінің орнына ең кіші элемент

. . . . .

Қадам n-1. Бұл сәтке дейін бірінші n-2 элементтер массивте реттелген болып тұрады, содан кейін тек екі а_n-1және а_nарасында рет қою керек болады. Осы кезеңде сұрыптау процессі аяқталады.

Мысалы. 6 элемент берілген болсын –15, 33, 42, 07, 12, 19 бүтін сандар.

	а₁	а₂	а₃	а₄	а₅	а₆	Орындалатын операциялар
қадам1	15	33	42	07	12	19	салыстыру 19 және 12, ауыстыру жоқ
	15	33	42	07	12	19	салыстыру 12 және 07, ауыстыру жоқ
	15	33	07	42	12	19	салыстыру 07 және 42, орындарын ауыстырамыз
	15	07	33	42	12	19	салыстыру 07 және 33, орындарын ауыстырамыз
	07	15	33	42	12	19	салыстыру 07 және 15, орындарын ауыстырамыз; 07 – минималды
қадам 2	07	15	33	42	12	19	салыстыру 19 және 12, ауыстыру жоқ
	07	15	33	12	42	19	салыстыру 12 және 42, орындарын ауыстырамыз
	07	15	12	33	42	19	салыстыру 12 және 33, орындарын ауыстырамыз
	07	12	15	33	42	19	салыстыру 12 және 15, орындарын ауыстырамыз, 12 –екінші минималды.
қадам3	07	12	15	33	19	42	салыстыру 19 және 42, орындарын ауыстырамыз
	07	12	15	19	33	42	салыстыру 19 және 33, орындарын ауыстырамыз
	07	12	15	19	33	42	салыстыру 19 және 15, ауыстыру жоқ, 15 – үшінші минималды.
қадам4	07	12	15	19	33	42	салыстыру 42 және 33, ауыстыру жоқ
қадам4	07	12	15	19	33	42	салыстыру 33 және 19, ауыстыру жоқ, 19 – төртінші элемент.
қадам 5	07	12	15	19	33	42	салыстыру 42 және 33, ауыстыру жоқ, сұрыптау аяқталды
	07	12	15	19	33	42

жүктеу/скачать 1,23 Mb.

Достарыңызбен бөлісу:

1 2 3 4 5