Dokaz ostavljamo čitateljici za vježbu

U opisima algoritama, koji su dio objavljenih rješenja većine domaćih natjecanja, nerijetko se na kraju opisa rješenja pojedinog zadatka pojavljuje rečenica “Dokaz točnosti algoritma ostavljamo čitatelju za vježbu”. Ili čitateljici, da ne bi tko pomislio da autori imaju predrasude. Tako smo u rješenjima Studentskog 2018. u čak tri zadatka ostavili dokaz točnosti ili efikasnosti algoritma za vježbu upravo čitateljici.

Navedena rečenica nije karakteristična samo za opise algoritama, ona se često viđa i u matematici i sličnim znanostima. No koje je njezino pravo značenje?

Iz iskustva, rečenica može imati tri moguća značenja:

  1. Dokaz ostavljamo čitatelju za vježbu jer je točnost ili efikasnost algoritma, ako se on čita s razumijevanjem i ako se o njemu malo promisli, prilično očita i dokaz je bolje izostaviti da bi čitatelj malo zastao i razmislio o pročitanom. (Ovo je slučaj u zadatku Stablo u stablu sa spomenutog Studentskog.)
  2. Dokaz ostavljamo čitatelju za vježbu jer smo u se u točnost tvrdnje uvjerili intuitivno, a znali bismo je i dokazati, ali dokaz nije lako ukratko napisati i vjerojatno bi bio ružnjikav. (Ovo je slučaj u zadatku Ploča sa spomenutog Studentskog, kao i npr. u zadatku Sails – IOI 2007.)
  3. Dokaz ostavljamo čitatelju za vježbu jer tvrdnju ne znamo sami dokazati. (Ovo je slučaj u zadatku Načitan sa spomenutog Studentskog za neparan N, a skoro je bio slučaj i u zadatku GTA s Izbornih priprema 2014.)

Postoji i četvrti slučaj – autor rješenja izostavlja ne samo dokaz, nego i navedenu rečenicu, praveći se da je sve jasno, iako nije. Krunski primjer je zadatak Mravograd (Državno 2007.) koji je poznat po kratkom i lijepom rješenju za koje nije očita ni točnost, a pogotovo efikasnost tj. složenost algoritma. Do ključne zamjedbe dolazi se određenim koracima u razmišljanju koji su u službenom opisu izostavljeni. Drugim riječima, rješenje nije napisano metodički. No budući da se radi o zadatku za malo jaču publiku, autor (Luka Kalinovčić, ako se ne varam) nije nas podcijenio: čitatelji (i čitateljice, naravno) sposobni su sami ispuniti rupe u rješenju. A ta je rupa generiranje slučajnih primjera i promatranje u kojim se oblicima pojavljuju traženi “mokri trgovi”. Odatle se dolazi do tražene ideje.

U praksi je, dakle, i empirijski dokaz često dovoljan. Ionako u implementaciji griješimo češće nego u ideji. Testiranje rješenja usporedbom sa brute-forceom i generatorom slučajnih primjera u praksi je odličan dokaz. (To zaboravljaju neki natjecatelji naviknuti na online evaluatore i full feedback i onda griješe na županijskom ili HONI natjecanju.) Nedavno je Errichto pisao o jednom manje uobičajenom načinu testiranja. Ja sam je iskoristio nedavno, kada sam za zadatak Dionice (autora Domagoja Bradača) s ovogodišnjeg županijskog natjecanja pisao rješenje radi provjere. Nisam htio implementirati potpuno isti algoritam kao Domagoj (jer što ako je slučajno pogrešan), nego sam odlučio zadani niz gledati unatrag i primijeniti analogan algoritam u obrnutom smjeru. Dobio sam iste rezultate, što je empirijski potvrdilo točnost algoritma. Domagoj je doduše napisao dokaz, ali kao što ovaj odlomak sugerira, matematički dokaz nikad nije dovoljan jer ljudi griješe (zabrijavaju). U matematici se stvari dokazuju, a u drugim znanostima (kao i u životu) stvari se testiraju.

Dakle, pravo značenje rečenice “Dokaz ostavljamo čitatelju za vježbu” upravo je ono koje čitatelj svjesno ili nesvjesno percipira čim pročita tu rečenicu. Ono glasi: “Formalni dokaz nije bitan”. Bitno je da se čitatelj na ovaj ili onaj način uvjeri u istinitost tvrdnje. Primjerice, ako želimo podijeliti prirodne brojeve A i B tako da količnik zaokružimo na više, možemo ga dobiti kao (A + B – 1) div B. Na jednoj radionici nije mi se dalo objašnjavati zašto je tako pa sam rekao “dokažite za domaću zadaću”. Naravno, nisam očekivao da itko to formalno dokaže koristeći najveće cijelo i nejednakosti. U ovom slučaju dovoljno se uvjeriti na primjerima promatrajući nekoliko bitnih slučajeva. Dokazivanje je samo formalizacija intuicije, iako je taj stav općenito diskutabilan. Razmislite o njemu sami, za vježbu.

Komentiraj

Popunite niže tražene podatke ili kliknite na neku od ikona za prijavu:

WordPress.com Logo

Ovaj komentar pišete koristeći vaš WordPress.com račun. Odjava /  Izmijeni )

Google photo

Ovaj komentar pišete koristeći vaš Google račun. Odjava /  Izmijeni )

Twitter picture

Ovaj komentar pišete koristeći vaš Twitter račun. Odjava /  Izmijeni )

Facebook slika

Ovaj komentar pišete koristeći vaš Facebook račun. Odjava /  Izmijeni )

Spajanje na %s