Sustavna analiza grupa transformacija stanja Rubikove kocke. Rubikova kocka

"Mi vrtimo kocku, a kocka nas okreće"- tako je rekao izumitelj ove slagalice, Ernő Rubik. Ova kocka uvrće nam mozak svojom nevoljkošću da se sklopi u nekoliko sekundi. Vadimo ga gdje se može i gdje se “ne može”... Ljutimo se, nervozni, iznervirano listamo po njemu jednom, dvaput...

Sada već raširena mehanička slagalica "Rubikova kocka" prvo je nazvana "magična" ili "čarobna kocka", a u Kini je još zovu "mađarska kocka".

Izumljena je Rubikova kocka a patentirao ju je 70-ih godina 20. stoljeća mađarski kipar, profesor arhitekture i izumitelj Ernő Rubik, koji je svjetsku slavu stekao zahvaljujući svojim puzzle igračkama.

Erno Rubik predavao je industrijski dizajn i arhitekturu i volio je trodimenzionalno modeliranje objekata. Pokušavajući učenicima objasniti osnovne pojmove, došao sam do vizualnog pomagala koje je isprva izgledalo malo drugačije. Ideja i izvedba doživjele su promjene, a kao rezultat toga svijet je dobio originalnu igru ​​Rubikova kocka.

Usput, slične zagonetke bile su poznate i prije pojave Rubikove kocke. Godine 1958. izum sličan konceptu patentirao je William Gustafson, a početkom 70-ih svoje su izume predstavili Englez Frank Fock i Amerikanac Larry Nichols.
Ernő Rubik je uspio patentirati svoj izum tek početkom 1975. godine, a autorska prava su mu potvrđena 1977. godine.

Igra Rubikove kocke osvojila je sve, male i velike.
Procjenjuje se da je u svijetu prodano oko 350 milijuna Rubikovih kocki, a kada bi se poredale protezale bi se gotovo od sjevernog do južnog pola Zemlje.

Tradicionalna Rubikova kocka (3x3x3, tj. kvadratne stranice duljine 3 male kocke) sastoji se od 26 malih kockica koje se mogu okretati oko osi nevidljivih izvana. Svaki od devet kvadrata na svakoj strani kocke obojen je jednom od šest boja, obično raspoređenih u parovima jedan nasuprot drugog: bijelo-žuta, plavo-zelena, crveno-narančasta. Rotiranje stranica kocke omogućuje vam izmjenu obojenih kvadratića.

Što je bit igre?
U početku se kvadrati u boji "pomiješaju". Potrebno je okretanjem stranica kocke dovesti do stanja da se svaka strana sastoji od kvadrata iste boje. Evo što znači složiti Rubikovu kocku.
Ali uopće nije potrebno dodavati jednobojne rubove, na njima možete graditi geometrijske uzorke: "križevi", "prozori" itd.

Slaganje Rubikove kocke- nije lak zadatak!
Procjenjuje se da je broj mogućih kombinacija boja za vanjski dio Rubikove kocke 43.252.003.274.489.856.000.
Za jednostavnu igračku, Rubikova kocka je presložena.
Osamdesetih godina prošlog stoljeća ovu kocku su čak nazivali i “Gordijev čvor”.
Nažalost, većina vlasnika igračaka nikad nije uspjela sama složiti kocku.

Engleski profesor D. Singmeister smatra da osoba koja ne poznaje pravila slaganja kocke, ali zna logično razmišljati, može složiti Rubikovu kocku za dva tjedna, ako, naravno, ne zabušava.
Ali programeri, koristeći poseban kompjuterski program dokazao da se iz bilo koje početne konfiguracije kocka može riješiti u 25 poteza.

Godine 1981. objavljena je knjiga dvanaestogodišnjeg P. Bosserta "You can do The Cube" o pravilima slaganja Rubikove kocke, koja je postala bestseler. Prodano je više od milijun i pol primjeraka različiti jezici. A 1990. godine u Rusiji je objavljena knjiga koja opisuje algoritam za sastavljanje proizvoljno slojevite Rubikove kocke.

Tijekom godina ludila za Bubik kockom, ova je zabava postala čest uzrok psihičkih poremećaja. Nemogućnost rješavanja ove zagonetke dovela je do neuroza i napadaja agresije.
Poznat je slučaj kada su dresiranim majmunima dali ove kocke i pokazali im što da rade s njima. Nakon nekog vremena, majmuni, u očaju zbog nemogućnosti da ponove prikazano, počeli su pokazivati ​​iritaciju. Kao rezultat toga, jedan od majmuna bacio je ovu kocku na zid, drugi ju je pokušao pojesti, a treći ju je jednostavno slomio.
Sada je jasno zašto su neke tvrtke prodavale Rubikovu kocku u kompletu s čekićem. Nakon bezuspješnih pokušaja slaganja Rubikove kocke, neki neuravnoteženi igrači poželjeli su “kidati i bacati...”, “kidati i bacati...”

Rubikova kocka uređaj
Rubikova kocka se sastoji od 26 malih kockica i križa skrivenog unutar nje.
Osnova kocke je križ na čije je tanke osi vijcima pričvršćeno 6 središnjih kocki.
26 kocki se samo uvjetno mogu nazvati kockama, sve imaju različite zareze i šiljke.
Šest središnjih kocki nalazi se u središtu stranica velike kocke. Naslikani su samo s jedne strane s koje su vidljivi. Sve središnje kocke međusobno su povezane s tri osi, a svaki par nasuprotnih središnjih kocki može se okretati samo oko jedne svoje osi.
Osam malih kutnih kockica nalazi se na uglovima veće kocke i obojene su s tri strane. Preostalih dvanaest malih "bočnih" kockica nalazi se u sredini rubova velike kocke, također ih je potrebno obojiti samo na dvije vidljive strane.

S unutarnje strane, središnja, srednja i kutna kocka imaju različite izreze.

Središnje kocke pričvršćene su na unutarnji križ. Opruga pričvršćena na tanki kraj križa omogućuje povlačenje sloja kocki unatrag pri okretanju.

Ovako izgleda unutrašnjost lica kocke kada se skine s križa.

Vrsta kocke kojoj su uklonjene jedna strana i jedna srednja kocka.

Slaganje malih kockica temelji se na strogom redu. Kako god okreneš, kutne kocke će uvijek ostati kutne kocke, bočne kocke će uvijek ostati bočne kocke, a središnje će uvijek ostati centralne kocke. Ovo se ponekad naziva "temeljni teorem kubologije".
Središnje kocke se uopće ne mogu pomicati, pa one određuju početnu boju odgovarajućeg lica. Ako je središnja kocka na određenoj strani crvena, onda je to buduća crvena strana. Bit će crvena kada ispravno ispunite kocku.

Znaš li Kako samo ispada možeš li složiti Rubikovu kocku?
Trebate odlijepiti naljepnicu u boji s neke središnje kocke i nečim oštrim pokupiti ravni poklopac ispod nje, ukloniti je. Odvrnemo maticu, izvadimo oprugu, skinemo središnju kocku s križa, a onda samo...

Uz klasičnu troslojnu kocku (3x3x3), dostupne su pojednostavljene verzije sa stranicom duljine 2 male kocke, kao i složenije (4x4x4) i (5x5x5).
Zanimljivo je da se kocka sa stranicom 4x4 često naziva glavnom kockom ili "Rubikovom osvetom".
Inženjeri dizajna dugo vremena Nije bilo moguće izraditi verziju od šest slojeva. Sovjetski izumitelj Boris Bocharov uspio je riješiti ovaj problem. Ne znajući za Bocharovljev izum, Grk Panagiotis Verdes odlučio je upotrijebiti vlastitu metodu i objavio prve šestoslojne 2005. godine.

Godine 1972. Nijemac Uwe Meffert osmislio je igračku sličnog značenja - tetraedar. u Rusiji je takva igračka bila poznata kao "moldavska piramida", a izumio ju je neovisno o Meffertu 1981. godine inženjer A.A. Ordynets iz Kišinjeva.

Postoje i takve modifikacije Rubikove kocke. Ideja je ista, izvedba je u obliku lopte. Slagalica je u principu slična Rubikovoj kocki. Prilikom sastavljanja morate postaviti sektore iste boje. To se postiže rotiranjem 3 remena, dok su kutni trokuti nepomično fiksirani.

Dvostruki mezon Rubikova kocka 2x2x2 - hibridna slagalica napravljena od dvije Rubikove kocke. Slagalica se smatra završenom kada svako lice ima svoju boju.

Zmija- još jedna Rubikova slagalica, sastavljena od 24 identične jednakokračne trokutaste prizme međusobno povezane šarkama. Trokuti se mogu međusobno okretati na način da će, ovisno o vašoj mašti, figure nalikovati bilo kojim životinjama ili drugim figurama.

Sudokubični je hibrid Rubikove kocke i igre Sudoku. Na rubovima su nacrtani brojevi, a kocku treba presavijati tako da zbrojevi brojeva na njima budu jednaki.

Ponekad možete pronaći kocke sa slikama na licima. Tada je sastavljanje takve kocke vrlo slično dječjoj igri s kockama “Složi sliku”. Ali ne mogu ga svi odrasli sastaviti!

Svjetsko prvenstvo u slaganju Rubikove kocke održava se svake godine u Budimpešti, a državna i međunarodna natjecanja održavaju se prema posebnim pravilima. Da bi se odredilo vrijeme sastavljanja, svaki sudionik mora riješiti kocku 5 puta. Najbolji i najlošiji rezultati se odbacuju, a iz preostalih se izračunava aritmetička sredina. Ovo je izbrojivo vrijeme izgradnje. Vrijeme se mjeri točno do stotinki sekunde pomoću posebnih mjerača vremena.
Aktualni rekord u brzinskom rješavanju kocke postavio je na natjecanju 2008. Nizozemac Erik Akkersdijk: 7,08 sekundi.

Nedavno je poznati profesor Erno Rubik napravio novu zagonetku - Rubikova lopta (aka Rubikova sfera ili Rubikovih 360). Na njemu je radio tri godine.

Slagalica se sastoji od tri prozirne kugle koje se okreću oko osi i nalaze se jedna u drugoj. 6 obojenih kuglica kotrlja se unutar središnje sfere. Cilj igre je dovesti svaku kuglicu kroz rupe u sferama do utora odgovarajuće boje koji se nalazi na vanjskoj sferi.I iako se zadatak čini jednostavnim, vrlo je teško postići njegovo rješenje, čak i ako ste spretni rukama i velikom inteligencijom. Gravitacija ulazi u igru!

Nakon izuma poznate kocke, Ernő Rubik je postao najbogatiji čovjek u Mađarskoj i počeo je izmišljati druge trodimenzionalne zagonetke, a izumio je i društvenu igru ​​“Infinity”.

