16-dars: Isbot — invariant va almashish

2-darajaKumush — usullar9–16 darslar

HayotdaShifoxona

Registraturada ikki bemor turibdi: biriga besh daqiqa, ikkinchisiga yarim soat kerak. Hamshira qisqasini oldin kiritadi va buni hech kim so’ramaydi — hamma buni «shunchaki to’g’ri» deb biladi. Savol shu: qayerdan bilamiz?

Bu darsdan keyin siz

• ochko’z algoritm uchun almashish argumentini yozasiz
• invariant nima ekanini ayta olasiz va uni sikl ustida topasiz
• «testda ishladi» bilan «isbotlandi» ni ajratasiz

Avval qo’lda

Avval qo‘lda

~5 daqiqa·juftlikda·Qog'oz va qalam

Sinfdoshingiz ro’yxatdagi eng katta sonni topadigan algoritmni qadamma-qadam bajarsin. Siz esa har qadamdan keyin bitta gap yozing: «hozir eng o’zgaruvchisi ko’rilgan qismdagi eng katta songa teng».

Bu gap har qadamdan keyin rost bo’lib qolyaptimi? Endi shu gapni algoritm oxirida ayting: nima kelib chiqadi?

Nimani sezishingiz kerak

Gap sikl oxirida ham rost, ko’rilgan qism esa butun ro’yxatga aylangan. Demak eng — butun ro’yxatning maksimumi. Siz hozirgina algoritmni isbotladingiz, sinamadingiz.

Kompyuter yopiq. Bu mashq tugamaguncha kod ochilmaydi.

Ikkita asbob

invariantloop invariant

Sikl har aylanishidan keyin ham rost bo’lib qoladigan gap. Sikl tugagach u ham rost bo’ladi — natija shu yerdan chiqariladi.

almashish argumentiexchange argument

Optimal javobni olib, uni ochko’z javobga bir qadam yaqinlashtirish usuli. Har almashtirish javobni yomonlashtirmasa, ochko’z javob ham optimal bo’ladi.

Invariant sikl bilan yozilgan algoritmlar uchun, almashish argumenti esa ochko’z tanlovlar uchun ishlatiladi. Ikkalasining maqsadi bir xil: testsiz ishonch hosil qilish.

Almashish argumenti: navbat tartibi

Shifokorga uch bemor kelgan: 8, 5 va 6 daqiqa. Har bemorning chiqish vaqti — o’zigacha bo’lgan hamma vaqt plus o’zi. Bizga shu vaqtlar yig’indisi eng kichik bo’lgan tartib kerak.

To’liq izlash barcha tartiblarni ko’radi va aniq javob beradi.

?Avval o'ylang: bu kod nima chiqaradi? Ishga tushirishdan oldin yozing.

Bashorat qilingNusxalash

1from itertools import permutations2vaqtlar = [8, 5, 6]3def jami(tartib):4  soat = 05  natija = 06  for t in tartib:7      soat += t8      natija += soat9  return natija10print(min(jami(p) for p in permutations(vaqtlar)), jami(sorted(vaqtlar)))

Sizning bashoratingizTekshirish

Javobni ko'rish

35 35

Barcha tartiblardan eng yaxshisi 35, saralangan tartib ham 35. Bu tasodifmi yoki qonuniyat — testning o'zi ayta olmaydi.

Endi buni isbotlaymiz. Optimal tartibda yonma-yon turgan ikki bemorni olaylik: avval a daqiqalik, keyin b. Ulardan oldingi hammasi S daqiqa olgan bo’lsin.

?Avval o'ylang: bu kod nima chiqaradi? Ishga tushirishdan oldin yozing.

Bashorat qilingNusxalash

1S = 42a, b = 3, 73print((S + a) + (S + a + b), (S + b) + (S + b + a))

Sizning bashoratingizTekshirish

Javobni ko'rish

21 25

Chapdagi — a oldinda turgan holat, o'ngdagi — b oldinda. Farq faqat bitta joyda: qaysi biri IKKI marta qo'shiladi. Kichigi oldinda tursa yig'indi kichik.

Umumiy holda ikki hissa 2S + 2a + b va 2S + 2b + a bo’ladi. Ularning farqi a − b: demak a < b bo’lsa birinchi variant qat’iy kichik.

