Píšu CML

26.2.2015 21:58 | Přečteno: 1993× | LeliMath | poslední úprava: 26.4.2016 19:44

Aspoň mám ten pocit. Chci napsat dcerce na tablet aplikaci na procvičování matematiky. Udělal jsem si poměrně jasnou představu o designu i funkčnosti a začal jsem ji realizovat. Před večeří jsem dopsal komplexní datový model, co vše se dá parametrizovat pro generování rovnic. Zadavatel bude mít obrovské možnosti. Problém nastal, když jsem začal psát generátor.

Sepsání myšlenek mi možná pomůže odrazit se dál, pokud ne, třeba mi někdo ze čtenářů konstruktivně poradí.

Pro oba operandy rovnice i výsledek je možné nadefinovat buď minimální nebo maximální či obě hodnoty, případně rozsah hodnot (v tom případě jsou min a max zakázány). Pro jednoduchost zapomeňme na možné omezení vzdálenosti operandů. Triviální příklad se všemi možnostmi zadání je na prvním řádku, jedno řešení je na druhém řádku

min: 1, max: 10	+	min: 10	=	výčet: 12, 13, 14, 18
2	+	11	=	13

Problém je, jak napsat obecný generátor? Nejspíše bych měl začít od výčtu hodnot, ze kterého si náhodně vyberu jedno číslo. A pak náhodně vybrat druhé číslo a dopočítat zbývající číslo. Například u uvedeného příkladu si k náhodnému výsledku (13) náhodně vygeneruju první operand (2) a vypočtu druhý (11). Bohužel je ale až příliš snadné zvolit číslo, se kterým rovnice nikdy nebude sedět; ke kterému nenajdu vhodné operandy. Můžu si pomoci chytristikou pro konkrétní situace. Zde u odečítání je lepší si vybrat vyšší číslo, takže začnu druhým operandem (11) a odečtem získám první (2). Ale stejně mi hodnota nemusí vyjít v rozsahu povolených hodnot. Takže pak musí následovat hledání správné kombinace brutální silou s pojistkou proti uváznutí (když zadání nemá řešení nebo mám smůlu na blbě vylosovaná čísla).

Během psaní jsem nic nového nevymyslel. Napadá něco vás?

       

Komentáře

[Radek Miček]

Jaké funkce se v těch rovnicích mohou vyskytovat?

Pro vyřešení omezujících podmínek můžete zkusit nějaký CSP řešič např. minion nebo Gecode nebo ECLiPSe. Pokud to bude složitější, pak budete zřejmě potřebovat nějaký systém pro počítačovou algebru.

[Leoš Literák]

Díky, tušil jsem, že to bude vědecká disciplína. Po zběžném prohlédnutí nevidím reálné zprovoznění těchto knihoven pod androidem. Ale zkusím hledat něco v javě, už znám klíčová slova.

[Dadam]

Sčítání a násobení bych udělal hrubou silou. Vyberu si výsledek, vygeneruju všechny možnosti jak ho dostat (pro sčítání je počet možností rovný výsledku, to není tak hrozné) a pak z nich vyberu ty, které vyhovují omezením pro operandy.

Odčítání a dělení bude trochu horší, s daným výsledkem můžou být operandy jakkoliv složité. Tak si trochu pomůžu a jak odčítání, tak dělení si pro účely generování převedu na sčítání, respektive násobení. Pozor na dělení nulou.

[Marvin]

Mas uz to implementovany? Dochazi tam realne k tomu zasekavani?

Pokud to ma reseni, tak pravdepodobnost ze to bude u takhle jednoduchych prikladu nekonecne cyklit je dost mala. I kdyz chapu ze i ta teoreticka moznost ze k tomu dojde zpusobi ze brouk v hlave hloda Ja mam podobnej filozofickej problem s gitem, kde se k identifikaci souboru pouzivaji hashe, a muze tam dochazet ke kolizim.

Nedavno jsem delal neco podobnyho pro sestru a delal jsem to jednoduse hrubou silou:

- vygeneruju prvni cislo

- druhy cislo

- zkontroluju jestli vysledek je v nejakym rozsahu; kdyz ne tak zahodim a opakuju

Zadnyho zasekavani jsem si nevsiml. Ono i kdyz bys musel udelat treba 1000 pokusu nez se trefis, tak na dnesnich pocitacich jsou to radove mikrosekundy...

Kdyz by k tomu dochazelo tak bych tam asi dal pocitadlo a po N pokusech nahlasil chybu

[Leoš Literák]

Na tabletech jsou přeci jen horší procesory než v PC, takže stupidní hrubou silou jít nemohu. Chci ty větve aspoň trochu optimalizovat. Ale jinak konceptuálně souhlasím.

[radix]

Dnesni PC/NTB jsou tak 10krat (max) rychlejsi nez dnesni prumerne tablety.