Početkom 80-ih Ernő Rubik postaje urednik časopisa za igre i zagonetke, a 1983. osniva vlastiti studio Rubik studio, koja je razvila zagonetke. Godine 1987. stekao je zvanje profesora. Godine 1990. osnovao je Mađarsku tehničku akademiju i bio njezin predsjednik do. Godine 1988. osnovao je međunarodnu zakladu Rubik za potporu talentiranim izumiteljima.

U Mađarskoj je 2002. godine izdana prigodna kovanica u obliku kvadrata. Godina na kovanici je 1975. (ove godine je primljen patent za Rubikovu kocku) i prikazuje poznatu kocku.

Ernő Rubik trenutno je uključen u razvoj videoigara i vodi Rubik Studio. Primljen kao član najprestižnijeg nizozemskog puzzle društva na svijetu, broj 0.

Kao što je poznato, broj moguća stanja Rubikova kocka je jednaka
43.252.003.274.489.856.000 (43 kvintilijuna 252 kvadrilijuna 3 bilijuna 274 milijarde 485 milijuna 856 tisuća). Odakle dolazi ova brojka? A evo odakle dolazi:
(broj rasporeda rebrastih kocki) x
x(broj postavljanja kutnih kocki) x
x (broj kombinacija rotacija rubnih kocki) x
x (broj kombinacija rotacija kutnih kocki).

Postoje i središnje kocke, ali one su uvijek na svojim mjestima, a njihova se orijentacija (za kocku s jednoličnom bojom svake strane) može zanemariti.

U Rubikovoj kocki ima 12 oštrih kocki, što znači da se prva kocka može postaviti na 12 mjesta, druga kocka na 11 mjesta, kocka 3 na 10 mjesta, četvrta na 9 mjesta i tako sve do zadnje. To jest, broj SVIH rasporeda rubnih kocki jednak je
12 * 11 * 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 479001600.
Ovo se piše kao 12! (12-faktorijel).

Faktorijel broja n (latinski factorialis - djeluje, proizvodi, množi; označava se s n!, izgovara se en factorial) umnožak je svih prirodnih brojeva od 1 do uključivo n.

Slično, računamo broj SVIH rasporeda kutnih kocki. Ima ih 8, što znači
8! = 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 40320.

Sada izbrojimo SVIH kombinacija rotacija rebrastih kockica. Svaka od 12 rubnih kocki može imati samo 2 orijentacije - 0 i 180 stupnjeva, dakle 2 na 12. potenciju = 4096.

Na isti način izračunavamo broj svih orijentacija kutnih kocki: 3 na 8. potenciju = 6561.

Čini se da možete pomnožiti dobivena 4 broja i sve je spremno. Ali nije to tako jednostavno. Do sada će brojka biti puno veća. Odrežemo višak.

Ako se kocke pomaknu iz ispravnog položaja samo dopuštenim okretajima (a ne fizičkim rastavljanjem i ponovnim sastavljanjem cijelog uređaja ili ponovnim bojanjem lica), tada ne može doći do situacije u kojoj:

1. sve srednje kocke su na svojim mjestima i samo je jedna od njih krivo okrenuta;
2. sve srednje kocke stoje i pravilno su okrenute, a sve kutne kocke, osim dvije, stoje (u bilo kojem položaju) na svojim mjestima;
3. sve srednje kocke stoje i pravilno su okrenute, a sve kutne kocke stoje na svojim mjestima i samo je jedna od njih pogrešno okrenuta.

Za svakoga koga zanima odakle su izvedena takva svojstva, preporučam pročitati članak “Matematika čarobne kocke” V. Dubrovskog u časopisu “Kvant” br. 8 za 1982. i članak “Mađarska kocka sa šarkama” u br. 12. za 1980. u istom časopisu, autori - V. Zalgaller i S. Zalgaller. . Ako nikada niste bili matematičar, ne preporučam čitanje, jer ćete se oduševiti. Dakle, vjerujte mi na riječ.

U skladu s prvim svojstvom, ne može se rotirati samo jedna rubna kocka, što znači da nećemo uzeti u obzir ni njezinu orijentaciju. Stoga dijelimo 2 na 12. potenciju s 2, što je jednako 2 na 11. potenciju. Dobivamo 2048.

Na temelju trećeg svojstva, prema kojem se samo jedna kutna kocka ne može netočno rotirati (što znači zanemariti njezinu orijentaciju), prilagodit ćemo izračun svih orijentacija kutnih kocki na minimum koji je potreban. Odnosno, dijelimo s 3, ili pišemo 3 na 7. potenciju, što je ekvivalentno. Rezultat će biti 2187.

Pa, zadnja prilagodba temelji se na drugom svojstvu. Prekida nemoguće permutacije. Odnosno, ako smo već postavili 6 od 8 kutnih kockica na njihova mjesta (u bilo kojoj orijentaciji), tada će posljednje 2 sigurno doći na svoje mjesto. Sjećate se kako smo izračunali položaj kutova? (Od 8 mogućih mjesta za prvu kocku do jednog mjesta za posljednju kocku.) Dakle, množitelji za posljednje kocke sada se mogu zanemariti. Podijelimo 8! s 2, dobivamo 20160.

Dakle, sada razumijete što i odakle je došlo u ovoj formuli, što znači da možete sigurno pomnožiti dobivene brojeve:
12! * 8!/2 * 2 11 * 3 7 = 12! * 8! * 2 10 * 3 7 .
Još uvijek možete proširiti 12! i 8! prostim brojevima, tada dobivamo
2 27 * 3 14 * 5 3 * 7 2 * 11 = 43252003274489856000.
Ili jednostavno pomnožite unaprijed izračunata 4 broja:
479001600 * 20160 * 2048 * 2187 = 43252003274489856000.

Izračunajmo sada koliko će mogućih stanja imati Rubikova kocka, uzimajući u obzir rotacije središnjih kockica (sredina). Kao što znate, ima ih 6 (u kocki dimenzija 3x3x3) i svaki od njih se može rotirati za 0, 90, 180 i 270 (ili minus 90) stupnjeva, odnosno imati 4 moguća položaja. Stoga je broj mogućih kombinacija centara 4 na 6. potenciju. Ali u kocki je nemoguće imati stanje u kojem je, kada je kocka potpuno sastavljena, samo jedna središnja kocka rotirana za 90 stupnjeva (u bilo kojem smjeru), stoga za posljednju središnju kocku od šest uzimamo u obzir samo dvije položaji - 0 i 180 stupnjeva. Dobivamo
(4 6)/2=(2 2) 6 /2=2 12 /2=2 11 = 2048 mogućih kombinacija.

Sada množenjem ovog broja s brojem kombinacija uglova i rubova koji su nam poznati, dobivamo:
2048 * 43252003274489856000 = 88580102706155225088000.

Dakle, broj kombinacija Rubikove kocke 3x3x3, uzimajući u obzir orijentaciju središnjih kocki, je
2 11 * 2 27 * 3 14 * 5 3 * 7 2 * 11 = 2 38 * 3 14 * 5 3 * 7 2 * 11=
=88,580,102,706,155,225,088,000 (88 sekstilijuna 580 kvintilijuna 102 kvadrilijuna 706 bilijuna 155 milijardi 255 milijuna 88 tisuća).

U posljednje vrijeme ima puno kocki s dizajnom (ili dizajnom) na rubovima. Ako ste kupili jednu od ovih za sebe, onda ćete sigurno imati situaciju da središnje kocke budu pogrešno orijentirane. Da biste riješili takvu kocku, morate znati (na njenom mjestu, naravno).

Pošaljite svoj dobar rad u bazu znanja jednostavno je. Koristite obrazac u nastavku

Studenti, diplomanti, mladi znanstvenici koji koriste bazu znanja u svom studiju i radu bit će vam vrlo zahvalni.

Objavljeno na http://www.allbest.ru/

MINISTARSTVO OBRAZOVANJA I ZNANOSTI UKRAJINE

Nacionalno zrakoplovno sveučilište nazvano po. NE. Žukovski

"Kharkovski zrakoplovni institut"

NASTAVNI RAD

u disciplini: “Osnove sistemske analize”

na temu: SUSTAVSKA ANALIZA GRUPA TRANSFORMACIJA STANJA RUBIKOVE KOCKE

Kharkov - 2014

Uvod

1.1 Relevantnost rada

1.2 Stablo problema

1.3 Stablo ciljeva

3.4.1 Thistlethwaiteov algoritam

3.4.2 Kotsembaov algoritam

Zaključak

Bibliografija

Primjena

Uvod

Rubikova kocka jedna je od najpopularnijih slagalica na svijetu. Stvorio ga je 1975. godine Erne Rubik (Rubik Ernh), mađarski izumitelj, kipar i profesor arhitekture.

Godine 1971. Ernő je imenovan nastavnikom na Akademiji primijenjenih umjetnosti. Između ostalih predmeta predavao je trodimenzionalno modeliranje. Prema jednoj verziji, koristeći ovo pomoć u nastavi Rubik je studentima pokušao objasniti osnove matematičke teorije grupa. Zadatak izumitelja bio je sljedeći: natjerati pojedinačne raznobojne kocke da se slobodno okreću na svojim mjestima bez narušavanja strukturalnog jedinstva cijelog uređaja.

Samom izumitelju trebalo je mjesec dana da sastavi kocku nakon što je napravio prvi model.

U sljedećih 40 godina vodeći matematičari i programeri pokušavali su pronaći najkraći algoritam za slaganje Rubikove kocke. U ovom trenutku, najkraći algoritam nije pronađen.

Prvo poglavlje ovog rada daje pregled literature i donosi zaključke na temelju rezultata pregleda izvora informacija. Prikazano je stablo problema i stablo ciljeva te je definirana svrha istraživanja. Određuje se predmet istraživanja, daju se dokazi da je predmet istraživanja objekt sa stajališta analize sustava. Određen je predmet istraživanja.

Drugo poglavlje sadrži analizu predmeta istraživanja. Dane su strukturne, funkcionalne, informacijske i klasifikacijske vrste analize proučavanog objekta.

U trećem poglavlju obrazlaže se izbor modela prikaza predmeta istraživanja. Date su ulazne i izlazne veličine, te osnovne jednadžbe koje opisuju predmet proučavanja.

U zaključku su izneseni zaključci, prijedlozi i preporuke te je prikazan praktični značaj rada.

defragmentacija rubikova kocka matematički

1. Analiza sustava transformacijskih grupa stanja Rubikove kocke

1.1 Relevantnost rada

Rubikova kocka je plastična kocka razbijena u 27 podudarnih kockica. Unutarnja kocka je uklonjena, a 26 vanjskih kocki spojeno je tako da se bilo koja strana od 9 kocki susjedna jednoj strani kocke može rotirati u bilo kojem smjeru za 900. Nakon rotacije od 900, cijeli sustav zadržava istu slobodu rotacije: opet, bilo koje lice u bilo kojem smjeru može se rotirati za 900 u svojoj ravnini.

