R va maf” fakulteti 812-21- guruh ca

1-teorema. Uchlari soni m va qirralari soni n bo 'Igan G graf uchun quyidagi tasdiqlar ekvivalentdir:
G daraxtdir;
G asiklikdir va n=m—l;
G bog'lamlidir va n=m—\;
Algoritm termini o’rta asrlar ulug’ matematigi al-Xorazmiy nomidan kelib chiqqan. XX asrning 30-yiligacha algoritm tushunchasi ko’proq matematik ma’no emas, balki metodologik ma’noni kasb etar edi. Algoritm deganda, u yoki bu masalalar sinfini yechish imkonini beruvchi aniq ifodalangan chekli qoidalar majmui tushunilgan. EHM larning paydo bo’lishi bilan algoritm tushunchasi yanada keng tarqaldi. EHM va dasturlash usullarining rivojlanishi algoritmlarni ishlab chiqish avtomatlashtirishdagi zaruriy bosqich ekanligini tushunishga yordam berdi. EHM larning paydo bo’lishi algoritmlar nazariyasining rivojlanishiga olib keldi. Algoritmlarni tuzish – bu ijodiy ish bo’lib, ixtiyoriy zaruriy algoritmni tuzish uchun umumiy usullar mavjud emas, kishining ijodiy qobiliyatiga bog’liq
Algoritm tushunchasi zamonaviy matematika va informatikaning asosiy tushunchalaridan biri hisoblanadi. Algoritm termini o’rta asrlar ulug’ matematigi al-Xorazmiy nomidan kelib chiqqan. XX asrning 30-yiligacha algoritm tushunchasi ko’proq matematik ma’no emas, balki metodologik ma’noni kasb etar edi. Algoritm deganda, u yoki bu masalalar sinfini yechish imkonini beruvchi aniq ifodalangan chekli qoidalar majmui tushunilgan. EHM larning paydo bo’lishi bilan algoritm tushunchasi yanada keng tarqaldi.
EHM va dasturlash usullarining rivojlanishi algoritmlarni ishlab chiqish avtomatlashtirishdagi zaruriy bosqich ekanligini tushunishga yordam berdi. EHM larning paydo bo’lishi algoritmlar nazariyasining rivojlanishiga olib keldi.
Algoritmlarni tuzish – bu ijodiy ish bo’lib, ixtiyoriy zaruriy algoritmni tuzish uchun umumiy usullar mavjud emas, kishining ijodiy qobiliyatiga bog’liq.Albatta, algoritmni aniq sxema bo’yicha tuzish zarur bo’lib qoladigan sodda hollar ham mavjud. Bunday hollarda yechilish algoritmiavval biron kim tomonidan olingan masalalarni misol keltirish mumkin. Masalan, differensial tenglamalarni sonli integrallash uchun Eyler metodi. Bu metod masalani yechish uchun umumiy holda ifodalangan algoritmdir, lekin algoritmlash ijodiy ekanligini quyidagi algoritmlar nazariyasining ba’zi bir ma’lumotlaridan ko’rish mumkin.
Agar bizdan biror algoritmni ishlab chiqish talab qilinsa, dastlab izlanayotgan algoritmni tuzish mumkinmi yo’qmi degan savolga javob izlash kerak. Chunki ba’zi hollarda algoritmni tuzish mumkin emasligini ko’rsatib berish mumkin. Ba’zi bir hollarda algoritmni tuzish mumkinligi isbotlanadi. Bunday isbot mavjud bo’lganligi bilan tuzilgan algoritmni amalgam oshirib bo’lmaydi yoki uning samaradorligi talabga javob bermaydi. Shunga qaramasdan bir nechta algoritmlar bitta amaliyotga
qo’llanilayotganini topish mumkin.Albatta, algoritmni aniq sxema bo’yicha tuzish zarur bo’lib qoladigan sodda hollar ham mavjud. Bunday hollarda yechilish algoritmiavval biron kim tomonidan olingan masalalarni misol keltirish mumkin.
Masalan, differensial tenglamalarni sonli integrallash uchun Eyler metodi. Bu metod masalani yechish uchun umumiy holda ifodalangan algoritmdir, lekin algoritmlash ijodiy ekanligini quyidagi algoritmlar nazariyasining ba’zi bir ma’lumotlaridan ko’rish mumkin. Agar bizdan biror algoritmni ishlab chiqish talab qilinsa, dastlab izlanayotgan algoritmni tuzish mumkinmi yo’qmi degan savolga javob izlash kerak. Chunki ba’zi hollarda algoritmni tuzish mumkin emasligini ko’rsatib berish mumkin. Ba’zi bir hollarda algoritmni tuzish mumkinligi isbotlanadi. Bunday isbot mavjud bo’lganligi bilan tuzilgan algoritmni amalgam oshirib bo’lmaydi yoki uning samaradorligi talabga javob bermaydi. Shunga qaramasdan bir nechta algoritmlar bitta amaliyotga qo’llanilayotganini topish mumkin.Algoritmlarning turli ta’riflari mavjud.
Rasmiy ta’riflardan biri bo’yicha algoritm bu qo’yilgan masalani bir xil yechilishiga olib keluvchi aniq harakatlarning ketma-ketligi. Bu tushunchadan algoritmning quyidagi xossalari kelib chiqadi:Algoritmlarning turli ta’riflari mavjud. Rasmiy ta’riflardan biri bo’yicha algoritm bu qo’yilgan masalani bir xil yechilishiga olib keluvchi aniq harakatlarning ketma-ketligi. Bu tushunchadan algoritmning quyidagi xossalari kelib chiqadi:Diskretlilik – ya’ni aniqlanayotgan jarayonni qadamba-qadam ko’rinishi. Ommaviylik – algoritm o’xshash masalalar turkumini yechishi kerak. Tushunarlilik – algoritmda beriladigan ko’rsatmalar foydalanuvchiga tushunarli bo’lib, uning talablariga javob berishi kerak. Aniqlilik – algoritmda ma’lum tartibda amallarni bajarish nazarda tutilishi kerak va bajaruvchiga joriy qadam tugatilishi bilan qaysi qadam keyingi bo’lib bajarilishi aniq ko’rsatilishi kerak.
Har qanday matematik nazariya u yoki bu matematik jumlaning rost yoki yolg’onligini o’rganadi.
Ta’rif: Rost yoki yolg’onligi bir qiymatli aniqlangan darak gapga jumla (mulohaza) deyiladi.
Ta’rifga ko’ra “0<1”, “2*5=10”, “7 – juft son”, “1 – tub son” gaplar mulohaza bo’lib, ulardan birinchisi va ikkinchisi rost, uchinchisi va to’rtinchisi yolg’on mulohazalardir.
Mulohazalar nazariyasining boshlang’ich ob’yektlari sodda (oddiy) mulohazalardan iborat. Sodda mulohazalar lotin alifbosining katta harflari A, B, C, …. yoki kichik harflari a, b, c,.... orqali belgilanadi. Mulohazalarning rost yoki yolg’onligi ularning mazmuniga qarab aniqlanadi. Rost mulohazalarning qiymati 1, yolg’onligi mulohazalarning qiymati 0 orqali belgilanadi. Mulohaza bir vaqtning o’zida ham rost, ham yolg’on bo’la olmaydi.
Matematikada har bir teorema mulohaza hisoblanadi.
Sodda mulohazalardan bog’lovchi yoki bog’lovchi so’zlar orqali murakkab mulohazalar hosil qilinadi.
“emas”, “va”, “yoki”, “... kelib chiqadi”, “zarur va yetarli” kabi bog’lovchi so’zlarga bittadan mantiqiy amal mos keladi.
Mulohazalar ustida bajariladigan inkor, kon’yuksiya, dizyunksiya, implikatsiya, ekvivalensiya amallari mavjud.
Mulohazalar hisobining simvollari. Har qanday hisobning tafsifi buhisobning simvollari tafsifidan, formulalar va keltirib chiqarish formulalari ta‟rifidan iborat..
Mulohazalar hisobida uch kategoriyali simvollardan iborat alifbo qabul qilinadi.Birinchi kategoriya simvollari:x, y,z,..., x1, x2 . Bu simvollarni o„zgaruvchilar deb ataymiz.Ikkinchi kategoriya simvollari:. Bular mantiqiy bog‘lovchilardir. Birinchisi – diz‟yunksiya yoki mantiqiy qo„shish belgisi, ikkinchisi – kon‟yunksiya yoki mantiqiy ko„paytma belgisi, uchinchisi – implikasiya belgisi va to„rtinchisi – inkor belgisi deb ataladi.Uchinchi kategoriyaga qavslar deb ataladigan ( , ) simvollar kiritiladi Mulohazalar hisobida boshqa simvollar yo„q.Mulohazalar hisobi formulasi tushunchasi. Mulohazalar hisobining formulasi deb mulohazalar hisobi alifbosi simvollarining muayyan ketmaketligiga aytiladi.Formulalarni belgilash uchun lotin alifbosining bosh harflaridan foydalanamiz. Bu harflar mulohazalar hisobining simvollari qatoriga kirmaydi. Ular faqatgina formulalarning shartli belgilari bo„lib xizmat qiladi.
Endi mulohazalar hisobi formulasi tushunchasi ta‟rifini keltiramiz.
t a ’ r i f. Mulohazalar hisobi formulasi tushunchasi quyidagicha aniqlanadi:
1) har qanday x, y,z,...o‘zgaruvchilarning istalgan biri formuladir;
2) agar A va B ning har biri formula bo‘lsa, u holda (A B), (A B), (A B) va A ham formuladir.
3) boshqa hech qanday simvollar satri formula bo‘la olmaydi.
O‘zgaruvchilarni elementar formulalar deb ataymiz.
Algoritmlarning ko'rinishi matematika paydo bo'lishi bilan bog'liq. Xorazm Abdulloh shahridan (yoki Abu Ja'far) bo'lgan bir olim Muhammad ibn Musoul Al-Xorazmi ko'p kitob yaratdi, bu esa ko'p qirrali raqamlar bo'yicha arifmetik ta'sirni amalga oshirishni tasvirlab bergan matematika bo'yicha kitob yaratdi. "Algoritm" so'zi Evropada ushbu Markaziy Osiyo matematika kitoblarini lotin tiliga topshirgandan so'ng, uning nomi "algoritm" deb yozilgan.
Algoritm - boshlash (rejasi) ketma-ketligining tavsifi, uning qat'iy ijrosi qadamlarning yakuniy soniga olib keladi.
Algoritmlashtirish - muammoni hal qilish uchun algoritm (tizmani rivojlantirish) jarayoni.
Algoritmlar misollari:
Do'konda sotib olingan har qanday uni ishlab chiqarish bo'yicha ko' bilan ta'minlangan.
Har bir shov-shuvli yo'l qoidalarini bilishi kerak.
Avtomobillarning amalga oshirish ishlab chiqarish faqat konveyerga avtomobilni yig'ish tartibi ixtiro qilingan.