rekursiv tuzilmalar haqida

DOCX 10 стр. 285,4 КБ Бесплатная загрузка

10 стр.

FaylHub.uz

Скачать через Telegram

Размер 285,4 КБ

Тип файла DOCX

Страницы 10

Обновлено Дек 2025

Предварительный просмотр (5 стр.)

Прокрутите вниз 👇

1 / 10

2-ma’ruza. daraxtlar grafning xususiy holati sifatida dastlab rekursiya so‘zining mazmuni haqida. bu so‘z jarayonni ifodalaydi. biron bir jarayon ro‘y berishi davomida yana shu jarayonning o‘zi ichma-ich takroriy ravishda bajarilsa, bunday jarayon rekursiv jarayon bo‘ladi. masalan, faraz qilaylik, kompyuter ekraniga uning o‘zining tasvirini chizish kerak. tasvirlangan ekranning ichida yana ekran tasviri bo‘lsin va h.k. bu jarayon rekursiv jarayondir. endi rekursiv tuzilmalar haqida. agar biron-bir ma‘lumotlar tuzilmasining har bir elementi yana xuddi shunday tuzilmadan iborat bo‘lsa, ushbu ma‘lumotlar tuzilmasi rekursiv tuzilma bo‘ladi. 4.2-rasmda misol sifatida s tuzilmadagi m1 element aynan s tuzilmaga o‘xshash, m2 elementda tashkil etuvchilar soni bitta ko‘p bo‘lsa-da, tuzilmasi s tuzilma bilan bir xil. ya‘ni, ma‘lumotlarning rekursiv tuzilmasi - bu elementlari ham aynan shu tuzilma kabi ma‘lumotlardan iborat bo‘ladi. daraxt tushunchasi. daraxtning kompyuter xotirasida tasvirlanishi daraxt - bu chiziqli bo‘lmagan bog‘lamli ma‘lumotlar tuzilmasidir. daraxtlar quyidagi belgilari bilan tavsiflanadi: · daraxtda ildiz deb ataluvchi shunday yagona element mavjudki, unga boshqa …

2 / 10

ajasi deyiladi. masalan, 4.3-rasmdagi m1 uchun shoxlanish darajasi 2, m2 uchun esa 3 ga teng. shoxlanish darajasi bo‘yicha daraxtlar quyidagi sinflarga ajratiladi: 1) agar shoxlanish darajasi m ga teng bo‘lsa, bunday daraxt m-ar daraxt deyiladi; 2) agar shoxlanish darajasi yoki 0, yoki m ga teng bo‘lsa, bunday daraxt to‘liq m-ar daraxt deyiladi; 3) agar shoxlanish darajasining maksimal qiymati 2 ga teng bo‘lsa, bunday daraxt binar (ikkilik daraxt) deyiladi; 4) agar shoxlanish darajasi yo 0 ga, yo 2 ga teng bo‘lsa, bunday daraxt to‘liq binar daraxt deyiladi. daraxt tugunlari o‘rtasidagi bog‘lanishlarni tavsiflash uchun «ota» va «bola» atamalari ishlatiladi. masalan, 4.3-rasmdagi m1 tugun a va b elementlar uchun «ota», a va b elementlar esa m1 uchun «bola» hisoblanadi. daraxtlarni tasvirlash daraxtni tasavvur qilish va elementlarini qayta ishlash algoritmlarini tahlil qilishda uning chizma shaklidan foydalanish maqsadga muvofiq (4.4-rasm). kompyuter xotirasida esa daraxtlarni bog‘lamli ro‘yxat shaklida tasvirlash ancha qulay. bu ro‘yxatning elementlari tugunning qiymati …

3 / 10

daraxtni qaraylik. uning ko‘rinishi quyidagicha bo‘lsin: binar daraxtni hosil qilish uchun xotirada tarkibi quyidagicha bo‘lgan elementlarni olish kerak (4.6-rasm): v > li key record >ht f 1 f xotirada daraxtga mos keluvchi ma'lumotlar tuzilmasini yaratish uchun maketree(key,rec) nomli protsedura ishlatilib, u xotirada ikki ko‘rsatkichga va ikki (kalit va axborot) maydonga ega bo‘lgan element (daraxt tuguni)ni hosil qiladi. maketree protsedurasining ko‘rinishi: psevdokodda: p = getnode r(p) = rec k(p) = key v = p left(p) = nil paskal tilida: new(p); pa.r := rec; pa.k := key; v := p; pa.left := nil; right(p) = nil pa.right := nil; m-ar daraxtni binar daraxtga keltirish algoritmini quyidagicha yozish mumkin: 1. daraxtning tugunlarida chap katta —bola”ga mos keluvchi shoxdan boshqa barcha shoxlar kesib tashlanadi (4.7a-rasm); 2. bir —ota”ning barcha —bola”lari gorizontal chiziqlar bilan birlashtiriladi (4.7b-rasm); 3. ushbu tuzilmadagi har bir element uchun uning ostida joylashgan element katta “bola” hisoblanadi (4.7v-rasm). a) b) v) g) …