U početku je svaka strana velike kocke obojena u svoju boju (crvena, narančasta, žuta, zelena, plava, bijela). Nakon niza nasumično odabranih rotacija, boja lica kocke postaje šarolika: na rubovima se nalaze ćelije različitih boja. Rješenje zagonetke je korištenje rotacija za postizanje originalnog rasporeda kockica, tj. takav raspored u kojem će svaka strana kocke opet biti iste boje.

“John Conway, jedan od vodećih svjetskih teoretičara grupa, ili jedan od njegovih kolega na Cambridgeu, definirao je najkraći put od bilo kojeg stanja natrag do početnog stanja kao Božji algoritam.

Broj kombinacija kockica koje se mogu dobiti rotiranjem stranica (izračunato je da ih ima N = 43.252.003.274.489.856.000, tj. više od 43 kvintilijuna) čini je nedostupnom gruboj sili čak i na računalu. Može se primijetiti da se svaka kombinacija ne može dobiti rotiranjem stranica kocke: ako dopustite da se kocka rastavi na svojih 26 kockica, tada možete napraviti 12N = 529024039393878272000 različitih kombinacija.

1.2 Stablo problema

Glavni problem ovog rada može se podijeliti na podprobleme i prikazati u obliku problemskog stabla (vidi sliku 1.1).

1. Poteškoće sekvencijalne obrade svih mogućih različitih stanja Rubikove kocke

1.1. Složenost konstruiranja grafa stanja za Rubikovu kocku

1.1.1. Ograničene mogućnosti grafičkih urednika i alata za vizualizaciju grafa stanja Rubikove kocke

1.2. Ograničeni računalni resursi

1.2.1. Ograničen kapacitet digitalnih medija

Slika 1.1 -- Stablo problema

1.3 Stablo ciljeva

Glavni cilj ovog rada može se podijeliti na podciljeve i predstaviti u obliku stabla ciljeva (vidi sliku 1.2).

1. Istražite mogućnost stvaranja algoritama i formulirajte preporuke za optimizaciju broja transformacija između početnog i ciljanog stanja Rubikove kocke

1.1. Optimizacija na grupi transformacija stanja Rubikove kocke

1.1.1. Primjena metoda teorije grupa

1.2. Potražite algoritam za pronalaženje optimalnog rješenja

1.2.1. Proučavanje i analiza algoritama za transformaciju stanja Rubikove kocke

Slika 1.2 -- Stablo ciljeva

Svrha rada je istražiti mogućnost stvaranja algoritama i formulirati preporuke koje omogućuju optimizaciju broja transformacija između početnog i ciljanog stanja Rubikove kocke.

Predmet proučavanja - stanja Rubikove kocke.

Predmet istraživanja - Grupe transformacija stanja Rubikove kocke

Metode istraživanja:

· Obrada postojećih informacija;

· Analiza postojećih algoritama.

Glavni ciljevi studije:

· Provođenje morfološke, funkcionalne, informacijske i klasifikacijske analize predmeta istraživanja;

· Proučavanje algoritama za transformaciju stanja Rubikove kocke;

· Određivanje glavnih čimbenika koji utječu na optimizaciju grupa transformacija Rubikove kocke.

2. Opis sustava za trodimenzionalni vizualizator procesa defragmentacije (Rubikova kocka) sa stajališta analize sustava

2.1 Strukturni opis sustava

Razmotrimo strukturu sustava Rubikove kocke (slika 2.1) i njegova svojstva sa stajališta analize sustava.

Slika 2.1 - Struktura Rubikove kocke

Svojstva sustava:

1) Pojava

Središnji mehanizam - dizajniran za spajanje 26 podudarnih kocki za kontrolu rotacije lica

Kocke - odredite položaj indikatora boja na svakoj plohi

Svaki od sustava obavlja svoju funkciju, ali njihova kombinacija potiče vizualizaciju proces korak po korak defragmentaciju bez ugrožavanja integriteta cijelog uređaja.

2) Integritet

Kada se sve središnje kocke uklone iz sustava, rubne i kutne kocke više nisu kontrolirane središnjim mehanizmom i sustav prestaje postojati

3) Aditivnost

Prijelaz sustava u nulto stanje provodi se uzastopnim rotacijama lica kocke.

4) Sinergija

Rotacija jedne plohe uzrokuje istovremenu promjenu položaja i orijentacije u prostoru devet kocki koje pripadaju rotirajućoj plohi.

5) Progresivna sistematizacija

Proces slaganja Rubikove kocke je želja za cjelovitošću premaz u boji svako lice

6) Izomorfizam

Sve središnje, rubne i kutne kocke slične su strukture (unutar grupe).

Vrsta elementarnog sastava - mješoviti tip. Kocke su iste vrste elemenata, a istovremeno se razlikuju od središnjeg mehanizma.

Vrsta elementa je stvarna.

Vrsta veza između elemenata je informacijska.

Vrsta strukture - hijerarhijska.

Uobičajeno, Rubikova kocka može se prikazati kibernetičkim modelom, gdje je (x1, ..., xn) vektor ulaza objekta, a (y) izlaz.

2.2 Funkcionalni opis sustava

Funkcionalni opis sustava je opis glavne funkcije koju sustav obavlja i funkcija podsustava i elemenata ovog sustava, s naznakom parametara sustava, podsustava i elemenata. Funkcionalni opis također sadrži strukturni opis sustava, opis čimbenika koji razaraju i koji stvaraju sustav.

Strukturni opis sustava:

1. Rubikova kocka

1.1. Centralni mehanizam

1.1.1. Debelo rame križa

1.1.2. Tanka os križa

1.1.2.1. Perilica

1.1.2.2. Proljeće

1.1.2.3. vijak

1.2. Kocke

1.2.1. Središnji

1.2.1.1. Obojeni slojevi

1.2.2. Costal

1.2.2.1. Obojeni slojevi

1.2.3. Kutak

1.2.3.1. Obojeni slojevi

Funkcije sustava i njegovih podsustava prikazane su u tablici 2.1

Tablica 2.1 - Funkcionalni opis sustava

Parametri sustava i njegovih podsustava prikazani su u tablici 2.2

Tablica 2.2 - Parametri podsustava i elemenata

Ukupno i ukupan broj funkcija

· Funkcije prve razine - 1

· Funkcije druge razine - 2

· Funkcije treće razine - 5

· Funkcije četvrte razine - 4

Opće karakteristike sustavi prikazani su u tablici 2.3

Tablica 2.3 - Opće karakteristike sustava

2.3 Informacijski opis sustava

Opis informacija trebao bi dati ideju o organizaciji i upravljanju sustavom. Ovo je najviše Potpuni opis, budući da opisuje sustav koji je već u procesu njegovog funkcioniranja. Informacijski opis utvrđuje ovisnost morfoloških i funkcionalnih svojstava sustava o kvaliteti i količini unutarnjih (o sebi i o okolini) i vanjskih (koje dolaze iz vanjske okoline) informacija.

Princip rada objekta istraživanja

Slike 2.2, 2.4 i 2.5 prikazuju unutarnji križ, rubnu kocku i kutnu kocku. Slika 2.3 prikazuje pričvršćenje središnje kocke na unutarnji križ

Slika 2.6 prikazuje unutrašnjost lica uklonjenog s križa.

Slika 2.7 prikazuje Rubikovu kocku kojoj je uklonjena jedna strana i jedan rub.

Radi veće jasnoće, na slikama 2.6 i 2.7, središnje kocke, rubne kocke, kutne kocke i unutarnji križ obojeni su u različite boje. Ova boja nema nikakve veze s obojenim slojevima na vanjskim rubovima kocki.

Na slikama 2.6 i 2.7 možete vidjeti kako se izbočine na rubnim i kutnim kockama presavijaju u gotovo cilindričnu izbočinu s unutarnje strane lica velike kocke, a na srednjem sloju nastaje cilindrično prstenasto udubljenje. Rotacija lica odgovara rotaciji cilindrične izbočine u cilindričnom udubljenju.

Uloga opruge 4 (slika 2.2) je da može lagano povući rotirajuću površinu prilikom okretanja.

Slika 2.2

Popis elemenata sustava:

1) debelo rame križa - 1;

2) tanka os križa - 6;

3) podloška - 6;

4) proljeće - 6;

5) matica - 6;

6) središnje kocke - 6;

7) rebraste kocke - 12;

8) kutne kocke - 8;

9) slojevi u boji -54 (9 komada x 6 boja).

Svojstva dijelova elementa prikazana su u tablici 2.4

Tablica 2.4 - Svojstva dijelova elemenata sustava

Geometrijska sredina broja svojstava po elementu:

Struktura objekta prikazana je na slici 2.3

Slika 2.3 - Grafikon sustava

Sustavne veze između elemenata sustava:

1) Povezivanje

3. Kutne kocke - središnja kocka

4. Rebraste kocke - središnja kocka

5. Centralna kocka - podloška

6. Kutna kocka - preljevi u boji

7. Rebrasta kocka - preljevi u boji

8. Središnja kocka - prekrivač u boji

10. Opruga - matica

11. Matica - tanka os križa

12. Tanka os križa - debeli krak križa

2) Transformativni

1. Vanjsko okruženje(korisnik) - kutne kocke

2. Vanjska okolina (korisnik) - rebraste kocke

9. Podloška - opruga

Broj priključaka po elementu sustava prikazan je u tablici 2.5

Tablica 2.5 - Broj priključaka po elementu

Geometrijski srednji broj veza po elementu:

Određujemo broj kvanta prostora koji zauzimaju elementi (tablica 2.6).

Kvantum prostora elementa vi je volumen pravokutnog paralelopipeda koji omeđuje dati element.

Volumen prostora postojanja elemenata V je volumen kocke s bridom jednakim zbroju maksimalnih dimenzija elemenata.

Broj kvanta: =

Tablica 2.6 - Broj kvanta prostora koje zauzimaju elementi

Geometrijska sredina broja kvanti prostora:

2.4 Klasifikacijski opis sustava

Klasifikacija je podjela skupa objekata na

klase prema najbitnijim karakteristikama.

Rezultati klasifikacije sustava prikazani su u tablici 2.7.

Tablica 2.7 - klasifikacija sustava prema kriterijima klasifikacije

3. Modelni prikaz predmeta istraživanja

3.1 Osnovne jednadžbe koje opisuju predmet proučavanja

Za označavanje redoslijeda rotacija lica Rubikove kocke 3X3X3, koristi se "Singmaster notacija", koju je razvio David Singmaster i objavio 1981. godine.