◆Asosiy g'oya

Xulosa: optimal tartibda hech qanday juftlikda uzunroq bemor qisqarog’idan oldin tura olmaydi — aks holda uni almashtirib javobni yaxshilash mumkin bo’lardi. Bu esa aynan saralangan tartib. Isbot tugadi va u hech qanday testga tayanmaydi.

Invariant: nega ikkilik qidiruv to’g’ri

Ikkilik qidiruvning invarianti bir gapda yoziladi: «javob har doim chap va ong orasida».

Boshida bu rost, chunki oraliq butun maydonni qamraydi. Har qadamda ham rost bo’lib qoladi: biz faqat javob bo’la olmaydigan yarmini tashlaymiz. Sikl chap == ong bo’lganda tugaydi — demak o’sha nuqta javob.

Shu bitta gap ikkita narsani beradi. Birinchisi — to’g’rilik. Ikkinchisi — to’xtash kafolati: oraliq har qadamda qat’iy kichrayadi, ya’ni sikl abadiy aylanmaydi (7-darsdagi tuzoq aynan shu talab buzilganda paydo bo’lgan edi).

Endi 14-darsga qaytamiz

Intervallar masalasida biz tugash vaqti bo’yicha saralagan edik va «nega» degan savolni 16-darsga qoldirgan edik. Javob — almashish argumenti.

Optimal yechimni oling. Undagi birinchi interval X bo’lsin, ochko’z tanlagani esa G — eng erta tugaydigani. G ning tugashi X nikidan katta emas, demak X ni G ga almashtirsak, qolgan intervallarga kamroq xalaqit beradi va yechim buzilmaydi.

Shu almashtirishni takrorlab, optimal yechimni ochko’z yechimga bosqichma-bosqich aylantirish mumkin. Uzunligi esa hech qachon kamaymaydi — demak ochko’z yechim ham optimal.

Sinab ko’r

Vizualda yonma-yon juftlik almashtiriladi va yig’indi qanday o’zgarishi ko’rinadi. Farq har safar aynan ikki vaqtning ayirmasiga teng.

Almashish argumenti — nega saralash optimal

Yonma-yon juftlikni almashtiring: yig'indi kamaysa, eski tartib optimal emas edi.

Yonma-yon turgan uzunroq va qisqaroq bemor almashtirilsa, umumiy kutish vaqti kamayadi.

Algoritmning har qadami quyidagi ro‘yxatda matn sifatida ham berilgan — vizual faqat shu qadamlarni chizadi, yangi ma’lumot qo‘shmaydi.

1. Uch bemor: 8, 5 va 6 daqiqa. Har bemorning chiqish vaqti — o'zigacha bo'lgan hamma vaqt plus o'zi. Bizga shu vaqtlar yig'indisi kerak.
2. 8 va 5 yonma-yon turibdi, uzunrog'i oldinda. Almashtirib ko'ramiz.
3. Yig'indi 40 dan 37 ga tushdi. Farq — aynan 3, ya'ni ikki vaqtning ayirmasi.
4. 8 va 6 yonma-yon turibdi, uzunrog'i oldinda. Almashtirib ko'ramiz.
5. Yig'indi 37 dan 35 ga tushdi. Farq — aynan 2, ya'ni ikki vaqtning ayirmasi.
6. Endi hech bir juftlikda uzunroq bemor qisqarog'idan oldin turmaydi — bu esa aynan saralangan tartib. Demak saralash optimal: buni sinab emas, ISBOTLAB bildik.

navbat

min80min51min62

chiqish vaqti

81319

yig'indi

jami40

Uch bemor: 8, 5 va 6 daqiqa. Har bemorning chiqish vaqti — o'zigacha bo'lgan hamma vaqt plus o'zi. Bizga shu vaqtlar yig'indisi kerak.

Almashtirish0

OrqagaO‘ynatishOldinga1/6Qayta boshlash

Xatoni toping

▲Tuzoq — xatoni toping

16 / 40

MasalaTanga qaytarishda ochko'zlik (eng kattadan boshlash) optimalmi?

Taklif qilingan isbot

