Markiyan Hirnyk

Markiyan Hirnyk
9 years, 127 days


These are Posts that have been published by Markiyan Hirnyk

I would like to pay attention to an article by David Austin "The Stable Marriage Problem and School Choice"

Here is its inroduction:

" Every year, 75,000 New York City eighth graders apply for admission to one of the city's 426 public high schools. Until recently, this process asked students to list five schools in order of preference. These lists were sent to the schools, who decided which applicants to accept, wait-list, or reject. The students were then notified of their status and allowed to accept only one offer and one position on a waiting list. After the students had responded to any offers received, schools with unfilled positions made a second round of offers, and this process continued through a concluding third round.

This process had several serious problems. At the end of the third round of offers, nearly half of the students, usually lower-performing students from poor families, had not been accepted into a school. Many of these students waited through the summer only to learn they had been matched with a school that was not on their list of five schools.

This process also encouraged students and their parents to think strategically about the list of schools they submitted. Students that were rejected by the school at the top of their list might find that their second-choice school had no vacancies in the second round of offers. This made it risky for many students to faithfully state their true preferences, a view encouraged by the Education Department's advice that students "determine what your competition is" before creating their lists of preferred schools.

Lastly, schools would often underrepresent their capacity hoping to save positions for students who were unhappy with their initial offerings.

In the end, the process couldn't place many students while it encouraged all parties, both students and schools, to strategically misrepresent themselves in an effort to obtain more desirable outcomes not possible otherwise. Widespread mistrust in the placement process was a natural consequence.

Using ideas described in this column, economists Atila Abdulkadiroglu, Parag Pathak, and Alvin Roth designed a clearinghouse for matching students with high schools, which was first implemented in 2004. This new computerized algorithm places all but about 3000 students each year and results in more students receiving offers from their first-choice schools. As a result, students now submit lists that reflect their true preferences, which provides school officials with public input into the determination of which schools to close or reform. For their part, schools have found that there is no longer an advantage to underrepresenting their capacity.

The key to this new algorithm is the notion of stability, first introduced in a 1962 paper by Gale and Shapley. We say that a matching of students to schools is stable if there is not a student and a school who would prefer to be matched with each other more than their current matches. Gale and Shapley introduced an algorithm, sometimes called deferred acceptance, which is guaranteed to produced a stable matching. Later, Roth showed that when the deferred acceptance algorithm is applied, a student can not gain admittance into a more preferred school by strategically misrepresenting his or her preferences.

This column will present the game-theoretic results contained in the original Gale-Shapley paper along with Roth's subsequent analysis. Pathak calls the deferred acceptance algorithm "one of the great ideas in economics," and Roth and Shapley were awarded the 2012 Nobel Prize in economics for this work"

It would be nice to realize that in Maple.

 

 