Slova L, R, F, B, U, D označavaju rotaciju lijeve, desne, prednje, stražnje, gore i dolje strane za 90° u smjeru kazaljke na satu. Rotacije od 180° označavaju se dodavanjem broja 2 desno od slova ili dodavanjem nadnarednog broja 2 desno od slova. Rotacija od 90° u smjeru suprotnom od kazaljke na satu označava se dodavanjem prazna slova (?) ili nadnarednog znaka -1 s desne strane slova. Tako, na primjer, L2 i L2 zapisi; L? i L-1 su ekvivalentni.

Postoje dva najčešća načina mjerenja duljine rješenja (metrike). Prva metoda - jedan korak (potez) rješenja smatra se zakretanjem lica za 90° (četvrtokretni, QTM). Prema drugoj metodi, pola okreta lica (faceturnmetric, FTM, ponekad se naziva i HTM - half-turnmetric) također se računa kao 1 potez. Prema tome, F2 (rotiranje prednje strane za 180°) treba računati kao dva poteza u QTM metrici ili kao 1 potez u FTM metrici.

Kako bi se u tekstu označila duljina niza za metriku koja se koristi, koristi se zapis koji se sastoji od brojeva broja poteza i malog prvog slova oznake metrike. Dakle, 14f znači "14 poteza u FTM metrici", a 10q znači "10 poteza u QTM metrici". Zvjezdica se koristi za označavanje da je broj poteza minimalan u danoj metrici: 10f* označava optimalnost FTM rješenja s 10 poteza.

3.2 Ulazne i izlazne veličine

Ulazne veličine su sva moguća stanja Rubikove kocke. Jedina izlazna vrijednost je nulto (prikupljeno) stanje.

3.3 Proučavanje transformacija stanja Rubikove kocke korištenjem matematičke teorije grupa

Države - razne opcije Sklopovi Rubikove kocke koji nastaju kada se 8 kutnih kocki nasumično postavi duž vrhova kocke i 12 rubnih kocki duž rubova. Središnje kocke u svim stanjima nalaze se na isti način - isto kao u nultom stanju, kada je svaka strana kocke obojena istom bojom. Ako se stanje S2 može dobiti iz stanja S1 pomoću neke operacije, tada se može ići iz S2 u S1 mijenjanjem smjera svakog od zavoja i izvođenjem obrnutim redoslijedom. U ovom slučaju stanja S1 i S2 su povezana.

Da biste u potpunosti opisali stanje Rubikove kocke, potrebno je za svaku malu kocku naznačiti mjesto koje zauzima i njenu orijentaciju na tom mjestu. Svaka kutna kocka može se postaviti na isto mjesto na tri načina, a rubna kocka na dva načina.

Neka je Rubikova kocka u nultom stanju. Prenumerirajmo njezine vrhove i kutne kocke koje se nalaze u njima brojevima od 1 do 8, a bridove i odgovarajuće rubne kocke brojevima od 1 do 12. Osim toga, na svakom rubu velike kocke izabrat ćemo određeni smjer (vektor ).

Sada se lokacija i-tog kuta (j-te sredine) kocke u stanju S može specificirati brojem yS(i) (φS(j)) vrha (brida) gdje se nalazi (i = 1. .8, j = 1. .12).

Da biste postavili orijentaciju kutnih kocki, odaberite par suprotnih stranica velike kocke, na primjer njezine vodoravne strane. Da budemo precizni, pretpostavimo da je gornja kocka plava, a donja zelena. Svaka kutna kocka ima jednu stranu plave boje, ili jedan zeleni rub. Kut b (b = 00, 1200 ili 2400) za koji ovu kocku treba zakrenuti u svom položaju oko dijagonale velike kocke u smjeru suprotnom od kazaljke na satu tako da ova ploha (plava ili zelena) postane vodoravna, nazvat ćemo kutom rotacije ove kocke kutna kocka u stanju S i oko srednje vrijednosti bS(i), gdje je i broj kocke.

Orijentacija j-te bridne kocke u stanju S bit će određena kutom inS(i) između vektora brida na kojem se kocka treba nalaziti i vektora brida na kojem se nalazi (φS(j ) th ruba). Kut inS(i) može biti 00 ili 1800; nazvat ćemo ga kutom zakreta j-te rubne kocke u stanju S.

Pogledajmo kako se karakteristike stanja bS, bS, fS i yS mijenjaju kada se plohe rotiraju. Lako je provjeriti da:

1) Kutovi rotacije kutnih kocki se ne mijenjaju kada se četiri okomite plohe zakrenu za 1800 i kada se vodoravne plohe proizvoljno zakrenu.

2) Kutovi rotacije rubnih kocki se ne mijenjaju kada se dvije suprotne plohe zakrenu za 1800 i kada se preostale plohe proizvoljno zakrenu.

3) Kada se bilo koja okomita strana rotira za ±900, 1200 se dodaje kutovima rotacije bs dviju kocki koje stoje na njezinim suprotnim vrhovima, a 2400 se dodaje kutovima rotacije dviju drugih kutnih kocki.

4) Kada rotirate desnu ili lijevu plohu za ±900, mijenjaju se kutovi rotacije sve četiri rubne kocke ove plohe.

Odavde odmah slijedi da su zbrojevi zakretnih kutova svih kutnih i svih bridnih kocki

A(S) = bS(1) + bS(2) + … + bS

B(S) = inS(1) + inS(2) + … + inS

ostaju konstantni za sve rotacije lica. Takve karakteristike stanja nazivamo invarijantama. Vrijednosti bilo koje invarijante za dva vezana stanja S1 i S2 se podudaraju. Stoga su jednakosti A(S1) = A(S2) i B(S1) = B(S2) potrebne uvjete povezanosti država. Dodavanjem njima slične jednakosti za drugu invarijantu dobivaju se dovoljni uvjeti.

Permutacija konačnog skupa je svako preslikavanje tog skupa na samog sebe. Dakle, funkcija us definirana na skupu (1, …, 8) je permutacija tog skupa, a φS je permutacija skupa (1, …, 12). Svaka operacija F također je pridružena dvjema permutacijama φF i yF istih skupova: ako se nulto stanje S0 prenese operacijom F u stanje S, tada je, po definiciji, yS(i) = yF(i), φF(j ) = φS(j). Drugim riječima, yF(i) i φF(j) su brojevi onih mjesta koja su kao rezultat operacije F zauzeta kutnom kockom koja stoji na i-to mjesto, a rebrasta kocka stoji na j. mjestu.

Izvršivši jednu za drugom permutacije y1 i y2 istog skupa, ponovno dobivamo njegovo preslikavanje na sebe - permutaciju y. Zove se kompozicija permutacija y1 i y2: y = y1 _ y2.

Neka je y proizvoljna permutacija skupa (1, 2, …, n). Nacrtajmo dvije linije od n točaka jednu ispod druge. Ako, kada se y preuredi, broj i ide u j, povezujemo i-ta točka gornja linija sa segmentom sa j-ta točka dno - dobivamo graf permutacije od y. Označimo s N(y) broj točaka presjeka segmenata grafa (točku u kojoj se sijeku više od dva segmenta računamo onoliko puta koliko ima pari segmenata koje sadrži). Permutacija y se zove parna (neparna) ako je broj N(y) paran (neparan). Predznak permutacije y definiramo jednakošću e(y) = (-1) N(y). e(y) je jednak 1 ili -1 ovisno o tome je li permutacija parna ili neparna. Otkrijmo kako parnost sastava y1 _ y2 ovisi o paritetima y1 i y2. Kompozicijski graf konstruira se vrlo jednostavno: kombiniramo donju liniju permutacijskog grafa y1 s gornjom linijom grafa y2 - dobivamo međugraf, a zatim svaku izlomljenu liniju u međugrafu zamijenimo segmentom koji povezuje njegove krajeve . Broj točaka sjecišta izlomljenih linija u međugrafu jednak je N(y1) + N(y2). Prilikom ispravljanja, broj točaka sjecišta isprekidanih linija može se smanjiti, ali će paritet ostati.

Dakle, N(y1 _ y2) i N(y1) + N(y2) su brojevi iste parnosti; prema tome, e(y1 _ y2) = (-1) N(y1 _ y2) = (-1) N(y1) + N(y2)= (-1) N(y1) × 1N(y2) = e( y1) _ e(y2). Drugim riječima, sastav dviju permutacija je paran ako su im pariteti isti, a neparan je u suprotnom.

Pretpostavimo da permutacija skupa od n elemenata ostavlja n - m elemenata fiksnim, a preostalih m elemenata možemo poredati tako da prvi od njih ide u drugi, drugi u treći, i-ti u (i+1)-ti, i m-ti element- opet na prvu. Tada se permutacija naziva ciklusom duljine m ili m-ciklusom.

Nazovimo predznak stanja S broj e(S) = e(yS) _ e(φS). Jednako je 1 ili -1 ovisno o tome podudaraju li se pariteti permutacija yS i φS ili ne.

Razmotrimo rotaciju F bilo kojeg lica za 900. Neka se kao rezultat ove rotacije Rubikova kocka pomakne iz stanja S u stanje S." Tada je yS" = yS _ yF, φS" = φS _ φF. Permutacije yF i φF su 4 -ciklusa, pa su neparni i e(uF) = e(fF) = -1. Dakle, e(uS") = e(uS)Č e(uF) = -e(uS), e(fS") = e(fS)Č e(φF) = -e(φS) i e(S") = e(S). Predznak stanja se ne mijenja kada se lica okreću. Ovo je treća invarijanta.

Sustav invarijanti A(S), B(S) i e(S) je potpun, odnosno podudarnost njihovih vrijednosti za dva stanja osigurava povezanost tih stanja.

3.4 Analiza nekih algoritama za rješavanje zagonetke

Prvi razvijeni algoritmi zahtijevali su 200-300 poteza (rotacija lica) da bi se kocka vratila u nulto stanje.

Postupno se smanjivala duljina algoritama (tj. minimalni broj poteza koji jamči rješenje). To se dogodilo zbog promjene redoslijeda montaže različite dijelove slagalice (poboljšanje strategije) i korištenje kraćih operacija za preslagivanje i ispravno orijentiranje kocki (poboljšanje taktike). “Slojeviti” algoritam Rubikove kocke, koji je postao najpopularniji, rješava je u najviše 108 poteza. Njegovim poboljšanjem moguće je ovaj broj smanjiti na 86 poteza. Daljnja poboljšanja zahtijevaju dramatično povećanje broja formula koje se moraju imati na umu ili na papiru tijekom procesa sastavljanja.

