Pentru a nu crea confuzii, acesta nu este un articol științific, ci o prezentare a unui site deschis în 2014: www.be-logic.ro care încearcă să acopere un gol privind modul tradițional al acumulărilor de cunoștințe.
Introducere
De obicei informatica consideră că algoritmica este domeniul de bază cu care trebuie să înceapă pregătirea unui viitor programator.
Fals!
Un algoritm nu poate fi înțeles - și cu atât mai puțin conceput - dacă nu suntem obișnuiți cu un mod logic de abordare a problemelor.
Mai mult, totul în jur se desfășoară după o anumită logică, iar regulile acestei logici sunt aproape aceleași, indiferent de domeniul considerat.
Întotdeauna vor exista propoziții adevărate și propoziții false; întotdeauna valoarea lor va fi determinantă în desfășurarea activităților (profesionale sau - de ce nu? - zilnice).
Întotdeauna o anumită acțiune depinde de anumite premise și întotdeauna ea va avea un anumit efect, chiar dacă nu conștientizăm permanent acest lucru.
Experiența a arătat că o pregătire temeinică în aria IT (chiar și numai pentru simpli utilizatori) are nevoie de o gândire organizată.
Cum este dificil de convins cineva de necesitatea unor lecții de calcul propozițional, de numeroasele categorii de logică folosite (binară, Lukasiewicz, Moisil, propozițională, temporală, deontică etc.), o modalitate utilizată tot mai frecvent este cea ludică: este mai ușor să înveți prin joacă.
Așa că în 2001 (după mai multe tentative) am lansat un site de probleme www.galaxyng.com/potw (site-ul mai poate fi accesat și acum, deși este inactiv). Aici erau propuse săptămânal câte două probleme de logică - înrudite în special cu matematica.
Ulterior am avut surpriza să găsesc probleme de pe acest site folosite la testele de angajare de firme de IT (evident, fără nicio menționare a sursei).
După ce am trecut în timp prin diverse variante (www.revistadelogica.com, fmi.unibuc.ro/revistadelogica), din toamna anului trecut am lansat - cu ajutorul lui Bogdan Burlacu - site-ul www.be-logic.ro.
Aici propun bilunar patru probleme de dificultăți diferite (de la cele de nivelul învățământului gimnazial până la probleme de cercetare). Marea lor majoritate nu sunt enunțuri originale ci sunt preluate de pe alte site-uri de profil (IBM, Macalestear Univ, Massachussettes Univ etc.) sau din concursuri anuale (Puzzleup, Turkzeka, MathPuzzle și altele).
Exemple de probleme
În cei 15 ani, pe site-urile (www.galaxyng.com/potw, www.revistadelogica.com, www.be-logic.ro) au fost propuse și rezolvate peste 1000 probleme. Am selectat pentru exemplificare numai trei.
Prima este o problemă de implicații logice:
Se fac următoarele afirmații:
Întrebare: Animalele din curtea mea pot fi trase de coadă? |
Se pot da multe soluții. De exemplu:
(2) Animalele din curtea mea nu au coarne ⇒ (5) Nici un animal din curtea mea nu poate arunca pe cineva peste gard ⇒ (3) Taurii nu fac parte din animalele din curtea mea ⇒ (6) Toate animalele din curtea mea sunt ușor de înfuriat ⇒ (1) Toate animalele din curtea mea lovesc cu piciorul ⇒ (4) Niciun animal din curtea mea nu poate fi tras de coadă.
Sau:
Din 1 și 6 rezultă că taurii și numai taurii nu lovesc cu piciorul.
Conform 4, taurii și numai taurii pot fi trași de coadă.
Din 2 și 5 rezultă că în curtea mea nu sunt animale care pot arunca ușor pe cineva peste gard.
Conform 5, la mine în curte nu sunt tauri.
Concluzie: animalele de la mine din curte nu pot fi trase de coadă.
În mod deliberat nu am prezentat aici o rezolvare formalizată.
Și o problemă cu discuții între logicieni:
| Sunt alese patru numere întregi distincte din intervalul [1, 10]. Lui S i se spune suma acestor patru numere, iar lui P produsul lor.Cei doi sunt apoi întrebați dacă pot ghici numerele. Are loc urmatoarea secvență de afirmații:S: Nu știu nici un număr. P: Știu unul din ele. S: Acum știu și eu două numere. P: Acum le știu pe toate patru.Care ar putea fi cele patru numere? |
Cele patru numere sunt {4, 6, 9, 10} sau {2, 8, 9, 10}.
După afirmația lui P ("Eu știu un număr"), S deduce că sunt posibile următoarele combinații:
P = 210: {2, 3, 5, 7}; {1, 5, 6, 7}; {1, 3, 7, 10}
P = 216: {2, 3, 4, 9}; {1, 4, 6, 9}; {1, 3, 8, 9}
P = 252: {2, 3, 6, 7}; {1, 4, 7, 9}
P = 270: {2, 3, 5, 9}; {1, 5, 6, 9}; {1, 3, 9, 10}
P = 280: {2, 4, 5, 7}; {1, 5, 7, 8}; {1, 4, 7, 10}
P = 288: {2, 3, 6, 8}; {1, 4, 8, 9}
P = 336: {2, 4, 6, 7}; {2, 3, 7, 8}; {1, 6, 7, 8}
P = 420: {3, 4, 5, 7}; {2, 5, 6, 7}; {2, 3, 7, 10}; {1, 6, 7, 10}
P = 432: {2, 4, 6, 9}; {2, 3, 8, 9}; {1, 6, 8, 9}
P = 504: {3, 4, 6, 7}; {2, 4, 7, 9}; {1, 7, 8, 9}
P = 540: {3, 4, 5, 9}; {2, 5, 6, 9}; {2, 3, 9, 10}; {1, 6, 9, 10}
P = 560: {2, 5, 7, 8}; {2, 4, 7, 10}; {1, 7, 8, 10}
P = 630: {3, 5, 6, 7}; {2, 5, 7, 9}; {1, 7, 9, 10}
P = 840: {4, 5, 6, 7}; {3, 5, 7, 8}; {3, 4, 7, 10}; {2, 6, 7, 10}
P = 960: {4, 5, 6, 8}; {3, 4, 8, 10}; {2, 6, 8, 10}
P = 1080: {4, 5, 6, 9}; {3, 5, 8, 9}; {3, 4, 9, 10}; {2, 6, 9, 10}
P = 1260: {4, 5, 7, 9}; {3, 6, 7, 10}; {2, 7, 9, 10}
P = 1440: {2, 8, 9, 10}; {4, 5, 8, 9}; {, 3, 6, 8, 10}
P = 1680: {5, 6, 7, 8}; {4, 6, 7, 10}; {, 3, 7, 8, 10}
P = 2160: {4, 6, 9, 10}; {5, 6, 8, 9}; {, 3, 8, 9, 10}
Aceste variante se obțin căutând toate numerele care se pot descompune în două produse de câte trei factori din [1, 10], toate cele șase numere din cele două produse fiind distincte.
La cele două grupe de câte trei factori se adaugă apoi arbitrar unul dintre celelalte patru numere neutilizate.
S ordonează aceste quadrupluri după suma lor:
S = 17: {2, 3, 5, 7}
S = 18: {2, 4, 5, 7}; {2, 3, 6, 7}; {2, 3, 4, 9}
S = 19: {3, 4, 5, 7}; {2, 4, 6, 7}; {2, 3, 6, 8}; {2, 3, 5, 9}; {1, 5, 6, 7}
S = 20: {3, 4, 6, 7}; {2, 5, 6, 7}; {2, 3, 7, 8}; {1, 4, 6, 9}
S = 21: {3, 5, 6, 7}; {3, 4, 5, 9}; {2, 4, 6, 9}; {1, 5, 7, 8}; {1, 5, 6, 9}; {1, 4, 7, 9}; {1, 3, 8, 9}; {1, 3, 7, 10}
S = 22: {4, 5, 6, 7}; {2, 5, 7, 8}; {2, 5, 6, 9}; {2, 4, 7, 9}; {2, 3, 8, 9}; {2, 3, 7, 10}; {1, 6, 7, 8}; {1, 4, 8, 9}; {1, 4, 7, 10}
S = 23: {4, 5, 6, 8}; {3, 5, 7, 8}; {2, 5, 7, 9}; {2, 4, 7, 10}; {1, 3, 9, 10}
S = 24: {4, 5, 6, 9}; {3, 4, 7, 10}; {2, 3, 9, 10}; {1, 6, 8, 9}; {1, 6, 7, 10}
S = 25: {4, 5, 7, 9}; {3, 5, 8, 9}; {3, 4, 8, 10}; {2, 6, 7, 10}; {1, 7, 8, 9}
S = 26: {5, 6, 7, 8}; {4, 5, 8, 9}; {3, 6, 7, 10}; {3, 4, 9, 10}; {2, 6, 8, 10}; {1, 7, 8, 10}; {1, 6, 9, 10}
S = 27: {4, 6, 7, 10}; {3, 6, 8, 10}; {2, 6, 9, 10}; {1, 7, 9, 10}
S = 28: {5, 6, 8, 9}; {3, 7, 8, 10}; {2, 7, 9, 10}
S = 29: {4, 6, 9, 10}; {2, 8, 9, 10}
S = 30: {3, 8, 9, 10}
Căutăm acum o linie pe care:
- există cel puțin două quadrupluri (altfel S ar ști toate cele patru numere),
- toate quadruplurile au două (și numai două) elemente comune.
Există o singură linie cu această proprietate: 29 : {4, 6, 9, 10}; {2, 8,9, 10}.
După afirmația lui S; P deduce că este vorba de această linie. Cum el cunoaște produsul, va putea decide care din cele două quadrupluri este soluție.
Pe lângă probleme specifice de logică sunt și probleme cu tentă informatică pronunțată, de exemplu:
| În Masada (Galileea) s-a decis că erau prea mulți prizonieri și ei trebuie executați. 1000 prizonieri (numerotați de la 1 la 1000) au fost așezați în cerc, iar celui cu numărul 1 i s-a dat o sabie. El a fost instruit să omoare cu ea prizonierul situat la stânga, după care să dea sabia următorului prizonier viu (din stânga); acesta va trebui să facă aceleași operații. Procedeul se repetă până rămâne un singur prizonier, care va fi eliberat. Din Masada a iesit Iosif. a) Ce poziție ocupa el în cercul celor 1000 prizonieri ? b) Deoarece ultima mișcare generează controverse (rămân doi prizonieri și unul îi dă sabia celuilalt să îl omoare), se decide să fie lăsați liberi ultimii doi prizonieri. Pe ce loc era camaradul lui Iosif, care a scăpat din Masada? (Examen de admitere Ph.D, Standford 1995) |
Răspunsul este 977 (pentru Iosif) și 465 (pentru camaradul său).
Soluția se poate obține foarte elegant în modul următor: se scrie 1000 în binar, după care primul 1 (din stânga) se mută la sfârșitul numărului.
Reprezentarea binară a numărului 1000 este 1111101000. Mutând 1 la sfârșit, se obține 1111010001, care este scrierea în binar a lui 977.
Ca altă variantă, se complementează 1000 scris în binar, iar ce rezultă se scade din 1000 (afirmația este adevărată și pentru un N arbitrar). Astfel, complementul lui 1111101000 este 10111 - scrierea lui 23 în binar. Calculând apoi 1000 ?- 23 obținem 977.
Pentru a doua persoană grațiată: se complementează prima cifră binară din numărul lui Iosif: deci, 1111010001 devine 0111010001, care este reprezentarea binară a lui 465.
Probleme curente
Site-ul www.be-logic.ro se actualizează la 1 și 16 ale fiecărei luni. Ultimele probleme, propuse pe 1 iulie 2015 sunt:
Cacao, 5 puncte
Deși este vară, azi este o vreme ploioasă și ai decis să-ți faci o ceașcă cu cacao fierbinte. Începi prin a umple cana cu cacao (de fapt un amestec de apă cu cacao dizolvată).
Bei o optime din conținut și constați că trebuie ceva lapte. Completezi cana adăugând lapte și din acest amestec bei o treime.
Din nou, ești de părere că mai trebuie lapte, așa că faci din nou o completare până se umple cana. Din noul conținut de cacao cu lapte bei o jumătate de cană.
Umpli din nou cana adăugând lapte. Culmea, acest amestec de lapte și cacao îți place foarte mult, așa că bei totul.
Dacă iei ca măsură ceașca, cât lapte și câtă cacao ai băut ?
Afirmații, 10 puncte
Avem următoarele afirmații:
- Acum este zi.
- Acum este noapte.
- Exact una din afirmațiile 6 și 9 este adevărată.
- Exact una din afirmațiile 2 și 6 este falsă.
- Afirmațiile 4, 5 și 10 sunt toate false.
- Exact una din afirmațiile 1 și 10 este falsă.
- Cinci din aceste 11 afirmații sunt adevărate.
- Exact una din afirmațiile 3 și 10 este falsă.
- Exact una din afirmațiile 6 și 10 este adevărată.
- Exact una din afirmațiile 1 și 2 este falsă.
- Afirmațiile 1, 8 și 11 sunt toate false.
i. Care dintre cele 11 afirmații sunt întotdeauna adevărate?
ii. Este zi sau este noapte?
Cumpărături, 25 de puncte
La un magazin sunt de vânzare cinci produse: A, B, C, D, E. Prețurile lor în lei sunt numere întregi din intervalul [1, 500].
Să presupunem că aveți un cont care este penalizat cu o jumătate de punct de câte ori cumpărătura pe care o faceți nu este multiplu de 5 lei.
Prețul produsului A este de 1 leu, dar nu știi nimic despre prețurile celorlaltor patru produse. De asemenea, nu ești avertizat de prețurile și penalizările pe care le acumulezi în timp.
Singura informație - pe care o obții la sfârșitul lunii - este dacă penalizările cumulate pe luna respectivă sunt un număr întreg sau nu.
De exemplu după ce ai făcut următoarele șase cumpărături:
AB
AC
AABC
AAABCC
AAABBC
BBBBC
poți decide dacă B și C costă (sau nu) ambele 4 lei.
Problema cere să stabiliți un set de cumpărături - câte una pe zi - astfel ca la sfârșitul lunii să știi dacă prețurile produselor B, C, D, E au exact două valori distincte.
Mănuși, 10 puncte
S-a întâmplat o catastrofă și singurul spital din zonă trebuie să facă față afluxului de pacienți care trebuie operați urgent.
Cazurile sunt atât de complexe încât fiecare pacient trebuie operat de fiecare doctor.
Problema este că pacienții pot suferi de diverse boli contagioase, iar doctorii - prin natura meseriei - pot fi purtătorii altor boli infecțioase.
Deci, pentru a preveni răspândirea vreunui microb care ar face situația și mai grea, fiecare doctor trebuie să folosească mănuși la contactul cu un pacient. Trebuie avut grijă să nu existe niciun doctor și niciun pacient care să intre în contact cu suprafața (unei mănuși) deja contaminată prin contactul cu alt doctor/pacient.
Este permis ca:
a) doctorii să poarte mai multe perechi de mănuși simultan (trase una peste alta); de remarcat că atunci suprafațele de contact dintre mănuși se pot contamina una de la alta;
b) mănușile să poată fi întoarse și folosite pe oricare din fețe.
Știind că sunt x doctori și y pacienți, care este numărul minim de mănuși folosite în următoarele cazuri:
1) x = y = 2;
2) x = 3; y = 1;
3) x = y = 4.
Dacă vă plac asemenea probleme și doriți să aflați mai multe, vă aștept pe site-ul www.be-logic.ro.
Prof. Dr. Emerit Adrian Atanasiu
Universitatea București