The William Lowell Putnam Mathematical Competition, often abbreviated to the Putnam Competition, is an annual mathematics competition for undergraduate college students enrolled at institutions of higher learning in the world (regardless of the students' nationalities). One can see some problems and answers here. I find it remarkable that a lot of these problems can be done with Maple. Here is a sample (The DirectSearch package should be downloaded from http://www.maplesoft.com/applications/view.aspx?SID=101333 and installed in your Maple.).

 

rsolve({a(k)=a(k-1)^2-2,a(0)=5/2},a)#2014,A-3

NULL

rs := unapply(rsolve({a(0) = 5/2, a(k) = a(k-1)^2-2}, a), k)

proc (k) options operator, arrow; 2*cosh(arccosh(5/4)*2^k) end proc

(1)

(2)

evalf(product(1-1/rs(k), k = 0 .. infinity))

.4285714286

(3)

identify(%)

3/7

(4)

sol := solve({1/x-1/(2*y) = 2*(-x^4+y^4), 1/x+1/(2*y) = (x^2+3*y^2)*(3*x^2+y^2)}, explicit)

sol[1]; evalf(sol)

{x = 1.122865470, y = .1228654698}, {x = -0.39087502e-2+.3661111372*I, y = -1.003908750+.3661111372*I}, {x = .6924760152-.5923802638*I, y = -.3075239848-.5923802638*I}, {x = .6924760152+.5923802638*I, y = -.3075239848+.5923802638*I}, {x = -0.39087502e-2-.3661111372*I, y = -1.003908750-.3661111372*I}, {x = .3469845126+.1168520057*I, y = 0.3796751170e-1+1.067908527*I}, {x = .7773739670+.4755282581*I, y = .4683569607-.4755282736*I}, {x = .2183569726+.2938926261*I, y = 1.027373941-.2938926802*I}, {x = .3469845126+1.067908522*I, y = 0.3796751830e-1+.1168520056*I}, {x = -.2120324818+.8862728900*I, y = .5969845187+.2984876419*I}, {x = -.3494002531+.8416393955*I, y = -.6584172547-.1094171332*I}, {x = -.2120324818+.2984876377*I, y = .5969845144+.8862728969*I}, {x = -.9084172475+.6600037635*I, y = -0.9940025307e-1+0.7221851120e-1*I}, {x = -.3494002531+.1094171208*I, y = -.6584172336-.8416394020*I}, {x = -.9084172475+0.7221851117e-1*I, y = -0.9940025050e-1+.6600037719*I}, {x = -.9084172475-0.7221851117e-1*I, y = -0.9940025050e-1-.6600037719*I}, {x = -.3494002531-.1094171208*I, y = -.6584172336+.8416394020*I}, {x = -.9084172475-.6600037635*I, y = -0.9940025307e-1-0.7221851120e-1*I}, {x = -.2120324818-.2984876377*I, y = .5969845144-.8862728969*I}, {x = -.3494002531-.8416393955*I, y = -.6584172547+.1094171332*I}, {x = -.2120324818-.8862728900*I, y = .5969845187-.2984876419*I}, {x = .3469845126-1.067908522*I, y = 0.3796751830e-1-.1168520056*I}, {x = .2183569726-.2938926261*I, y = 1.027373941+.2938926802*I}, {x = .7773739670-.4755282581*I, y = .4683569607+.4755282736*I}, {x = .3469845126-.1168520057*I, y = 0.3796751170e-1-1.067908527*I}

(5)

plots:-implicitplot([1/x+1/(2*y) = (x^2+3*y^2)*(3*x^2+y^2), 1/x-1/(2*y) = 2*(-x^4+y^4)], x = 0 .. 2, y = 0 .. 1, color = [red, blue], gridrefine = 4)

 

"http://kskedlaya.org/putnam-archive/  and https://en.wikipedia.org/wiki/William_Lowell_Putnam_Mathematical_Competition"

Re(convert(int(ln(x+1)/(x^2+1), x = 0 .. 1), polylog))

(1/8)*Pi*ln(2)

(6)

Im(convert(int(ln(x+1)/(x^2+1), x = 0 .. 1), polylog))

0

(7)

NULL

DirectSearch:-GlobalOptima(int(sqrt(x^4+(-y^2+y)^2), x = 0 .. y), {y = 0 .. 1}, maximize)

[.333333333333333, [y = HFloat(0.9999999999999992)], 96]

(8)

rsolve({T(0) = 2, T(1) = 3, T(2) = 6, T(n) = (n+4)*T(n-1)-4*n*T(n-2)+(4*n-8)*T(n-3)}, T)

GAMMA(n+1)+2^n

(9)

floor(10^20000/(10^100+3))

9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999997000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000899999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999730000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000080999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999975700000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000007289999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999997813000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000656099999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999803170000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000059048999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999982285300000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000005314409999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999998405677000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000478296899999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999856510930000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000043046720999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999987085983700000000000000000000000000000000000000000000000000000000000000000000000000000000000000000003874204889999999999999999999999999999999999999999999999999999999999999999999999999999999999999999998837738533000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000348678440099999999999999999999999999999999999999999999999999999999999999999999999999999999999999999895396467970000000000000000000000000000000000000000000000000000000000000000000000000000000000000000031381059608999999999999999999999999999999999999999999999999999999999999999999999999999999999999999990585682117300000000000000000000000000000000000000000000000000000000000000000000000000000000000000002824295364809999999999999999999999999999999999999999999999999999999999999999999999999999999999999999152711390557000000000000000000000000000000000000000000000000000000000000000000000000000000000000000254186582832899999999999999999999999999999999999999999999999999999999999999999999999999999999999999923744025150130000000000000000000000000000000000000000000000000000000000000000000000000000000000000022876792454960999999999999999999999999999999999999999999999999999999999999999999999999999999999999993136962263511700000000000000000000000000000000000000000000000000000000000000000000000000000000000002058911320946489999999999999999999999999999999999999999999999999999999999999999999999999999999999999382326603716053000000000000000000000000000000000000000000000000000000000000000000000000000000000000185302018885184099999999999999999999999999999999999999999999999999999999999999999999999999999999999944409394334444770000000000000000000000000000000000000000000000000000000000000000000000000000000000016677181699666568999999999999999999999999999999999999999999999999999999999999999999999999999999999994996845490100029300000000000000000000000000000000000000000000000000000000000000000000000000000000001500946352969991209999999999999999999999999999999999999999999999999999999999999999999999999999999999549716094109002637000000000000000000000000000000000000000000000000000000000000000000000000000000000135085171767299208899999999999999999999999999999999999999999999999999999999999999999999999999999999959474448469810237330000000000000000000000000000000000000000000000000000000000000000000000000000000012157665459056928800999999999999999999999999999999999999999999999999999999999999999999999999999999996352700362282921359700000000000000000000000000000000000000000000000000000000000000000000000000000001094189891315123592089999999999999999999999999999999999999999999999999999999999999999999999999999999671743032605462922373000000000000000000000000000000000000000000000000000000000000000000000000000000098477090218361123288099999999999999999999999999999999999999999999999999999999999999999999999999999970456872934491663013570000000000000000000000000000000000000000000000000000000000000000000000000000008862938119652501095928999999999999999999999999999999999999999999999999999999999999999999999999999997341118564104249671221300000000000000000000000000000000000000000000000000000000000000000000000000000797664430768725098633609999999999999999999999999999999999999999999999999999999999999999999999999999760700670769382470409917000000000000000000000000000000000000000000000000000000000000000000000000000071789798769185258877024899999999999999999999999999999999999999999999999999999999999999999999999999978463060369244422336892530000000000000000000000000000000000000000000000000000000000000000000000000006461081889226673298932240999999999999999999999999999999999999999999999999999999999999999999999999998061675433231998010320327700000000000000000000000000000000000000000000000000000000000000000000000000581497370030400596903901689999999999999999999999999999999999999999999999999999999999999999999999999825550788990879820928829493000000000000000000000000000000000000000000000000000000000000000000000000052334763302736053721351152099999999999999999999999999999999999999999999999999999999999999999999999984299571009179183883594654370000000000000000000000000000000000000000000000000000000000000000000000004710128697246244834921603688999999999999999999999999999999999999999999999999999999999999999999999998586961390826126549523518893300000000000000000000000000000000000000000000000000000000000000000000000423911582752162035142944332009999999999999999999999999999999999999999999999999999999999999999999999872826525174351389457116700397000000000000000000000000000000000000000000000000000000000000000000000038152042447694583162864989880899999999999999999999999999999999999999999999999999999999999999999999988554387265691625051140503035730000000000000000000000000000000000000000000000000000000000000000000003433683820292512484657849089280999999999999999999999999999999999999999999999999999999999999999999998969894853912246254602645273215700000000000000000000000000000000000000000000000000000000000000000000309031543826326123619206418035289999999999999999999999999999999999999999999999999999999999999999999907290536852102162914238074589413000000000000000000000000000000000000000000000000000000000000000000027812838944369351125728577623176099999999999999999999999999999999999999999999999999999999999999999991656148316689194662281426713047170000000000000000000000000000000000000000000000000000000000000000002503155504993241601315571986085848999999999999999999999999999999999999999999999999999999999999999999249053348502027519605328404174245300000000000000000000000000000000000000000000000000000000000000000225283995449391744118401478747726409999999999999999999999999999999999999999999999999999999999999999932414801365182476764479556375682077000000000000000000000000000000000000000000000000000000000000000020275559590445256970656133087295376899999999999999999999999999999999999999999999999999999999999999993917332122866422908803160073811386930000000000000000000000000000000000000000000000000000000000000001824800363140073127359051977856583920999999999999999999999999999999999999999999999999999999999999999452559891057978061792284406643024823700000000000000000000000000000000000000000000000000000000000000164232032682606581462314678007092552889999999999999999999999999999999999999999999999999999999999999950730390195218025561305596597872234133000000000000000000000000000000000000000000000000000000000000014780882941434592331608321020638329760099999999999999999999999999999999999999999999999999999999999995565735117569622300517503693808501071970000000000000000000000000000000000000000000000000000000000001330279464729113309844748891857449678408999999999999999999999999999999999999999999999999999999999999600916160581266007046575332442765096477300000000000000000000000000000000000000000000000000000000000119725151825620197886027400267170471056809999999999999999999999999999999999999999999999999999999999964082454452313940634191779919848858682957000000000000000000000000000000000000000000000000000000000010775263664305817809742466024045342395112899999999999999999999999999999999999999999999999999999999996767420900708254657077260192786397281466130000000000000000000000000000000000000000000000000000000000969773729787523602876821942164080815560160999999999999999999999999999999999999999999999999999999999709067881063742919136953417350775755331951700000000000000000000000000000000000000000000000000000000087279635680877124258913974794767273400414489999999999999999999999999999999999999999999999999999999973816109295736862722325807561569817979875653000000000000000000000000000000000000000000000000000000007855167211278941183302257731529054606037304099999999999999999999999999999999999999999999999999999997643449836616317645009322680541283618188808770000000000000000000000000000000000000000000000000000000706965049015104706497203195837614914543357368999999999999999999999999999999999999999999999999999999787910485295468588050839041248715525636992789300000000000000000000000000000000000000000000000000000063626854411359423584748287625385342308902163209999999999999999999999999999999999999999999999999999980911943676592172924575513712384397307329351037000000000000000000000000000000000000000000000000000005726416897022348122627345886284680807801194688899999999999999999999999999999999999999999999999999998282074930893295563211796234114595757659641593330000000000000000000000000000000000000000000000000000515377520732011331036461129765621272702107522000999999999999999999999999999999999999999999999999999845386743780396600689061661070313618189367743399700000000000000000000000000000000000000000000000000046383976865881019793281501678905914543189676980089999999999999999999999999999999999999999999999999986084806940235694062015549496328225637043096905973000000000000000000000000000000000000000000000000004174557917929291781395335151101532308887070928208099999999999999999999999999999999999999999999999998747632624621212465581399454669540307333878721537570000000000000000000000000000000000000000000000000375710212613636260325580163599137907799836383538728999999999999999999999999999999999999999999999999887286936215909121902325950920258627660049084938381300000000000000000000000000000000000000000000000033813919135227263429302214723922411701985274518485609999999999999999999999999999999999999999999999989855824259431820971209335582823276489404417644454317000000000000000000000000000000000000000000000003043252722170453708637199325153017053178674706663704899999999999999999999999999999999999999999999999087024183348863887408840202454094884046397588000888530000000000000000000000000000000000000000000000273892744995340833777347939263771534786080723599733440999999999999999999999999999999999999999999999917832176501397749866795618220868539564175782920079967700000000000000000000000000000000000000000000024650347049580675039961314533739438130747265123976009689999999999999999999999999999999999999999999992604895885125797488011605639878168560775820462807197093000000000000000000000000000000000000000000002218531234462260753596518308036549431767253861157840872099999999999999999999999999999999999999999999334440629661321773921044507589035170469823841652647738370000000000000000000000000000000000000000000199667811101603467823686647723289448859052847504205678488999999999999999999999999999999999999999999940099656669518959652894005683013165342284145748738296453300000000000000000000000000000000000000000017970102999144312104131798295096050397314756275378511064009999999999999999999999999999999999999999994608969100256706368760460511471184880805573117386446680797000000000000000000000000000000000000000001617309269922988089371861846558644535758328064784065995760899999999999999999999999999999999999999999514807219023103573188441446032406639272501580564780201271730000000000000000000000000000000000000000145557834293068928043467566190278008218249525830565939618480999999999999999999999999999999999999999956332649712079321586959730142916597534525142250830218114455700000000000000000000000000000000000000013100205086376203523912080957125020739642457324750934565663289999999999999999999999999999999999999996069938474087138942826375712862493778107262802574719630301013000000000000000000000000000000000000001179018457773858317152087286141251866567821159227584110909696099999999999999999999999999999999999999646294462667842504854373814157624440029653652231724766727091170000000000000000000000000000000000000106111661199647248543687855752712667991103904330482569981872648999999999999999999999999999999999999968166501640105825436893643274186199602668828700855229005438205300000000000000000000000000000000000009550049507968252368931907017744140119199351389743431298368538409999999999999999999999999999999999997134985147609524289320427894676757964240194583076970610489438477000000000000000000000000000000000000859504455717142713203871631596972610727941625076908816853168456899999999999999999999999999999999999742148663284857186038838510520908216781617512476927354944049462930000000000000000000000000000000000077355401014542844188348446843727534965514746256921793516785161120999999999999999999999999999999999976793379695637146743495465946881739510345576122923461944964451663700000000000000000000000000000000006961986091308855976951360215935478146896327163122961416510664500889999999999999999999999999999999997911404172607343206914591935219356555931101851063111575046800649733000000000000000000000000000000000626578748217797037925622419434193033220669444681066527485959805080099999999999999999999999999999999812026375534660888622313274169742090033799166595680041754212058475970000000000000000000000000000000056392087339601733413306017749077372989860250021295987473736382457208999999999999999999999999999999983082373798119479976008194675276788103041924993611203757879085262837300000000000000000000000000000005075287860564156007197541597416963569087422501916638872636274421148809999999999999999999999999999998477413641830753197840737520774910929273773249425008338209117673655357000000000000000000000000000000456775907450774040647778743767526721217868025172497498537264697903392899999999999999999999999999999862967227764767787805666376869741983634639592448250750438820590628982130000000000000000000000000000041109831670569663658300086939077404909608122265524774868353822811305360999999999999999999999999999987667050498829100902509973918276778527117563320342567539493853156608391700000000000000000000000000003699884850351269729247007824516966441864731003897229738151844053017482489999999999999999999999999998890034544894619081225897652644910067440580698830831078554446784094755253000000000000000000000000000332989636531614275632230704206526979767825790350750676433665964771573424099999999999999999999999999900103109040515717310330788738041906069652262894774797069900210568527972770000000000000000000000000029969067287845284806900763378587428179104321131567560879029936829441608168999999999999999999999999991009279813646414557929770986423771546268703660529731736291018951167517549300000000000000000000000002697216055906075632621068704072868536119388901841080479112694314649744735209999999999999999999999999190835183228177310213679388778139439164183329447675856266191705605076579437000000000000000000000000242749445031546806935896183366558168250745001165697243120142488318477026168899999999999999999999999927175166490535957919231144990032549524776499650290827063957253504456892149330000000000000000000000021847450052839212624230656502990235142567050104912751880812823948662932355200999999999999999999999993445764984148236212730803049102929457229884968526174435756152815401120293439700000000000000000000001966270504755529136180759085269121162831034509442147669273154155379663911968089999999999999999999999410118848573341259145772274419263651150689647167355699218053753386100826409573000000000000000000000176964345427997622256268317674220904654793105849793290234583873984169752077128099999999999999999999946910696371600713323119504697733728603562068245062012929624837804749074376861570000000000000000000015926791088519786003064148590679881418931379526481396121112548658575277686941528999999999999999999995221962673444064199080755422796035574320586142055581163666235402427416693917541300000000000000000001433411197966780740275773373161189327703824157383325650900129379271774991824737609999999999999999999569976640609965777917267988051643201688852752785002304729961186218467502452578717000000000000000000129007007817010266624819603584507039493344174164499308581011644134459749264226384899999999999999999961297897654896920012554118924647888151996747750650207425696506759662075220732084530000000000000000011610630703530923996233764322605633554400975674804937772291047972101377433780374640999999999999999996516810788940722801129870703218309933679707297558518668312685608369586769865887607700000000000000001044956763317783159661038789034507019896087810732444399506194317489123969040233717689999999999999999686512971004665052101688363289647894031173656780266680148141704753262809287929884693000000000000000094046108698600484369493491013105631790647902965919995955557488574021157213621034592099999999999999971786167390419854689151952696068310462805629110224001213332753427793652835913689622370000000000000008464149782874043593254414191179506861158311266932799636000173971661904149225893113288999999999999997460755065137786922023675742646147941652506619920160109199947808501428755232232066013300000000000000761773480458663923392897277206155617504248014023951967240015657449571373430330380196009999999999999771467955862400822982130816838153314748725595792814409827995302765128587970900885941197000000000000068559613241279753105360754948554005575382321262155677051601409170461423608729734217640899999999999979432116027616074068391773515433798327385303621353296884519577248861572917381079734707730000000000006170365191715177779482467945369860501784408913594010934644126825341528124785676079587680999999999998148890442485446666155259616389041849464677325921796719606761952397541562564297176123695700000000000555332867254366000153422115083287445160596802223460984117971414280737531230710847162891289999999999833400139823690199953973365475013766451820959332961704764608575715778740630786745851132613000000000049979958052892940013807990357495870064453712200111488570617427285266377810763976244660216099999999985006012584132117995857602892751238980663886339966553428814771814420086656770807126601935170000000004498196224760364601242719132174628305800834098010033971355568455673974002968757862019419448999999998650541132571890619627184260347611508259749770596989808593329463297807799109372641394174165300000000404837660228432814111844721895716547522075068820903057422001161010657660267188207581747750409999999878548701931470155766446583431285035743377479353729082773399651696802701919843537725475674877000000036435389420558953270066024970614489276986756193881275167980104490959189424046938682357297536899999989069383173832314018980192508815653216903973141835617449605968652712243172785918395292810738930000003279185047850305794305942247355304034928808057449314765118209404186327048164224481412156778320999999016244485644908261708217325793408789521357582765205570464537178744101885550732655576352966503700000295126654306527521487534802261977363143592725170438328860638846376769434334780203327094110048889999911462003708041743553739559321406791056922182448868501341808346086969169699565939001871766985333

(10)

int(exp(-1985*(t+1/t))/sqrt(t), t = 0 .. infinity)

(1/1985)*Pi^(1/2)*exp(-3970)*1985^(1/2)

(11)

l := [seq(LinearAlgebra:-Determinant(Matrix(n, proc (i, j) options operator, arrow; 1/min(i, j) end proc)), n = 1 .. 10)]

[1, -1/2, 1/12, -1/144, 1/2880, -1/86400, 1/3628800, -1/203212800, 1/14631321600, -1/1316818944000]

(12)

with(gfun):

rec := listtorec(l, u(n))

[{u(n+1)+(n^2+5*n+6)*u(n+2), u(0) = 1, u(1) = -1/2}, ogf]

(13)

rsolve(rec[1], u)

(-1)^n*(n+1)/GAMMA(n+2)^2

(14)

``

Hope the reader will try to continue the above.

Download Putnam_done_with_Maple.mw

I'd like to pay attention to the article of David Austin "How to Grow and Prune a Classification Tree"

Here is its introduction:

"

It's easy to collect data these days; making sense of it is more work. This article explains a construction in machine learning and data mining called a classification tree. Let's consider an example.

In the late 1970's, researchers at the University of California, San Diego Medical Center performed a study in which they monitored 215 patients following a heart attack. For each patient, 19 variables, such as age and blood pressure, were recorded. Patients were then grouped into two classes, depending on whether or not they survived more than 30 days following the heart attack.

Assuming the patients studied were representative of the more general population of heart attack patients, the researchers aimed to distill all this data into a simple test to identify new patients at risk of dying within 30 days of a heart attack.

By applying the algorithm described here, Breiman, Freidman, Olshen, and Stone, created a test consisting of only three questions---what is the patient's minimum systolic blood pressure within 24 hours of being admitted to the hospital, what is the patient's age, does the patient exhibit sinus tachycardia---to identify patients at risk. In spite of its simplicity, this test proved to be more accurate than any other known test. In addition, the importance of these three questions indicate that, among all 19 variables, these three factors play an important role in determining a patient's chance of surviving.

Besides medicine, these ideas are applicable to a wide range of problems, such as identifying which loan applicants are likely to default and which voters are likely to vote for a particular political party.

In what follows, we will describe the work of Breiman and his colleagues as set out in their seminal book Classification and Regression Trees. Theirs is a very rich story, and we will concentrate on only the essential ideas"

It would be interesting to compare this approach with discriminant analysis. Hope somebody of  the Maple developers will give a concrete example on this theme with Maple.

What is Groebner? That was asked in different forms several times in MaplePrimes and MathStackExchange (for example, see http://math.stackexchange.com/questions/3550/using-gr?bner-bases-for-solving-polynomial-equations ). In view of this I think the presented post on Groebner basis will be useful. This post consists of two parts: its mathematical background and examples of solutions of polynomial systems by hand and with Maple.

Let us start. Up to Wiki http://en.wikipedia.org/wiki/Gr%C3%B6bner_basis ,Groebner basis computation can be seen as a multivariate, non-linear generalization of both Euclid's algorithm for computing polynomial greatest common divisors, and Gaussian elimination for linear systems. This is implemented in Maple trough the Groebner package.
The simplest introduction to the topic I know is a well-written book of Ivan Arzhantsev (https://zbmath.org/?q=an:05864974) which includes the proofs of all the claimed theorems and the solutions of all the exercises. Here is its digest groebner.pdf done by me (The reader is assumed to be familiar with the ideal notion and ring notion (one may refresh her/his knowledge, looking in http://en.wikipedia.org/wiki/Ideal_%28ring_theory%29)). It should be noted that there is no easy reading about this serious matter.
Referring to the digest as appropriate, we solve the system
S:={a*b = c^2+c, a^2 =a+ b*c, a*c = b^2+b} by hand and with the Groebner package.
For the order a > b > c we construct its ideal
J(S):=<f1 = a*b-c^2-c,f2 = a^2-a-b*c, f3 = a*c-b^2-b>.
The link between f1 and f2 gives
f1*a-f2*b = (-c^2-c)*a + (a + b*c)*b = a*b -a*c + b^2*c -
a*c^2 =f4.
The reduction with f1 produces
f4 ->-a*c^2- a*c + b^2*c + c^2 +c =: f4.
Now the reduction with f3 produces
f4 -> -b^2- b - b*c +c^2 + c =:f4.
The link between f2 and f3 gives:
f2*c - f3*a = a*b +a*b^2 -a*c -b*c^2 = f5.
The reduction with f1 produces
f5 -> -a*c + c*b +c^2 +c =:f5.
The reduction with f3 produces
f5 -> -b^2 -b + c*b +c^2 +c =:f5.
The reduction with f4 produces
f5 -> 2b*c =: f5.
The link between f1 and f3
f1*c - f3*b = b^3 + b^2 -c^3 -c^2=:f6.
The reduction with f4 produces
f6 -> 2b*c + 2b*c^2 -2c^3 -2c^2=:f6.
At last, we reduce f6 by f5, obtaining f6:= -2c^3 -2c^2.
We see the minimal reduced Groebner basis of S consists of
a^2 -a -b*c, -b^2 -b- b*c +c^2 +c, -2c^3 - 2c^2.
Now we find the solution set of the system under consideration. The equation -2c^3 - 2c^2 = 0 implies
c=0, c=0, c=-1. The the equation -b^2 - b - b*c +c^2 + c = 0 gives
b = 0 , b = -1, b = 0, b = -1, b = 0, b = 0 respectively.
At last, knowing b and c, we find a from a^2 -a -b*c = 0.
Hence,
[{a = 0, b = 0, c = 0}, {a = 1, b = 0, c = 0}, {a = 0, b = -1, c = 0}], [{a = 0, b = 0, c = 0}, {a = 1, b = 0, c = 0}, {a = 0, b = -1, c = 0}], [{a = 0, b = 0, c = -1}].
The solution of the system under consideration by the Groebner package is somewhat different because Maple does not find the minimal reduced Groebner basis directly.

 

with(Groebner):

[b*c, a*c-c^2-c, b^2-c^2+b-c, a*b-c^2-c, a^2-a, c^3+c^2]

(1)

GB2 := remove(has, GB1, a);

[b*c, b^2-c^2+b-c, c^3+c^2]

(2)

GB3 := Basis(GB2, lexdeg([b, c]))

[b*c, b^2-c^2+b-c, c^3+c^2]

(3)

op(remove(has, GB3, {b}))

c^3+c^2

(4)

solc := solve(c^3+c^2);

-1, 0, 0

(5)

solb := [seq(op(map(`union`, [solve(eval(GB3, c = i), {b})], {c = i})), i = solc)]

[{b = 0, c = -1}, {b = -1, c = 0}, {b = 0, c = 0}, {b = -1, c = 0}, {b = 0, c = 0}]

(6)

sol := seq(op(map(`union`, [solve(eval(GB1, i))], i)), i = solb)

{a = 0, b = 0, c = -1}, {a = 0, b = -1, c = 0}, {a = 0, b = 0, c = 0}, {a = 1, b = 0, c = 0}, {a = 0, b = -1, c = 0}, {a = 0, b = 0, c = 0}, {a = 1, b = 0, c = 0}

(7)

NULL

S2 := {a*c-b^2-b, a*b-c^2-c, a^2-b*c+a}:

GB1 := Basis(S2, lexdeg([a, b, c]))

[a*c+b*c+c^2+c, b^2+b*c+c^2+b+c, a*b-c^2-c, a^2-b*c+a]

(8)

GB2 := remove(has, GB1, a)

[b^2+b*c+c^2+b+c]

(9)

sol1 := solve(GB2, b)

{b = -(1/2)*c-1/2+(1/2)*(-3*c^2-2*c+1)^(1/2)}, {b = -(1/2)*c-1/2-(1/2)*(-3*c^2-2*c+1)^(1/2)}

(10)

map(proc (c) options operator, arrow; `union`(c, sol1[1]) end proc, map(proc (C) options operator, arrow; solve(C, {a}) end proc, eval(S2, sol1[1])))

{{a = 2*c*(c+1)/(-c-1+(-3*c^2-2*c+1)^(1/2)), b = -(1/2)*c-1/2+(1/2)*(-3*c^2-2*c+1)^(1/2)}, {a = -1/2-(1/2)*(1+2*c*(-3*c^2-2*c+1)^(1/2)-2*c^2-2*c)^(1/2), b = -(1/2)*c-1/2+(1/2)*(-3*c^2-2*c+1)^(1/2)}, {a = -1/2+(1/2)*(1+2*c*(-3*c^2-2*c+1)^(1/2)-2*c^2-2*c)^(1/2), b = -(1/2)*c-1/2+(1/2)*(-3*c^2-2*c+1)^(1/2)}, {a = -(1/2)*c-1/2-(1/2)*(-3*c^2-2*c+1)^(1/2), b = -(1/2)*c-1/2+(1/2)*(-3*c^2-2*c+1)^(1/2)}}

(11)

``

 

Download groebner.mw

I'd like to pay attention to the recent article "The Misfortunes of a Trio of Mathematicians Using Computer Algebra Systems. Can We Trust in Them?"

In particular, the authors consider the integral

int(abs(exp(2*Pi*Ix)+exp(2*Pi*I*y)),[x=0..1,y=0..1]),

stating "Both Mathematica and Maple return zero as the answer to this calculation. Yet this cannot be correct, because the integrand is clearly positive and nonzero in the indicated region". Unfortunately, they give only the Mathematica command to this end.

Of course, the integral under consideration is complicated so the the simple-minded trials

int(evalc(abs(exp((2*Pi*I)*x)+exp((2*Pi*I)*y))), [x = 0 .. 1, y = 0 .. 1]);

and

VectorCalculus:-int(evalc(abs(exp((2*Pi*I)*x)+exp((2*Pi*I)*y))), [x,y]=Rectangle( 0 .. 1, 0 .. 1));

fail. However,this can be found with Maple (I think with Mathematica too.) in such a way.

 

A := evalc(abs(exp((2*Pi*I)*x)+exp((2*Pi*I)*y)))

((cos(2*Pi*x)+cos(2*Pi*y))^2+(sin(2*Pi*x)+sin(2*Pi*y))^2)^(1/2)

(1)

NULL

B := simplify(A, trig)

(2*cos(2*Pi*x)*cos(2*Pi*y)+2+2*sin(2*Pi*x)*sin(2*Pi*y))^(1/2)

(2)

op(B)[1]

2*cos(2*Pi*x)*cos(2*Pi*y)+2+2*sin(2*Pi*x)*sin(2*Pi*y)

(3)

combine(op(B)[1], x)

2*cos(2*Pi*x-2*Pi*y)+2

(4)

C := eval(B, op(B)[1] = combine(op(B)[1], x))

(2*cos(2*Pi*x-2*Pi*y)+2)^(1/2)

(5)

int(C, [x = 0 .. 1, y = 0 .. 1])

4/Pi

(6)

``

 

Download int.mw

 

 

1 2 3 4 5 6 7 Last Page 1 of 9