Istovremeno s onima koji su voljeli rješavati zagonetku držeći je u rukama, na neosvojivu kocku jurišali su i programeri. Isprva su uspjeli oni koji su uzeli malu kocku veličine 2H2H2. Problem su riješili od kraja: počevši od nultog stanja kocke, program ga počinje uništavati, primajući i pamteći rezultate različitih rotacija lica. Ako se bilo koja boja kocke ponovno pojavi, odgovarajuća operacija se zanemaruje, tako da u memoriji računala ostaju samo najkraće formule. Kao rezultat toga, dobiven je popis svih mogućih stanja male kocke, s naznakom nakon kojih se rotacija stranica prvi put pojavljuju. Ovaj popis nikada nije objavljen niti tiskan niti u jednom primjerku. Razlog nije toliko njegova enormna veličina, već činjenica da zbog svoje veličine preteško pronalaženje operacije koja vam je potrebna u ovom trenutku na popisu.

Rotirajući lica 12 puta, računalo nije pronašlo niti jedno novo stanje Male kocke. Stoga je za rješavanje zagonetke od 8 kockica uvijek dovoljno napraviti najviše 11 poteza.

Mala kocka nije ništa više od 8 kutnih kockica klasične Rubikove kocke. Ali potonji ima 26 kockica, a to komplicira zadatak sortiranja. Rubikova kocka može imati N 4,3×1019 različitih stanja.

Od programera koji su razvili algoritam za klasičnu Rubikovu kocku prvi je postigao uspjeh engleski matematičar Morvin Thistlethwaite koji je u srpnju 1981.g. razvio je algoritam koji je uvijek dopuštao slaganje Rubikove kocke u ne više od 52 poteza. Iako je u načelu Rubikovu kocku moguće složiti ručno pomoću ovog algoritma, u stvarnosti to može riješiti samo računalo. Kasnije je ovaj algoritam nešto poboljšan - prvo je to postigao sam Englez, a kasnije, u prosincu 1990. Hans Klosterman iz Nizozemske doveo je duljinu algoritma do 42 poteza. Važno je napomenuti da je ovo ograničenje opravdano striktno, a ne empirijski, tj. Dokazano je da se iz bilo kojeg stanja Rubikove kocke možete vratiti na nulu u najviše 42 poteza, a ovaj algoritam ne može jamčiti bolji rezultat. To znači da drugi algoritam ne može biti kraći. Naravno, ovaj dokaz u biti koristi računalo: za svaku fazu sklapanja izvršena je potpuna pretraga opcija, broj potrebnih poteza u najgorem slučaju uzet je kao duljina ove faze.

Nova postignuća 1992 postigao njemački matematičar Herbert Kotzemba. Bio je među onima koji su radili na maloj kocki, ali se potom pridružio programerima koji su istraživali klasičnu Rubikovu kocku. Razvio je algoritam i napisao program koji vam omogućuje da završite slagalicu u najviše 21 potezu. Ova je procjena duljine, za razliku od prethodne, empirijska: sva stanja Rubikove kocke koja su predložena Kotsembinom programu poredana su u ne više od 21 potezu.

U srpnju 2010. programer iz Palo Alta Thomas Rokicki, učitelj matematike iz Darmstadta Herbert Kozemba, matematičar iz države Kent Morley Davidson i inženjer Google Inc. John Detridge dokazao je da se svaka konfiguracija Rubikove kocke može riješiti u najviše 20 poteza. U ovom slučaju, svaka rotacija ruba smatrana je jednim potezom. Tako se pokazalo da je broj Boga u FTM metrici 20 poteza. Količina izračuna uključivala je oko 35 godina procesorskog vremena koje je donirao Google. Tehnički podaci o performansama i broju računala se ne objavljuju; Izračuni su trajali nekoliko tjedana.

U kolovozu 2014. Thomas Rokicki i Morley Davidson objavili su da je u QTM metrici Božji broj 26q.

3.4.1 Thistlethwaiteov algoritam

Thistlethwaite je koristio niz podskupina duljine 4

G0 = (L, R, F, B, U, D)

Ova grupa je ista kao grupa Rubikove kocke. Njegov je poredak

G1 = (L2, R2, F, B, U, D)

Ova podskupina uključuje sve uvjete koji se mogu riješiti bez korištenja ±90° rotacije lijeve ili desne strane. Njegov je poredak

G2 = (L2, R2, F2, B2, U, D)

Ova podskupina uključuje sve uvjete koji se mogu riješiti pod uvjetom da su rotacije četiri okomite strane za ±90° zabranjene. Njegov je poredak

G3 = (L2, R2, F2, B2, U2, D2)

Ova podskupina uključuje sve uvjete koji se mogu riješiti korištenjem samo rotacije od 180°. Njegov je poredak

Ova podskupina uključuje jedno nulto stanje.

U prvoj fazi proizvoljno zadano stanje iz skupine G reducira se na stanje koje leži u podskupini G1. Cilj druge faze je dovesti kocku u stanje u podskupini G2 bez korištenja ±90° rotacije lijeve i desne plohe. U trećoj fazi, Rubikova kocka se dovodi u konfiguraciju pripadnost grupi G3, dok su rotacije okomitih rubova za ±90° zabranjene. U završnoj, četvrtoj fazi, Rubikova kocka se potpuno slaže okretanjem strana za 180°.

Navedene skupine međustanja određuju se izračunavanjem određenih karakteristika tih stanja. Ove karakteristike, koje su sačuvane pod svim dopuštenim radnjama, matematičari nazivaju invarijantama. Svaka podskupina odgovara vlastitom skupu invarijanti i njihovim vrijednostima.

Thistlethwaite je, obavivši vrlo mukotrpan posao sortiranja algoritama, pokazao da je za prvu fazu uvijek dovoljno 7 poteza, za drugu 13, za treću 15, a za četvrtu 17. Ukupno, cijeli algoritam ne zahtijeva više od 52 poteza. Ovaj je rezultat bio mnogo bolji od svih drugih algoritama za rješavanje kocke koji su u to vrijeme mogli dati. Imao je samo jedan “nedostatak”: nikako nije pomagao pri ručnom rješavanju kocke.

3.4.2 Kotsembaov algoritam

Thistlethwaiteov algoritam poboljšao je 1992. učitelj matematike iz Darmstadta Herbert Kotzemba.

Kotsemba je smanjio broj faza algoritma na dvije

G0 = (U, D, L, R, F, B)

G1 = (U, D, L2, R2, F2, B2)

Vizualni opis grupe G1 može se dobiti izradom sljedeće oznake (Slika 3.1):

· Označite sve U i D oznake znakom “+”.

· Sve oznake na rebrastim elementima FR, FL, BL i BR označite znakom “-”.

· Ostavite sve druge naljepnice neoznačene.

Tada će sve konfiguracije grupe imati iste oznake (koje se podudaraju s oznakama na završenoj kocki).

Slika 3.1 - Međustanje Rubikove kocke u Kotsembinom algoritmu. Grupa G1

Kotsembaov algoritam, u još manjoj mjeri nego Thistlethwaiteov algoritam, može se nazvati “algoritmom sklopa” u uobičajenom smislu riječi. Samo relativno brzo računalo s velikim RAM-om može implementirati ovaj algoritam. Međutim, sama ideja je prilično jednostavna.

Cijela montaža kocke podijeljena je u 2 faze. U prvoj fazi dopuštena je svaka rotacija lica. Jedini cilj prve faze je dovesti kocku u neko "među" stanje. Čim se kocka, nakon određenog broja okretaja, nađe u međustanju, počinje druga faza. U ovoj fazi se ne koriste sve moguće rotacije ploha, već samo one koje ne uklanjaju kocku iz klase međustanja. Nulto stanje (potpuno sklopljena kocka) također pripada ovoj klasi, pa će se prije ili kasnije pronaći običnom pretragom opcija.

Ako je ukupan broj poteza potrošen na prvu i drugu fazu veći od 21, tada se program vraća na prvu fazu i preuzima sljedeće međustanje. Uštede u pretraživanju dobivene zahvaljujući ovoj ideji su ogromne: u prvoj fazi razmatraju se približno opcije, au drugoj opcije. Ukupno, program mora pogledati oko opcija, a ovaj broj je 9 redova veličine manji od ukupnog broja stanja kocke.

Kotzembin i Thistlethwaiteov algoritam imaju mnogo toga zajedničkog. Na primjer, oboje koriste koncept klase međustanja. Štoviše, Kotsembaova "međustanja" praktički se podudaraju s Thistlethwaiteovom "drugom klasom međustanja". Jedina je razlika u sustavu označavanja - Kotsemba u drugom stupnju dopušta proizvoljne rotacije U i D, te rotacije na preostalih 180 ploha, a Thistlethwaite je u svom trećem stupnju za proizvoljne rotacije ostavio lica F i B. Drugim riječima, prvi stupanj Kotsembaove metode odgovara prva dva stupnja Thistlethwaiteovog algoritma, a drugi stupanj - posljednja dva. Razlike između ovih algoritama nisu toliko uočljive, već su fundamentalnije. Naime, Thistlethwaite je dobio specifične skupove operacija i pružio rigorozne matematičke dokaze kako bi opravdao duljine svake faze koju je naznačio. A Herbert Kotsemba je, ne zamarajući se nikakvim opravdanjem, jednostavno izazvao sve amatere: možete mi poslati sve probleme koje ne možete učiniti, a moj program će ih riješiti u 20 poteza!

U stvarnosti je Kotsembaov program malo kompliciraniji od gore opisanog. Ne nabraja iscrpno opcije ni u jednoj od njegovih faza. Umjesto toga, troši neko vrijeme na izradu posebnih filtara: ogromnih nizova koji sadrže popise stanja iz kojih je u određenom broju poteza (od 1 do 8) moguće doći do konačnog (za tu fazu) stanja. Nakon početka rješavanja kocke, program pokušava završiti prvu fazu u 10 poteza. Ona čini prva dva poteza i gleda niz filtera 8 poteza. Ako se stanje ne eliminira, onda se radi treći potez i pregledava se filter za 7 poteza itd. U protivnom se radi još jedan drugi potez. Druga faza montaže provodi se točno prema istoj shemi - Kotsembaov program joj ne dodjeljuje više od 14 poteza.

Kotsembinu poruku više su puta provjeravali i razjašnjavali drugi stručnjaci. Kao rezultat toga, pokazalo se da su za obje etape procjene broja poteza koje je dao Kotsemba previše optimistične: postoje početne pozicije iz kojih je nemoguće završiti prvu etapu za manje od 12 poteza, osim toga, postoje stanja iz “srednje” klase iz koje je nemoguće prijeći na riješenu kocku u manje od 18 poteza. Navedeni brojevi 12 i 18 točne su granice: Kotsembini sljedbenici uspjeli su izvršiti potpunu potragu za 1. i 2. etapom. Tako je dokazano da Božji algoritam ima duljinu ne veću od 30 poteza.

3.4.3 CFOP metoda (metoda Jessice Friedrich)

CFOP je naziv za četiri faze montaže (slika 3.2): Cross, F2L, OLL, PLL:

1) Križ - sklop križa, četiri rebraste kocke na donjem rubu;