4 / 10

ar haqidagi asosiy teorema deb ataluvchi quyidagi teorema o‘rinlidir. 1- teorema. uchlari soni va qirralari soni bo‘lgan graf uchun quyidagi tasdiqlar ekvivalentdir: 1) daraxtdir; 2) asiklikdir va ; 3) bog‘lamlidir va ; 4) bog‘lamlidir va undan istalgan qirrani olib tashlash amalini qo‘llash natijasida bog‘lamli bo‘lmagan graf hosil bo‘ladi, ya’ni ning har bir qirrasi ko‘prikdir; 5) grafninng o‘zaro ustma-ust tushmaydigan istalgan ikkita uchi faqat bitta oddiy zanjir bilan tutahtiriladi; 6) asiklik bo‘lib, uning qo‘shni bo‘lmagan ikkita uchini qirra bilan tutashtirish amalini qo‘llash natijasida faqat bitta siklga ega bo‘lgan graf hosil bo‘ladi. isboti. teoremaning 1) tasdig‘idan uning 2) tasdig‘i kelib chiqishini isbotlaymiz. graf daraxt bo‘lsin. daraxtning ta’rifiga ko‘ra, u asiklik bo‘lishini ta’kidlab, bo‘yicha matematik induksiya usulini qo‘llaymiz. matematik induksiya usulining bazasi: agar bo‘lsa, u holda daraxt faqat bitta uchdan tashkil topgan bo‘ladi. tabiiyki, agar bitta uchga ega bo‘lgan grafda sikl bo‘lmasa, u holda unda birorta ham qirra yo‘q, ya’ni . demak, bu …

5 / 10

hi kelib chiqadi. demak, bo‘lganda ham tenglik o‘rinlidir. bu esa, matematik induksiya usuliga ko‘ra, kerakli tasdiqning isbotlanganligini anglatadi. endi daraxtlar haqidagi asosiy teoremaning 2) tasdig‘idan uning 3) tasdig‘i kelib chiqishini isbotlaymiz. graf asiklik, ya’ni u siklga ega bo‘lmagan graf va bo‘lsin. grafning bog‘lamli bo‘lishini isbotlash kerak. agar graf bog‘lamli bo‘lmasa, u holda uni har bir bog‘lamli komponentasi siklsiz graf (ya’ni, daraxt) bo‘lgan qandaydir ta () graflar diz’yunktiv birlashmasi sifatida tenglik bilan ifodalash mumkin. har bir uchun graf daraxt bo‘lgani uchun, yuqorida isbotlagan tasdiqqa ko‘ra, agar unda ta uch va ta qirra bo‘lsa, u holda asiklikdir va tenglik o‘rinlidir. tushunarliki, va . demak, , ya’ni graf uchlarining umumiy soni undagi qirralar umumiy sonidan ta ortiqdir. bu esa, bo‘lgani uchun, tenglikka ziddir. zarur tasdiq isbotlandi. teoremaning 3) tasdig‘idan uning 4) tasdig‘i kelib chiqishini isbotlaymiz. – bog‘lamli graf va bo‘lsin. avvalo ta bog‘lamlilik komponentalariga ega karrali qirralari bo‘lmagan sirtmoqsiz -graf uchun munosabat o‘rinli …

Хотите читать дальше?

Скачайте все 10 страниц бесплатно через Telegram.

Скачать полный файл

О "rekursiv tuzilmalar haqida"

2-ma’ruza. daraxtlar grafning xususiy holati sifatida dastlab rekursiya so‘zining mazmuni haqida. bu so‘z jarayonni ifodalaydi. biron bir jarayon ro‘y berishi davomida yana shu jarayonning o‘zi ichma-ich takroriy ravishda bajarilsa, bunday jarayon rekursiv jarayon bo‘ladi. masalan, faraz qilaylik, kompyuter ekraniga uning o‘zining tasvirini chizish kerak. tasvirlangan ekranning ichida yana ekran tasviri bo‘lsin va h.k. bu jarayon rekursiv jarayondir. endi rekursiv tuzilmalar haqida. agar biron-bir ma‘lumotlar tuzilmasining har bir elementi yana xuddi shunday tuzilmadan iborat bo‘lsa, ushbu ma‘lumotlar tuzilmasi rekursiv tuzilma bo‘ladi. 4.2-rasmda misol sifatida s tuzilmadagi m1 element aynan s tuzilmaga o‘xshash, m2 elementda tashkil etuvchilar soni bitta ko‘p bo‘lsa-da, tuzilmasi s tuzil...

Этот файл содержит 10 стр. в формате DOCX (285,4 КБ). Чтобы скачать "rekursiv tuzilmalar haqida", нажмите кнопку Telegram слева.

Теги: rekursiv tuzilmalar haqida DOCX 10 стр. Бесплатная загрузка Telegram