1. 1Optimal yechimni olamiz va uni ochko‘z yechim bilan solishtiramiz.
2. 2Optimal yechimda eng katta tanga ishlatilmagan bo‘lsin.
3. 3U holda o‘sha tangani qo‘shib, kichiklaridan bir nechtasini olib tashlash mumkin — tanga soni kamayadi.
4. 4Demak optimal yechimda ham eng katta tanga bor, ya‘ni ochko‘zlik to‘g‘ri.

Bu javobning 3-qismi noto'g'ri. «Kichiklaridan bir nechtasini olib tashlash mumkin» — bu ASOSLANMAGAN. U faqat kichik tangalar katta tangaga to'liq yig'iladigan tizimlarda o'rinli. 1, 3, 4 tizimida 6 uchun bu bajarilmaydi: 4 ni qo'shsangiz qolgan 2 ni faqat ikkita birlik bilan yopasiz va tanga soni ortadi.

Javobning qaysi qismi noto'g'ri? Bosib belgilang.

Javobni ko'rsatish

O’zingizni sinang

1Invariant nima?

Javobni ko'rish

Sikl har aylanishidan keyin ham rost bo’lib qoladigan gap. Sikl tugagach ham rost bo’lgani uchun undan natija chiqariladi.

2Almashish argumentining sxemasi qanday?

Javobni ko'rish

Optimal yechimni oling, undagi bitta tanlovni ochko’z tanlovga almashtiring va yechim yomonlashmasligini ko’rsating. Takrorlab, optimalni ochko’zga aylantiring.

3Navbat masalasida nega qisqa bemor oldin turadi?

Javobni ko'rish

Yonma-yon ikki bemorning hissasi 2S + 2a + b va 2S + 2b + a. Farqi a − b, demak kichigi oldinda turganda yig’indi kichik bo’ladi.

4Ikkilik qidiruvning invarianti nima va u nimani kafolatlaydi?

Javobni ko'rish

«Javob chap va ong orasida». U ikki narsani beradi: javobning to’g’riligini va oraliq har qadamda kichrayganligi uchun siklning to’xtashini.

5Stress-test isbotning o'rnini bosa oladimi?

Javobni ko'rish

Yo’q. Stress-test xatoning borligini ko’rsatadi, isbot esa yo’qligini. Ikkalasi birga ishlatiladi: avval mulohaza, keyin tekshiruv.

Masalalar

Masalalar

3 ta

• Tasks and DeadlinesCSES 1630o'rta

  Darsdagi masalaning haqiqiy o‘lchamdagi varianti. Isbot o‘sha-o‘sha.

• Stick LengthsCSES 1074o'rta

  Tanlangan nuqtani bir birlik siljiting: qancha tayoq yutadi, qanchasi yutqazadi?

• Ferris WheelCSES 1090o'rta

  Eng og‘ir bolani kim bilan juftlash kerak? Javobni almashish argumenti bilan asoslang.

Lokal mashq: mashqlar/16-navbat-tartibi/ — masala matni, testlar va tekshir.py. Avval sekin.py ni o‘zingiz yozing, keyin tayyorini oching.

Topshiriq

Topshiriq — darajangizni tanlang

Asos5–7-sinfMustahkam8–9-sinfChuqur10–11-sinf

Asos · 5–7-sinf — Vizual va aniq ko'rsatmali

Eng katta sonni topish algoritmi uchun invariantni bir gapda yozing. Keyin [4, 9, 2] ro’yxatida har qadamdan keyin shu gap rost ekanini tekshirib chiqing.

Mustahkam · 8–9-sinf — Matnli masala, o'zingiz tuzasiz

16-navbat-tartibi masalasini yeching. sekin.py barcha tartiblarni ko’radi — uni n = 8 da yurgizib, necha variant tekshirilganini hisoblang. Keyin almashish argumentini o’z so’zingiz bilan yozing.

Chuqur · 10–11-sinf — Algoritmik, chegara holatlari bilan

Ferris Wheel masalasini yeching va yozma isbot keltiring: nega eng og’ir bolani eng og’ir mos sherigi bilan juftlash optimal? Isbotingizni sinfdoshingizga o’qib bering — u «demak» so’zining tagidagi taxminni topa oladimi?

Darsni belgilash uchun JavaScript kerak. Bu progressni saqlash uchun ishlatiladi — darslikning o'zi JavaScript'siz ham to'liq o'qiladi.

Darsni tugatdim