2) F2L (Prva dva sloja) - prva dva sloja - donji i srednji;

3) OLL (Orient the last layer) - orijentacija zadnjeg sloja;

4) PLL (Permute the last layer) - preuređivanje zadnjeg sloja.

Slika 3.2 - Četiri stupnja CFOP metode

Jedina faza za koju ne postoji jasna metodologija.

Glavni trik za sastavljanje križa je da se on mora sastaviti relativno. Na primjer, ako je križ sastavljen na bijelom rubu i na njemu je već bijelo-plava rubna kocka s bijelom bojom prema bijelom središtu, tada nije toliko važno je li plava strana te kocke poravnata s plavim rubom . Sve što trebate učiniti je postaviti zelenu i bijelu kocku suprotna strana, te bijelo-crvena i bijelo-narančasta lijevo i desno. Tijekom procesa sastavljanja, bijeli rub možete zavrnuti kako želite, a na kraju, u jednom pokretu, odmah spojite sve bočne sredine s kockama križa. Važno je samo upamtiti točan redoslijed boja na kocki: ako gledate bijelu stranu, onda se u smjeru kazaljke na satu nalaze plava, crvena, zelena, narančasta (straga žuta).

Morate staviti osam kocki na svoje mjesto: četiri kutna donja sloja i četiri rubna bočna sloja u srednjem sloju. Za početnike se odmah sastavlja par kutnih i rubnih kocki (odnosno, trebate sakupiti četiri takva para). Ovisno o početnom rasporedu kockica para, mora se primijeniti jedan ili drugi algoritam (slijed rotacija). Ukupno postoji više od 40 takvih algoritama.

Glavna poteškoća pozornice je brzo pronaći uparene kocke. Mogu biti na 16 različitih mjesta: 8 mjesta u zadnjem sloju i 8 u stupcima. Stupce je teže vidjeti, a što je manje stupaca prikupljeno, to je veća šansa da oni koji nisu sakupljeni sadrže potrebne kocke. Ako niste obratili pozornost na kocke za F2L prilikom sastavljanja križa, kada prijeđete na ovu fazu možete izgubiti puno vremena samo tražeći.

U ovoj fazi, kocke posljednjeg sloja su orijentirane tako da je zadnja strana sastavljena. Nije važno što kockice nisu na svojim mjestima: za to postoji posljednja faza.

Postoji 57 različitih početnih situacija, od kojih svaka ima svoj algoritam sastavljanja, od 6 do 14 poteza.

Završna faza montaže je postavljanje kockica posljednjeg sloja na prava mjesta. Pristup je približno sličan prethodnoj fazi, ali ovdje ima manje kombinacija i algoritama, samo 21 (13, ako računate zrcalne i inverzne kao jedan). S druge strane, nešto ih je teže identificirati, jer je ovdje potrebno uzeti u obzir različite boje, a boje na dijagramu možda se neće podudarati sa stvarnim bojama (do cikličke permutacije):

3.4.4 Glavni čimbenici koji utječu na optimizaciju grupa transformacija stanja Rubikove kocke

Podjela položaja položaja

Broj stanja Rubikove kocke podijeljen je u 2.217.093.120 grupa, od kojih svaka sadrži 19.508.428.800 različitih stanja. Jedan takav podproblem lako stane u memoriju modernog računala, a ova metoda je omogućila dosta brzo dobivanje rješenja.

1. Simetrija

Ako okrenete Rubikovu kocku lijevo-desno ili gore-dolje, tada se zapravo ništa neće promijeniti: broj koraka u rješenju ostat će isti. Umjesto rješavanja svih ovih stanja, moguće je dobiti rješenje za jedno i proširiti ga na rotirana stanja. Postoje 24 različite orijentacije u prostoru i 2 zrcalna položaja kocke za svako stanje, što vam omogućuje smanjenje broja riješenih stanja za 48 puta. Ako koristimo slično razmišljanje i upotrijebimo pretragu za problemom "pokrivanja skupa", tada se broj podzadataka smanjuje s 2.217.093.120 na 55.882.296.

2. Dobra i optimalna rješenja

Optimalno rješenje sadrži dovoljan broj koraka, ali ne više od potrebnog. Budući da je jedno stanje već poznato, što zahtijeva 20 koraka, ne morate tražiti optimalno rješenje za svako stanje, ali samo rješenja u 20 koraka ili manje. Ovo višestruko ubrzava zadatak.

3. Oprema

Za rješavanje 55.882.296 podzadataka, Google je osigurao flotu računala, a svi izračuni trajali su samo nekoliko tjedana. Google ne otkriva specifikacije računala, no za izračune je bilo potrebno 1,1 milijardu sekundi (35 godina) računalnog vremena.

Zaključak

U ovom radu razmatrana je skupina transformacija stanja Rubikove kocke.

Prikazana je relevantnost i praktični značaj rada.

Detaljno je ispitana struktura sustava. Sustav je klasificiran, kao i sljedeći opisi:

· morfološki, koji opisuje strukturu sustava, kao i svojstva svakog elementa sustava;

· funkcionalni, koji se temelji na komponentama sustava, njihovim funkcijama, ulaznim i izlaznim podacima;

· informacijski, koji daje analizu svojstava i veza svakog elementa sustava.

Proučavani su algoritmi za transformaciju grupa stanja Rubikove kocke i utvrđeni su glavni čimbenici koji utječu na optimizaciju grupa transformacija stanja Rubikove kocke.

Bibliografija

1. Jerry Slocum, David Singmaster, Wei-Hwa Huang, Dieter Gebhardt, Geert Hellings The Cube: The Ultimate Guide to the World's Bestseller Puzzle - Secrets, Stories, Solutions. - N. Y., 2009.

2. M. Evgrafov Mehanika čarobne kocke // Quantum. -- 1982. -- Broj 3. -- Str. 20-25

3. David Joyner Avanture u teoriji grupa: Rubikova kocka, Merlinov stroj i druge matematičke igračke. -- Baltimore: Johns Hopkins University Press, 2002. -- Str. 7.

4. Algoritam čarobne kocke V. Dubrovsky // Quantum. -- 1982. -- Broj 7. -- Str. 22-25.

5. Božji broj je 20 [Elektronički izvor] // URL: cube20.org

6. K. Knop Rubikova kocka: napad na uporište [Elektronički izvor]// URL: http://geocities.com/CapeCanaveral/4344/192.html

Dodatak A

CFOP algoritam (algoritam Jessice Friedrich)

Spin jezik:

F - front - prednja strana

B - leđa - stražnja strana

L - lijevo - lijeva strana

R - desno - desna strana

U - gore - gornja strana

D - dolje - donja strana

Fw - frontalni sa srednjim slojem

Bw - leđa zajedno sa srednjim slojem

Lw - lijevo zajedno sa srednjim slojem

Rw - desno zajedno sa srednjim slojem

Uw - vrh zajedno sa srednjim slojem

Dw - dno zajedno sa srednjim slojem

M - srednji sloj koji se nalazi između lijevog i desnog sloja

S - srednji sloj koji se nalazi između prednjeg i stražnjeg sloja

E - srednji sloj koji se nalazi između gornjeg i donjeg sloja

x - cijela kocka rotira od sebe duž ravnine koja kocinira s desnim slojem. To je u biti isto kao i rotirati desnu stranu kocke u smjeru kazaljke na satu zajedno s cijelom kockom.

y - cijela kocka u smjeru kazaljke na satu u horizontalnoj ravnini (gornji rub kocke je u smjeru kazaljke na satu zajedno s cijelom kockom)

z - cijela kocka u smjeru kazaljke na satu u frontalnoj ravnini (prednja strana kocke u smjeru kazaljke na satu zajedno s cijelom kockom)

Dodatak B

Primjena Rubikove kocke za objašnjenja u teoriji grupa

1. Skupovi i funkcije

Š Skup je skup elemenata od kojih se svaki pojavljuje više puta u skupu. (Konačni) skup može se eksplicitno specificirati kao popis unutar para vitičastih zagrada, na primjer (2,4,6,8) je skup parnih prirodnih brojeva manjih od 10. Sastoji se od četiri elementa. Postoje beskonačni skupovi - skupovi koji imaju beskonačan broj elemenata - kao što je skup cijelih brojeva, ali općenito se raspravlja samo o konačnim skupovima (i grupama).

Na zagonetkama često razmatramo višestruka stanja slagalice.

Š Funkcija F: AB preslikavanje skupa A u skup B je relacija koja pridružuje svaki element skupa A nekom elementu skupa B.

Korak na slagalici je funkcija na skupu stanja. Korak se primjenjuje na jedno stanje za prijelaz u drugo.

Š Funkcija F:A -> B naziva se injektivnom ako pridružuje različite elemente skupa A raznih elemenata set B.

Funkcija F:A -> B naziva se surjektivnom ako pridružuje svaki element skupa B elementu skupa A.

Funkcija F:A -> B naziva se bijektivnom ako je i injektivna i surjektivna.

Funkcija f se naziva inverzna od F (obično označena kao F-1) ako F:A -> B ima inverznu F-1:B -> A, tako da kad god je aF = b, tada je bF-1 = a

Rotacije Rubikove kocke su uvijek reverzibilne. Na primjer, korak R, rotiranje desne strane u smjeru kazaljke na satu, može se obrnuti rotiranjem desne strane u smjeru suprotnom od kazaljke na satu. Označava se kao R-1, iako je R" češći.

Š Kompozicija dviju funkcija F:A -> B i G:B -> C je funkcija koja je rezultat primjene prvo F, a zatim G. Dakle, preslikavanje elementa skupa A u element skupa C određuje se formulom = (aF) G. Ova funkcija je označena kao F? G.

Okreti se mogu kombinirati u sekvence okretanja.

Svaki niz koraka je sastav. Na primjer, ako primijenimo niz rotacija FRB na stanje S, možemo napraviti poteze jedan po jedan, što daje formulu ((SF)R)B, ili kao jednu funkciju F o R o B, što daje S (F o R o B) .

Š Funkcija identiteta IA:A ->A. AI = a je definiran za bilo koji element a iz skupa A. Lako je vidjeti da je funkcija identiteta bijektivna.

Identitet na kocki je slijed pokreta koji u konačnici ne mijenjaju stanje, npr. F2 B2 L2 R2 F2 B2 L2 R2.

2. Grupe i homomorfizmi

Š Grupa je zatvorena za množenje, to jest, ako pomnožite bilo koja dva elementa grupe, rezultat će biti element iste grupe.

Možete kombinirati dva niza poteza da biste dobili treći.

Š Postoji jedan jedini element, tj. element e u grupi je takav da za bilo koji element g u grupi vrijedi ge = eg = g.

Jedinstveni element skupine Rubikove kocke je odsutnost rotacije.

Š Svaki element ima inverz, to jest, ako je G element grupe, tada postoji element H u grupi takav da je GH = HG = e. Inverz od G je označen G-1.