Hledat nejaka chytra/rychla reseni mne v tomto pripade prijde jako predcasna optimalizace. Ale pokud se s tim chce clovek trochu vyhrat/neco se naucit a ma na to cas, tak proc ne ...

[Leoš Literák]

Vždycky se snažím nejdříve přemýšlet a pak programovat. Pamatuju na přednášku na UPOL od Drdy, kdy vykládal, jak železničáři měli hrozně složitý algoritmus na fixní počet desetinných míst, který počítal poloměr zatáčky pro trať. Potřebovali více desetinných míst. Kouknul na to, našel v tom geometrické rovnice a sepsal jim na pár řádek algoritmus na libovolný počet desetinných míst.

Podobně tady pro násobení. Pokud mám rozsah násobenců 10 čísel, může vyjít celkem 100 výsledků. Pokud je ale povoleno jen 5 výsledků, tak nalezení těchto rovnic může být se šancí 1:20 (pro prvočísla). Pokud ale začnu hledat od výsledku, mám dvakrát lepší šanci.

[deda.jabko]

Pamatuju na přednášku na UPOL od Drdy...

Toto je stezi uveritelna historka, ... protoze Dr.Dla na prednasky zasadne nechodil.

[Leoš Literák]

Bavím se o roku cca 1997.

[Mercuriuz]

predčasná optimalizace a promyslet si to dopředu a vyvarovat se možným problémům není jedno a to samý, nesmí se to samozřejmě přeháňet, ale pokud jde o důležitou část systému na které bude stát víc věcí, radši budu 20 minut přemýšlet a pak 10 minut programovat, než 5 minut přemýšlet a 5 minut programovat a potom to 10x přepisovat (nebo dělat znovu) včetně všech částí které ovlivnil přepis základu

[Josef Kufner]

Pokud to má být v rozsahu malé násobilky, tak těch možností budou stovky až tisíce. To i líný tablet upočítá během pár milisekund. Nebude to hezké řešení, ale bude spočítané rychleji, než naimplementuješ to hezké.

[Leoš Literák]

Filozofická otázka: je lepší hledat řešení pro náhodně generované argumenty nebo najít všechny rovnice a z nich jednu náhodně vybrat? No, nic zase to přepíšu

[Kaiten]

Vypočítat celkové množství možných rovnic, jednu náhodně vybrat a tuto konkrétní vygenerovat (skrz vygenerování všech kombinací před naší chtěnou). Velice rychle by se to dalo řešit v nějakém líném jazyku. Šla by Scala. Má explicitní lenost a běží nad JVM. Také by šli kombinace cachovat, pokud dá paměť. A pokud ne, šli by napřed komprimovat.

[Leoš Literák]

Reálné výsledky na Nexus 4: během jedné milisekundy zvládne 5 cyklů nalezení jedné rovnice (obsahující 2x generování náhodného čísla, dvě matematické operace, pár porovnání a hlavně několik volání funkcí).

Parametry:

FormulaDefinition{unknowns=[RESULT], operators=[+], result=Values{minValue=null, maxValue=null, listing=[10, 11, 12]}, operandDifference=null, rightOperand=Values{minValue=3, maxValue=60, listing=null}, leftOperand=Values{minValue=0, maxValue=90, listing=null}}

Moje optimalizovaná verze najde v 10 případech řešení do 3 pokusů 6x, do 5 pokusů 1x, do 9 pokusů 2x a jednou potřebovala 35 pokusů (což zabralo 7 ms). To je docela slušné

[Josef Kufner]

Pokud vím, ty destičky mají CPU běžící minimálně na 1GHz. Máš tam pár násobení, hm, co ten program dělá těch zbývajících 999000 taktů?

[Josef Kufner]

Trochu inspirace můžeš najít v materiálech k předmětu Testování a verifikace software, hlavně v druhé přednášce. Sice ti to komplikuje vazba mezi operandy a výsledkem, ale mohlo by ti to pomoct s generováním lépe rozložených testů v prostoru.

[Radovan]

Například u uvedeného příkladu si k náhodnému výsledku (13) náhodně vygeneruju první operand (2) a vypočtu druhý (11).

Já jsem na to šel opačně, vždy jsem vygeneroval operandy, z nich jsem vypočítal výsledek. Pokud byly příklady sčítání a násobení, vypsaly se operandy, pokud byly odčítání a dělení, vypsal se výsledek a první operand, bez ohledu na to jestli je větší nebo menší. Tak jsem se vždycky vešel do zadaného limitu.

Nedělaly se před třiceti lety takovéhle věci v BASICu na dvacet řádků?

[Leoš Literák]

Problém jsou ty omezující podmínky. V tomto případě součet náhodného čísla do desíti a většího než deset se málokdy trefí do čtyř konkrétních hodnot.

[Mercuriuz]

chápu důvod pro min-max omezení operandů a chápal bych to i u výsledku, proč je ale potřeba konkrétní výsledek z výčtu hodnot?

