[viesti Survo-keskustelupalstalla (2001-2013)]
| Kirjoittaja: | Seppo Mustonen |
|---|---|
| Sähköposti: | - |
| Päiväys: | 17.10.2007 13:12 |
Olen nyt saanut lasketuksi uudella ratkaisuohjelmallani SP_SOL avoimien, yksikäsitteisesti ratkeavien 4x5-Survo-ristikoiden lukumääräksi S(4,5)=257772, mikä vastaa aikaisempia arvioita. Laskenta tapahtui noin viikon kuluessa ja käytin siinä samanaikaisesti myös muutamia vanhempia koneitani. Jos olisin tehnyt koko työn pelkästään uusimmalla, nopeimmalla koneellani, aikaa olisi kulunut yhtäjaksoisesti noin 15.5 vuorokautta. Koska 15.5(vrk:sek)=1339200 ja sama ohjelma laskee luvun S(4,4) 37 sekunnissa, työmäärä kasvatettaessa 4x4-taulukkoa yhdellä vaivaisella rivillä kasvaa yli 36000-kertaiseksi. Jos vastaavasti nyt tähdättäisiin lukuun S(5,5), laskenta-aika tälläkin ohjelmalla olisi ainakin 36000*15.5=558000 vuorokautta eli 558000(vrk:vuosi)=1528 vuotta, mutta todellisuudessa vielä sitäkin enemmän. On siis todettava, että tarvitaan todella vielä paljon parempia ratkaisualgoritmeja, jotta voisi edes haaveilla luvun S(5,5) laskemisesta, vaikka itse luku on ehkä vain joitakin miljoonia. Tunnettujen S(m,n)-arvojen taulukko on nyt tällainen: m/n 2 3 4 5 6 7 8 9 2 1 18 62 278 1146 5706 28707 154587 3 18 38 583 5337 55815 4 62 583 5327 257772 5 278 5337 257772 6 1146 55815 7 5706 8 28707 9 154587 Oma haasteensa on yrittää edes karkeasti mallintaa esim. näiden lukujen asymptoottista käyttäytymistä tämän aineiston avulla. -Seppo
| Vastaukset: |
|---|
Survo-keskustelupalstan (2001-2013) viestit arkistoitiin aika ajoin sukrolla, joka automaattisesti rakensi viesteistä (yli 1600 kpl) HTML-muotoisen sivukokonaisuuden. Vuoden 2013 alusta Survo-keskustelua on jatkettu entistäkin aktiivisemmin osoitteessa forum.survo.fi. Tervetuloa mukaan!