Inverzni element grupe Rubikove kocke je inverzija rotacije, tj. rotacija u obrnuta strana pod istim kutom rotacije.

Š Množenje je asocijativno, odnosno ako su B i C elementi grupe, onda je (AB) C = A (BC).

Asocijativna priroda skupine Rubikove kocke je očita

Š Grupa je konačna ako ima konačan broj elemenata. Broj elemenata u grupi G naziva se red grupe i označava se sa | G|.

Broj stanja kocke je konačan, pa je stoga i broj funkcija na ovom skupu stanja također konačan. Grupa Rubikove kocke je stoga također konačna.

Postoji još jedna grupa - grupa rotacija kocke kao cjeline. Možemo postaviti bilo koje od šest lica na vrh, a zatim postoje četiri opcije za koje od susjednih lica treba postati prednje. Dakle, postoje 24 moguće orijentacije kocke. Rotacija cijele kocke je promjena između dvije takve orijentacije.

Š Redoslijed elementa g u skupini je najmanji prirodni broj N za koji je gN = e (ako takav N postoji), pri čemu eksponent gN ima prirodno značenje opetovanog množenja. Ako takav broj ne postoji, kaže se da je g beskonačnog reda. Red od g obično se označava O(G).

U konačnoj grupi svi elementi imaju konačan poredak

Grupa kocke je konačna. Ako radite bilo koju uzastopnu rotaciju, i također ih stalno ponavljate, na kraju ćete dobiti početno stanje.

3 Homomorfizam je preslikavanje F: G -> H koje svakom elementu g iz grupe G pridružuje u skladu jednoznačno određeni element h iz grupe H, ako svaki element g iz grupe G služi u ovom preslikavanju kao slika nekog element h iz grupe H, a ako za bilo koje elemente g1, g2 grupe G vrijedi jednakost (g1 · g2) F = (g1) F · (g2) F. Ako je homomorfizam jedan na jedan , tada se naziva izomorfizam.

Postoji homomorfizam od uobičajene Rubikove kocke 3 H 3 H 3 do Male kocke 2 H 2 H 2. Bilo koji korak niza na Rubikovoj kocki može se izvesti i na Maloj kocki. Stoga je svaka permutacija na pravilnoj kocki povezana s nekom permutacijom na maloj kocki. Ovo preslikavanje nije izomorfizam, jer mala kocka ima grupu koja je pojednostavljena verzija grupe veće kocke.

Objavljeno na Allbest.ru

Slični dokumenti

Značajke faktorizacije četverodimenzionalnih simplektičkih grupa. Istraživanje i analiza kompozicije geometrijskih transformacija. Karakteristike izometrije, pravilni prostori. Metode rješavanja strukturnih teorema - centri, komutante, teoremi jednostavnosti.

diplomski rad, dodan 14.02.2010


Proučavanje strukture grupa na temelju zadanih svojstava sustava njihovih podgrupa kao smjer u teoriji konačnih grupa. Pregled konačnih grupa s gustim sustavom F-subnormalnih podgrupa u slučajevima kada je F proizvoljna S-zatvorena formacija p-nilpotentnih grupa.

kolegij, dodan 07.03.2010


Grupa kao skup transformacija, zatvoren u odnosu na njihov sastav. Proučavanje nilpotentnih grupa, njihova najjednostavnija svojstva i karakteristike. Osobitosti dokazivanja teorema Sylowa, Lagrangea, Wielanda. Frattinijeva podgrupa konačne grupe je nilpotentna.

kolegij, dodan 04/10/2011


Nastanak i razvoj teorije grupa. Problem integriranja diferencijalnih jednadžbi. Algebarske konstrukcije u teoriji automata. Pojava koncepta permutacija. Skupine i klasifikacija holograma. Primjena teorije grupa u kvantna mehanika.

sažetak, dodan 08.02.2013


Rješavanje sustava linearnih jednadžbi Cramerovim, Gaussovim metodama (transformacijama koje ne mijenjaju skup rješenja sustava), matričnim metodama (nalaženjem inverzne matrice). Procjena vjerojatnosti događaja. Određivanje graničnih vjerojatnosti stanja sustava.

test, dodan 26.02.2012


Struktura konačnih grupa na temelju zadanih svojstava njihovih generaliziranih subnormalnih podgrupa. Korištenje metoda apstraktne teorije grupa i teorije formacija konačnih grupa. Subnormalne i generalizirane subnormalne podskupine i njihova svojstva. Generalizacija Hawkesovog teorema.

diplomski rad, dodan 20.12.2009


Kolmogorovljev sustav diferencijalnih jednadžbi. Rješavanje sustava algebarskih jednadžbi za konačne vjerojatnosti stanja. Grafikoni ovisnosti. Vrsta sustava čekanja temeljena na prirodi dolaznog toka i raspodjeli vremena usluge.

test, dodan 01.03.2016


Od Fourierove analize do valićne analize. Neki primjeri funkcija valićne analize u MATLAB-u. Konstrukcija poluortogonalnih spline valićnih sustava. Primjena valićnih transformacija za rješavanje integralnih jednadžbi. Wavelets paketa wavelet toolbox.

diplomski rad, dodan 04.12.2014


Bit teorije grupa. Uloga ovog pojma u matematici. Multiplikativni oblik bilježenja operacija, primjeri grupa. Formulacija suštine podskupine. Homomorfizmi grupa. Potpune i posebne grupe linearnih matrica. Klasične grupe malih dimenzija.

kolegij, dodan 06.03.2014


Opis nenilpotentnih grupa s permutabilnim generaliziranim maksimalnim podskupinama. Proučavanje grupa s X-permutabilnim I-maksimalnim podskupinama. Singulariteti grupa u kojima 2-maksimalne podskupine komutiraju s 3-maksimalne podskupine.

Datum od: 2013-12-24 Urednik: Zagumennyj Vladislav

Matematika Rubikove kocke- skup matematičkih metoda za proučavanje svojstava Rubikove kocke s apstraktne matematičke točke gledišta. Proučava algoritme za rješavanje kocke, procjenu algoritama za njezino rješavanje, itd. Temeljeno na teoriji grafova, teoriji grupa, teoriji izračunljivosti, kombinatorici.

Postoje mnogi algoritmi dizajnirani za transformaciju Rubikove kocke iz proizvoljne konfiguracije u konačnu konfiguraciju (sklopljena, sve strane su iste boje). Godine 2010. strogo je dokazano da za prijenos Rubikove kocke iz proizvoljne konfiguracije u riješenu konfiguraciju (često se taj proces naziva “sastavljanje” ili “rješavanje”) nije dovoljno više od 20 rotacija lica. Ovaj broj je promjer Cayleyeva grafa grupe Rubikove kocke. Algoritam koji rješava zagonetku u najmanjem mogućem broju poteza zove se Božji algoritam.

Božji algoritam Rubikove kocke

Povijest potrage za algoritmom Boga Rubikove kocke započela je najkasnije 1980. godine, kada je otvorena mailing lista za entuzijaste Rubikove kocke. Od tada su matematičari, programeri i samo amateri tražili Božji algoritam - algoritam koji bi omogućio praktično slaganje Rubikove kocke u minimalnom broju poteza. Povezan s ovim problemom bio je i problem određivanja Božjeg broja – broja poteza koji je uvijek dovoljan da se završi slagalica.

U srpnju 2010. programer iz Palo Alta Thomas Rokicki, učitelj matematike iz Darmstadta Herbert Kozemba, matematičar iz države Kent Morley Davidson i inženjer Google Inc. John Detridge dokazao je da se svaka konfiguracija Rubikove kocke može riješiti u najviše 20 poteza. U ovom slučaju, svaka rotacija ruba smatrana je jednim potezom. Tako se pokazalo da je broj Boga u FTM metrici 20 poteza. Količina izračuna uključivala je oko 35 godina procesorskog vremena koje je donirao Google. Tehnički podaci o performansama i broju računala se ne objavljuju; Izračuni su trajali nekoliko tjedana.

Donje granice za Božji broj

Prilično je lako pokazati da postoje rješive konfiguracije koje se ne mogu riješiti u manje od 17 poteza u FTM metrici ili 19 poteza u QTM metrici.

Ova se procjena može poboljšati uzimanjem u obzir dodatnih identiteta, na primjer, komutativnosti rotacija dviju suprotnih strana (L R = R L, L2 R = R L2, itd.) Ovaj nam pristup omogućuje dobivanje donje granice za Božji broj od 18f ili 21q.

"Superflip" - prva otkrivena konfiguracija, smještena na udaljenosti od 20f* od početne Ova procjena ostala je najpoznatija dugi niz godina. Štoviše, to proizlazi iz nekonstruktivnog dokaza, budući da ne navodi konkretan primjer konfiguracije koja zahtijeva 18f ili 21q za sastavljanje.

Jedna konfiguracija za koju se nije moglo pronaći kratko rješenje je takozvani “superflip” ili “12-flip”. "Superflip" je konfiguracija u kojoj su sve kutne i rubne kocke na svom mjestu, ali je svaka rubna kocka orijentirana u suprotnom smjeru.

Vrh koji odgovara superokretu u grafu Rubikove kocke je lokalni maksimum: svaki pomak iz ove konfiguracije smanjuje udaljenost do početne konfiguracije. To je dalo razloga za pretpostavku da je superflip na najvećoj udaljenosti od početne konfiguracije, odnosno da se radi o globalnom maksimumu.

Godine 1992. Dick T. Winter pronašao je rješenje za superflip u 20f. Godine 1995. Michael Reed dokazao je optimalnost ovog rješenja, što je rezultiralo donjom granicom za Božji broj od 20 FTM. Iste godine Michael Reed otkrio je "superflip" rješenje na 24q. Optimalnost ovog rješenja dokazao je Jerry Bryan.

Godine 1998. Michael Reed pronašao je konfiguraciju čije je optimalno rješenje bilo 26q*. Od srpnja 2013. ovaj je broj najpoznatija donja procjena Božjeg broja u QTM metrici.

Gornje granice za Božji broj

Da bi se dobila gornja granica za Božji broj, dovoljno je navesti bilo koji algoritam za rješavanje zagonetke koji se sastoji od konačnog broja poteza.

Prve gornje granice za Božji broj temeljile su se na "ljudskim" algoritmima koji su se sastojali od nekoliko faza. Dodavanje procjena odozgo za svaku fazu omogućilo je dobivanje konačne procjene reda veličine nekoliko desetaka ili stotina poteza.

Prvu specifičnu gornju granicu vjerojatno je postavio David Singmaster 1979. Njegov algoritam slaganja omogućio je slaganje Rubikove kocke u najviše 277 poteza. Singmaster je kasnije izvijestio da su Alvin Berlekamp, ​​​​John Conway i Richard Guy. razvio algoritam sklapanja koji ne zahtijeva više od 160 poteza. Ubrzo nakon toga, Conwayevi kubisti iz Cambridgea, koji su sastavljali popis kombinacija za jedno lice, pronašli su algoritam od 94 poteza.