[Leoš Literák]

Analyzoval jsem učebnici, jaké typy příkladů tam jsou. A tak mi přišlo dobré mít kromě od-do i možnost definovat konkrétní hodnoty. Asi jsem to nadefinoval příliš univerzálně, teď právě ruším decimální čísla a nechám jen celá.

[KS]

Tolik práce a přitom je to taková blbost

Koupil bych dceři papír a tužku a místo věnování spousty času sezení u počítače nad pochybným programem využil čas k osobnímu kontaktu.

[Aleš Kapica]

Přesně tak. Věnovat tolik času ptákovině, která ji za půl hodiny přestane bavit, je úplně o ničem.

Věnuj ten čas raději rovnou jí. Udělej si s ní výlet do nějakého IQ parku, když už ji chceš dopřávat technické vzdělání, nebo jen tak někam na hřiště, kde bude mít kontakt s jinými dětmi. Uděláš lépe.

[Leoš Literák]

Je to koníček pro mě. Jsem tvořivý člověk, nebaví mě jen konzumovat. Stagnace je čekání na smrt.

[pavlix]

+1

[Aleš Kapica]

Pokud to bereš jako cvičení, a pak se s tím hodláš někde vytasit.. Chtěl jsem jenom upozornit na fakt, že představy rodičů jsou mnohdy na hony vzdálené od představ jejich ratolestí.

[OldFrog {Ondra Nemecek}]

To je v pořádku, proti Vaší technické programovací zálibě nemůže nikdo nic namítat, sám to znám

Nicméně připomínka Aleše Kapicy a JD míří k otázce, zda to děláte pro sebe nebo pro dceru.

Pokud pro dceru, opusťte tablet a matematiku se učte skutečně rovnou s ní. Mimo kontakt, který má význam pro vás oba, to může být zajímavé i pro Vás - existují třeba pozoruhodné metody jak matematiku učit pomocí hudby (je využit rytmus a opakování), kreslení (je využita geometrie a vizuální vnímání), navlékání provázků (je využita topologie), ve skupině pomocí cvičení (kombinace všeho předešlého) atd. Viz montessori, waldorfská a intuitivní pedagogika.

Dopad na člověka se pak nedá porovnat s hraním nejaké hry na tabletu, které může malé děti spíš poškodit (chápu, že tím řadu lidí zde pobouřím, ale jsem o tom přesvědčen, mimo jiné vzhledem ke své zkušenosti s lidmi s postižením). Něco jiného je učit matematiku pomocí programování lidi v pozdějším věku - gymnázium a dál., tam je člověk už plně vybaven na uvažování v abstrakcích a je to naopak to pravé. Tam už ale programuje přímo ten člověk - žák.

Omlouvám se za delší příspěvek - ale podle mě to je přímo k tématu.

[Mercuriuz]

To, jestli ji přestane bavit není jisté, pokud by finální aplikace byla ve formě hry, může mít dítě radost z odehraného levelu (správně vypočítaných příkladů), následné odměny a samozřejmě chuť jít dál. Výukové aplikace nejsou vždycky špatné, pokud dítě ve volném času může k tabletu sednout a hrát hry které jsou totálně o ničem, je možnost, že by si dobrovolně vybralo zábavnou výukovou aplikaci - a o to by bylo strašně fajn, no ne?

[luky]

Resil bych to jako soustavu. Vycet se rozpadne na nekolik soustav podle intervalu. Pocitam ze se jedna o cela cisla, pokud ne, da se na ne prevest nasobenim mocninou desitky podle pozadovaneho poctu mist.

Po rozpadu vyctu c na 2 intervaly, ukazka pro c z <12; 14>:

  I.   a >= 2
 II.   a <= 9
III.   b >= 11
 IV.   c >= 12   --->   a + b >= 12
  V.   c <= 14   --->   a + b <= 14
------------------------------------
       b <= 12   V. - I.
       a <= 3    V. - III.
------------------------------------
       2 <= a <= 3
      11 <= b <= 12

Nyni postupuji tak, ze si postupne volim promenne z intervalu a dopocitam ostatni. Pro a = 2 a dosazeni do zbytku mi zadna omezujici podminka nepribude, takze mam reseni [2; 11], [2; 12]. Pro a 3 mi pribude b <= 11 (z V.), takze tam je jedno reseni [3; 11]. Pote dopocitam c a opakuji pro c = 18.

Dalsi moznost je resit to graficky a reseni generovat nahodnym vzorkovanim pres obdelnikovou obalku vysledneho utvaru.

[xsubway]

Malé zjednodušení zadání:

Řešil bych to vypuštěním podmínek pro výsledek. Oba parametry vygeneruji podle podminek, pak výpočítám výsledek.

Zobrazím jeden parametr a výsledek a ptám se na druhý parametr. Zobrazovat mohu více výsledků, ale jen jeden bude správný, ostatní mohou být generované ...