2014 2015 2016 2017 2018
BEBRO konkurso užduotys 2017

 

Skaitmenų atpažinimas

Taškai: 12

Skaitmenų atpažinimo sistema atpažįsta taip pavaizduotus skaitmenis:

Kiekvieną skaitmenį sudaro 7 atkarpos. Skaitmeniui atpažinti nebūtinai turi būti matomos visos 7 atkarpos. Sistema gali atpažinti skaitmenį net ir nežinodama, kaip pavaizduotos kai kurios atkarpos.

Parink atkarpas, kurios būtinos visiems dešimt skaitmenų (0...9) atpažinti.

Spustelėdamas pelę pasirink atkarpą arba atšauk savo pasirinkimą.

Paaiškinimas

Atpažinimo metodais (angl. pattern recognition algorithm) dažniausiai siekiama visoms įvestims surasti pagrįstą atsakymą ir išrinkti tikėtiniausią atitikmenį įvesčiai, atsižvelgiant į statistinį svyravimą. Atpažinimo metodai naudojami mašinų mokymosi srityje, kurioje daugiausia dėmesio skiriama duomenų ir dėsningumų atpažinimui. Vienas iš atpažinimo metodų yra nustatyti tam tikras savybes, pagal kurias vienareikšmiškai identifikuojami objektai.

Kompiuteriai – aktyviai besivystanti informatikos sritis. Plačiau galima skaityti čia:

https://en.wikipedia.org/wiki/Pattern_recognition

https://en.wikipedia.org/wiki/Computer_vision

https://en.wikipedia.org/wiki/Optical_character_recognition

https://en.wikipedia.org/wiki/Automatic_number_plate_recognition

Raktiniai žodžiai: skaitmuo, atpažinimas, minimizavimas.

Atsakymas

Teisingas atsakymas yra

Paaiškinsime, kodėl 4 atkarpų nepakanka. Kadangi 0 ir 8 skiriasi tik viena atkarpa, tai ši atkarpa yra būtina skaitmenims atpažinti:

Visus skaitmenis galima padalyti į dvi grupes. Tie, kurie turi šią atkarpą – {2;3;4;5;6;8;9}, ir tie, kurie jos neturi – {0;1;7}. Kitame žingsnyje pastebime, kad 1 ir 7 taip pat skiriasi tik viena atkarpa, todėl ją būtina pasirinkti:

Dabar visi skaitmenys suskirstyti į 4 grupes pagal tai, ar jie turi šias dvi atkarpas, ar ne: {1}, {0;7}, {4}, {2;3;5;6;8;9}. Pasirinktos atkarpos jau leidžia atpažinti 1 ir 4.

Suraskime kitus skaitmenis, kurie skiriasi tik viena atkarpa. Tokie skaitmenys yra 8 ir 9. Pasirinkime juos skiriančią atkarpą:

Dabar skaitmenys susiskirsto taip: {1}, {0}, {7}, {4}, {2;6;8}, {3;5;9}. 6 ir 8 taip pat skiriasi tik viena atkarpa. Pasirinkime ją:

Turime šias grupes: {1}, {0}, {7}, {4}, {2;8}, {6}, {3;9}, {5}. Taigi keturių atkarpų nepakanka skaitmenims atpažinti, nes 2 ir 8, taip pat 3 ir 9 dar liko neatskirti.

3 ir 9 skiriasi tik viena atkarpa. Šia atkarpa taip pat skiriasi skaitmenys 2 ir 8. Todėl turime pasirinkti dar ir šią atkarpą:

Pasirinkę visas aptartas atkarpas, gauname sprendinį:

Šis paaiškinimas parodo, kad atsakymas yra vienintelis.

Interaktyvi užduotis