Kiseleva Anastasia

Voditelj projekta:

Mališeva Tatjana Pavlovna

Institucija:

MBOU "Srednja škola br. 3" Konakovo, regija Tver.

izabrao sam matematički istraživački rad o Rubikovoj kocki jer Rubikovu kocku smatram ne samo igračkom, već ozbiljnim testom za misaone sposobnosti i manifestacijom upornosti onih koji je skupljaju. Rubikova kocka je igračka za um, fascinantna slagalica.

U svom istraživačkom radu (projektu) iz matematike “Rubikova kocka - dječja igračka ili složeni matematički simulator” pokušat ću proučiti Rubikovu kocku, razumjeti njenu strukturu i naučiti kako sastaviti ovu fascinantnu slagalicu.

Uvod
1. Teorijska izlaganja
1.1. Povijest stvaranja.
1.2. Algoritam sklapanja.
1.3. Sorte.
1.4. Rubikova kocka sada.
Zaključak
Popis korištene literature
Primjena

Uvod

Odabrao sam ovu temu jer Rubikovu kocku ne smatram samo igračkom, već ozbiljnim testom misaonih sposobnosti i manifestacijom ustrajnosti onih koji je slažu.

Postoje mnoge modifikacije ove igračke. Bilo bi sjajno dokučiti sve njegove tajne.

Cilj projekta: proučavati Rubikovu kocku, razumjeti njenu strukturu.

Zadatak: naučite kako sami sastaviti slagalicu.

1. Teorijska izlaganja

1.1. Povijest stvaranja.

Erne Rubik je mađarski nastavnik industrijskog dizajna i arhitekture. Dok sam izmišljao vizualno pomagalo o trodimenzionalnom modeliranju objekata za učenike, dobio sam igračku.

Probao Rubik raznih materijala- drvo, karton, papir, aplicirala sam brojeve i simbole na rubove, ali sam ipak prednost dala bojanju strana u različite boje.

Postoji legenda da mu je dizajn mehanizma sugerirao kamenčić, na mjesto središnje kocke postavio je križ oko kojeg su se ostale kocke slobodno okretale, a da se nisu raspadale.

Slagalica je bila gotova do 1974. i uspješno je testirana na studentima i prijateljima izumitelja, a više od godinu dana kasnije patentirao ju je sam izumitelj.

Masovna proizvodnja započela je krajem 1977., kada je jedna od mađarskih tvrtki oko Božića pustila probnu seriju novih slagalica. Igračka nije napustila zemlju. Srećom, zagonetka je slučajno zapela za oko poduzetniku Tiboru Lakziju koji je poslovno došao u domovinu. Zanimala ga je matematika i bavio se njezinom komercijalnom promocijom.

Tibor Lakzi: ”Kad sam prvi put vidio Erna Rubika i ponudio mu nešto novca, to mi se činilo kao milostinja. Rubik je bio grozno odjeven i pušio je jeftine cigarete. Ali već sam znao da preda mnom stoji genij. Prodat ćemo milijune slagalica, rekao sam mu.”

Igračka je završila na Sajmu igračaka u Nürnbergu, gdje je privukla pozornost engleskog izumitelja igara Toma Cramera.

Sve do 1979. Lakzi i Kremer pokušavali su zainteresirati velike proizvođače igračaka za kocku, ali su se bojali zbog njezine složenosti u izradi i sastavljanju (samom izumitelju trebalo je mjesec dana da složi slagalicu; u početku nije bio siguran hoće li je pronaći način da se to riješi).

Prve kocke bile su teške i nesigurne za korištenje; nisu ih htjeli izvoziti na Zapad. Godine 1980. pojavila se lakša i sigurnija verzija, a tada je kocka promijenila ime iz magične u Rubikova kocka. Igračka se udomaćila, samo u Mađarskoj, Portugalu i Njemačkoj slagalicu još zovu čarobna kocka, a Kinezi, koji su odbacili obje verzije imena, zovu je Mađarska kocka.

Konačno, u rujnu 1979., nakon pet dana pregovora, Ideal Toy Corporation, veliki proizvođač igračaka, bio je zainteresiran za igračku, te je potpisan ugovor o isporuci 1 milijuna kockica Americi.

Amerikanac Larry Nichols patentirao je svoju magnetsku kocku (slagalicu sličnu CD-u) u isto vrijeme kad i Rubik. Međutim, njegova igračka nije zaživjela i proizvođači su je odbili. A godinu dana kasnije, Japanac Terutochi Ichige uspio je patentirati točnu kopiju mađarske kocke u Japanu. Ali svijet nisu osvojile Nicholsova ili Terutochijeva kocka, već Rubikova kocka.

Godine 1980. kocka je imala svoj međunarodni debi, uspješno je obišla sajmove igračaka u Londonu, Parizu, New Yorku, Nürnbergu, pa čak iu Hollywoodu gdje ju je predstavljala mađarska filmska zvijezda Gabor.

Kocka je osvojila prestižnu nagradu BATR igračka godine 1980., a zatim 1981. U Engleskoj je održana ceremonija uručenja kocke princu Charlesu i Lady Diani, u čast čijeg je vjenčanja izdano posebno izdanje. Godine 1982. u Oxfordskom rječniku pojavio se unos o Rubikovoj kocki.

U dvije debitantske godine, više od 100 milijuna markiranih kockica prodano je diljem svijeta. A krivotvorina je i jedan i pol puta više, u njihovu proizvodnju uključili su se Tajvan, Kostarika, Brazil i Hong Kong.

Zbog plastične igračke u boji svijet je zahvatila masovna histerija: 1981. Patrick Bosser, 12-godišnji engleski školarac, objavio je knjigu Možete napraviti kocku sa svojom tehnologijom za rješavanje CR. Prodan je u oko milijun i pol primjeraka u sedamnaest ponovljenih izdanja i zauzeo prvo mjesto na listi bestselera godine!

U posljednjih godina Zanimanje za Cube je pomalo izblijedjelo. Nagli razvoj računalnih igara značajno je uzdrmao cijelu industriju društvenih igara i slagalica.

Sam Erno Rubik praktički je otišao u mirovinu, prodavši svoje ime američkoj tvrtki Tom Kremer 1985. Sedam gradova, doo.

1.3. Sorte.

Džepna kocka (2x2)

Rubikova kocka (3x3)

Rubikova osveta (4x4)

Profesorova kocka (5x5)

Rubikov triamid
Slagalica u obliku trodimenzionalnog trokuta (sastoji se od 10 figura u obliku dijamanta međusobno povezanih s četiri kristala).

Mađarsko prstenje.
Prototip slagalice osmislio je krajem 19. stoljeća William Churchill, a svoje su verzije predstavili i Erno Rubik (prstenovi koji se sijeku pod kutom) i Endre Pap (ravna verzija). Kod nas se zagonetka zvala "Čarobni prstenovi". Sastoji se od dva prstena spojena u obliku osmice, ispunjena raznobojnim (2-4 boje) kuglicama. Kuglice se slobodno kreću u prstenovima. Zadatak igrača bio je stvoriti kontinuirani niz loptica svake boje.
Slična slagalica, proizvedena u Njemačkoj, nazvana je Magic 8 (Magic Eight).

Rubikova zmija.
Zagonetka se može dati drugačiji oblik, budući da se sastoji od 24 prizme spojene u seriju šarkama.

Rubikova zamisao(ostale zagonetke koje je izradio Rubik).

Nepravilna Rubikova kocka.
Slagalica u obliku kocke, čiji su segmenti izrađeni u obliku različitih trapeza, može se sastaviti u trodimenzionalne raznobojne figure najbizarnijih oblika.

Kukuruz ili semafor.
Patentirao ga je Endre Pap 1982., ima cilindrični oblik, sastoji se od nizova diskova (obično 4 do 7) s rezovima koji tvore okomite utore u koje se stavljaju obojene kuglice. Diskovi se slobodno okreću jedan u odnosu na drugi, jedna kuglica nedostaje, što omogućuje zamjenu ostalih. Svrha igre- posložite kuglice tako da čine okomite redove iste boje.

Postoje dvije verzije slagalice - s kuglicama od šest različitih boja i s kuglicama koje se osim u šest osnovnih boja razlikuju i po nijansi. Druga verzija slagalice je teža, jer je potrebno izgraditi okomite redove u rastućem intenzitetu sjene.

Kocke drugih veličina.

Mezon.
Trostruki mezon (predstavlja nekoliko običnih RC međusobno povezanih na određeni način).

Kvadrat (prema načinu povezivanja i broju spojenih kockica razlikuju se: dvostruki mezon, trostruki mezon, sijamska kocka, kvartet, T-mezon, Q-mezon itd.).
Da biste to riješili, morate dovesti sva dostupna lica u svoju boju).

Ekskluzivne kocke.

Som kocka.
Prethodnik CR-a, izumio ga je švedski znanstvenik i pisac Piet Hein, prema legendi, tijekom predavanja o kvantnoj mehanici. Slagalica se sastoji od 7 pojedini dijelovi, od kojih trebate složiti kocku 3x3x3. Ima ih ukupno 240 na razne načine njezine odluke.

Kocke temeljene na društvenim igrama.

1.4. Rubikova kocka u naše vrijeme.

Američka Nacionalna zaklada za znanost dodijelila je Sveučilištu Northwestern potporu od 200.000 dolara za istraživanje Rubikove kocke. Najveći dio tih sredstava iskoristit će se za nabavu sustava za pohranu informacija ukupnog kapaciteta 20 TB. Istraživači će zabilježiti što više različitih stanja Rubikove kocke.

Metode razvijene tijekom rješavanja kombinatornih problema u budućnosti će naći primjenu u nizu područja (u poslovanju će pomoći pri optimalnom postavljanju robe na police supermarketa).

George Helm– jedan od najstrastvenijih ljudi oko zagonetki (slika iznad);
Sama kocka povremeno se izlaže u jednom ili drugom muzeju diljem svijeta, ali još nema svoj muzej, osim ako takvima ne računamo fotografije privatnih kolekcija na internetu. Možda će u budućnosti zagonetka imati svoj vlastiti punopravni muzej.

Zaključak

Učio sam o povijesti nastanka i strukturi Rubikove kocke, kao io njezinim vrstama i drugim zagonetkama, sličnim i različitim od nje, te sam savladao montažu.

Zadatak koji sam si zadao izvršio sam i savjetujem svima da ne zaustave pred poteškoćama, već da traže rješenje, jer to i nije tako teško!

Primjena

Danas postoji veliki broj varijanti i modifikacija Rubikove kocke.