Terve
Onko ideoita ohjelmalle jota ei ole vielä tehty? Oletko joskus tarvinnut jotain?
Multa on ideat loppu kun oon tehnyt jo kaiken :D.
Ohjelma, joka keksii ideoita.
Perl:lä horoskooppi scripti, eli scripti joka hakee uusimmat horoskoopit ;)
Marbo kirjoitti:
Perl:lä horoskooppi scripti, eli scripti joka hakee uusimmat horoskoopit ;)
No hohhoijaa :D
Pitänee siis ite vääntää se irssiin :(
Tee ohjelma, joka ratkaisee Sam Loyd'n "Back from the Klondike"-pulman älykkäästi.
Tee ohjelma, joka ratkaisee kauppamatkustajan ongelman polynomiaalisessa ajassa. Sellaista en ole jostain syystä vielä nähnyt. ^^ ;)
No onhan nuo haastavia.. Mutta sellainen ohjelma mistä olis vähän isompaa hyötyä.
Minun mainitsemastani olisi maailmalle erittäin suurta hyötyä, ja luultavasti niin ainutlaatuisella ohjelmalla olisi mahdollista tahkota jonkin verran rahaakin, jos pelkkä maine ja kunnia eivät riitä. Jos perehtyisit asiaan, tietäisit, miksi.
Mitä jos valitsisit jonkin yksinkertaisen lautapelin ja yrittäisit kehittää sitä pelaavan ohjelman?
JussiR kirjoitti:
Mutta sellainen ohjelma mistä olis vähän isompaa hyötyä.
Jos teet Metabolixin mainitseman ohjelman, tietojenkäsittelyn suurin avoin kysymys on ratkaistu.
Tuon Wikipedia-artikkelin muuten päättää arvoituksellinen virke:
Wikipedia: Kauppamatkustajan ongelma kirjoitti:
Ongelma on myös kognitiivisen psykologian probleema: mistä johtuu, että ihminen voi ratkaista tämän ongelman tehokkaammin kuin tietokone?
Tietääkö joku tarkemmin, miten ihminen voi ratkaista ongelman tietokonetta tehokkaammin?
Metabolix kirjoitti:
Minun mainitsemastani olisi maailmalle erittäin suurta hyötyä, ja luultavasti niin ainutlaatuisella ohjelmalla olisi mahdollista tahkota jonkin verran rahaakin, jos pelkkä maine ja kunnia eivät riitä. Jos perehtyisit asiaan, tietäisit, miksi.
Joo katsoin tuota vähän muiltakin sivuilta. Voisi vähemmän väsyneenä miettiä vähä kuinka tuon voisi tehdä.
Antti Laaksonen kirjoitti:
Wikipedia: Kauppamatkustajan ongelma kirjoitti:
Ongelma on myös kognitiivisen psykologian probleema: mistä johtuu, että ihminen voi ratkaista tämän ongelman tehokkaammin kuin tietokone?
Tietääkö joku tarkemmin, miten ihminen voi ratkaista ongelman tietokonetta tehokkaammin?
Englanninkielisessä Wikipediassa viitataan tähän: http://docs.lib.purdue.edu/jps/vol1/iss1/
Siitä vain ratkomaan kauppamatkustajan ongelmaa niin todennäköisesti ei tarvitse muutamaan vuoteen miettiä, että mitä tekisi. Sitten, jos sen ratkaiset, niin voit yleisemmin miettiä tuota P = NP ongelmaa. Yksi matematiikan kuudesta jäljellä olevasta Clay -instituutin miljoonan dollarin ongelmista. Riittää tekemistä pimeneviin syysiltoihin.
Itse aiheestakin, jos koittaisi jotain sanoa. Jos vain tuntuu, että kyvyt riittää, niin mikset menisi mukaan vaikka jonkun käyttämäsi open source -ohjelman kehitykseen. Monista isommistakin projekteista taitaa löytyä pienempiä ja helpompia bugikorjauksia tehtäväksi. Pienempien ohjelmien parista voi kyllä olla helpompi aloittaa.
Tee ohjelmia siitä mikä itseäsi kiinnostaa, vaikka olisikin olemassa parempia tai vaikka niille ei olisi järkevää käyttöä.
Lähde kurkottelemaan taivaita, niin hommaa riittää.
Tai pidä vain taukoa.
Cookin ja Levinin teoreeman ansiosta riittää ratkaista yksi NP-vaikea ongelma polynomiaalisessa ajassa, ja kaikki ratkeavat.
http://en.wikipedia.org/wiki/
Tässä on kiinnostava tuore artikkeli aiheesta. Tämä ei sisällä paljon raskasta matematiikkaa, joten se sopii myös aiheesta vasta kiinnostuneille.
http://www.americanscientist.org/issues/pub/
Eikö todellakaan kukaan ole tehnyt PC:lle ohjelmaa tuota kauppamatkustajan ongelmaa varten?
JussiR kirjoitti:
Eikö todellakaan kukaan ole tehnyt PC:lle ohjelmaa tuota kauppamatkustajan ongelmaa varten?
Ei polynomisessa ajassa toimivaa, hitaampia kyllä varmasti tuhansittain. Lukisit.
Metabolix kirjoitti:
JussiR kirjoitti:
Eikö todellakaan kukaan ole tehnyt PC:lle ohjelmaa tuota kauppamatkustajan ongelmaa varten?
Ei polynomisessa ajassa toimivaa, hitaampia kyllä varmasti tuhansittain. Lukisit.
Onhan eBay tehty juuri tuon ongelman ratkaisemiseksi.
Antti Laaksonen kirjoitti:
Tuon Wikipedia-artikkelin muuten päättää arvoituksellinen virke:
Wikipedia: Kauppamatkustajan ongelma kirjoitti:
Ongelma on myös kognitiivisen psykologian probleema: mistä johtuu, että ihminen voi ratkaista tämän ongelman tehokkaammin kuin tietokone?
Tietääkö joku tarkemmin, miten ihminen voi ratkaista ongelman tietokonetta tehokkaammin?
Tuohon wikipedian artikkeliin onkin lisätty aiheellinen puuttuva lähdemerkintä tagi. Kirjoittaja on ehkä ajatellut, että ihminen voisi intuition perusteella päätyä johonkin ratkaisuun tietokonetta nopeammin, mutta en oikein usko tähän. Solmujen määrän kasvaessa alkaa vaihtoehtojen määrä nousta erittäin nopeasti.
Metabolix kirjoitti:
JussiR kirjoitti:
Eikö todellakaan kukaan ole tehnyt PC:lle ohjelmaa tuota kauppamatkustajan ongelmaa varten?
Ei polynomisessa ajassa toimivaa, hitaampia kyllä varmasti tuhansittain. Lukisit.
Tosiaan tosiaan. Unohtu selvittää mitä polynominen aika tarkoittaa.. Nyt meni hankalammaksi :D
Ja noita NP probleemiahan on tosiaan ainakin yli 3000 tuhatta Wikipedian (http://en.wikipedia.org/wiki/List_of_NP-complete_problems) mukaan, että jos ei kauppamatkustajan ongelma kiehdo, niin sitten on muitakin mistä valita. Tosiaan kun katsoo tuotakin listaa, niin montaa erityylistä ongelmaa löytyy. Myös esim. tutut Sudoku (kun ruudukko suurenee) ja Tetris löytyvät listalta.
Noiden ratkaisusta tosin on turha haaveilla ilman kunnon yliopistotason tietämystä ja osaamista.
Ja tosiaan minustakin tuo väite, että ihminen ratkaisisi tuon kauppamatkustajan ongelman tehokkaammin, varsinkin kun solmujen määrä menee hirvittävän suureksi, kuulostaa kovin oudolta, jos solmujen määrä on kovin suuri. Tietysti jos ajatellaan, että ihminen näkee tuon verkon solmut ja niiden yhteydet piirrettynä (esim. Suomen kaupungit ja niiden väliset tiet), niin osaa hän suoraan sanoa, että ei kannata seilata äärilaidasta toiseen jatkuvasti (Rovaniemi-Helsinki-Kemi-Hanko-...) ja jonkinlaisen melko tyydyttävän ratkaisun varmaan tarjota (reaalimaailman tapauksessa, jos oikeasti pitäisi ajaa.), mutta ei välttämättä parasta. Ihminen pystyy kuitenkin pelkästään katsomalla melko helposti rajaamaan ratkaisujoukkoa, tosin mitä enemmän solmuja, niin sitä enemmän jää kuitenkin vielä vaihtoehtoja. Kone ei pysty näin "yksikertaisesti" rajaamaan noita ratkaisuita. Selviäisi varmaan enemmän, jos lukisi tuolta Jackal von ÖRF:n tarjoamasta linkistä.
Siinä jotain ajatuksen tynkää mitä mieleen tupsahti.
Päärynämies kirjoitti:
Ja noita NP probleemiahan on tosiaan ainakin yli 3000 tuhatta Wikipedian (http://en.wikipedia.org/wiki/List_of_NP-complete_problems) mukaan
Tuolla annettu luku on kylläkin 3000, eikä 3000*1000.
Hyvälle go-tekoälylle olisi käyttöä.
funktio kirjoitti:
Päärynämies kirjoitti:
Ja noita NP probleemiahan on tosiaan ainakin yli 3000 tuhatta Wikipedian (http://en.wikipedia.org/wiki/List_of_NP-complete_problems) mukaan
Tuolla annettu luku on kylläkin 3000, eikä 3000*1000.
Hups. Tosiaankin 3000 piti siihen kirjoittaa. Ilmeisesti jotenkin hassusti taas olen ajatellut. Hyvä, että muilta löytyy tarkkuutta.
PS. Meinasi tähänkin viestiin ensiksi melko autamaattisesti tulla sama virhe.
Päärynämies kirjoitti:
Tietysti jos ajatellaan, että ihminen näkee tuon verkon solmut ja niiden yhteydet piirrettynä (esim. Suomen kaupungit ja niiden väliset tiet), niin osaa hän suoraan sanoa, että ei kannata seilata äärilaidasta toiseen jatkuvasti (Rovaniemi-Helsinki-Kemi-Hanko-...) ja jonkinlaisen melko tyydyttävän ratkaisun varmaan tarjota (reaalimaailman tapauksessa, jos oikeasti pitäisi ajaa.), mutta ei välttämättä parasta.
Ongelmahan on kuitenkin nimenomaan löytää paras ratkaisu. Tietokoneellekaan ei tuota pahemmin ongelmia pullauttaa ulos jonkinlaista melko tyydyttävää ratkaisua.
Grez kirjoitti:
Päärynämies kirjoitti:
Tietysti jos ajatellaan, että ihminen näkee tuon verkon solmut ja niiden yhteydet piirrettynä (esim. Suomen kaupungit ja niiden väliset tiet), niin osaa hän suoraan sanoa, että ei kannata seilata äärilaidasta toiseen jatkuvasti (Rovaniemi-Helsinki-Kemi-Hanko-...) ja jonkinlaisen melko tyydyttävän ratkaisun varmaan tarjota (reaalimaailman tapauksessa, jos oikeasti pitäisi ajaa.), mutta ei välttämättä parasta.
Ongelmahan on kuitenkin nimenomaan löytää paras ratkaisu. Tietokoneellekaan ei tuota pahemmin ongelmia pullauttaa ulos jonkinlaista melko tyydyttävää ratkaisua.
Tosiaan, olet aivan oikeassa. Parasta ratkaisuahan on tarkoitus etsiä, pelkkä tyydyttävä ei riitä. Olisi pitänyt itse vielä selventää tuohon omaan viestiin, että kun solmujen määrä on hyvin suuri, niin aika hitaasti ihminenkään löytää sieltä sitä parasta ratkaisua (jos löytää ollenkaan), jonka löytämisestä siis ollaan kiinnostuneita.
Yksi ohjelma, mitä ei ole käsittääkseni kukaan tehnyt, on kehittää tekoäly Hinguereen.
Onhan tuo kauppatmatkustajan ongelmassa tietokone ihmistä nopeampi muutaman kymmeneen pisteeseen asti.. Brute force tyylillä ehkä 15 pisteeseen asti.
Visual Bsaicilla brute force tyylillä alle 10 pistettä alle 2sec. 11 pistettä 20 sec, 12 pistettä 300 sc, 13 pistetä 40 min.. 14 pistettä 15 tuntia.
Koska ihminen on hitaampi ainakin jos pisteet on kaikki melkein yhtä lähellä toisiaan ja niitä on paljon.
Itsekin tuota ratkaisin harjoituksen vuoksi, Javaa kun joutuu nyt opettelemaan. 10 solmun verkko ratkeaa hieman yli kahdessa sekunnissa, 11 sitten noin puolessa minuutissa. Siitä eteenpäin noillehan voi arvioita laskea. Solmujen määrän ollessa 12 on vaihtoehtojen määrä 12 -kertainen 11 solmun verkkoon nähden eli aikaakin menee noin 12-kertaisesti.
Tuota toimintaa voisi varmaan vielä optimoida rankalla kädellä. Ehkä sitä voisi harrastaa, saisi harjoitusta Javasta. Sitten vielä kiva GUI siihen päälle, niin on valmiina kiva lelu, jolla leikkiä.
Aihe on jo aika vanha, joten et voi enää vastata siihen.