Keskustelu: Ohjelmointikysymykset: C++: Luonnistuisiko tällainen aloittelevalta ohjelmoijalta?

Heipähei, arvon herrasväki.

Olen 17-vuotias lukiolainen, joka on ohjelmoinnin suhteen melko kokematon. Ala-asteella ohjelmoin isän kanssa laskimen, ja ylä-asteella innostuin yrittämään yksin nettioppaiden avulla ohjelmanpätkän kasaamista, mutta se meni melkolailla tolkuttomaksi leikkaa-liimaa touhuksi.

Nyt taasen, lukion pitkän matematiikan lukuteoria ja logiikka - kurssilla sain sellaisen harhaisen käsityksen, että kuka tahansa voi oppia ohjelmoimaan. Tämän mukatiedon turvin suunnittelin itselleni jonkinasteisen tavoitteen, ohjelman, joka minun täytyisi kyetä ohjelmoimaan kevyen harjoittelukauden jälkeen.

Vaikka ohjelma tulisi oikeasti hyötykäyttöön, ehkä jopa muidenkin kuin minun käytettäväksi, otan tämän harrastuspohjalta. Ensisijainen tavoite on perustason ohjelmointitaitojen hommaaminen, toissijainen se, että ohjelmasta tulisi oikeasti olemaan jotakin hyötyä allekirjoittaneelle. Ajattelin ennen projektiin ryhtymistä kysyä, ovatko tavoitteeni liian suuria. Tällä hetkellä en ole perehtynyt asiaan juuri ollenkaan, joten en osaa sanoa vaativuudesta mitään.

Eli, kyseessä on ohjelma, jonka tulisi etsiä vajaan neljänkymmenen rivin kymmenen alkiota pitkästä taulukosta annetut alkiot. Tämä kuulostaa helpolta, mutta lisäilläänpäs pari sääntöä:
- Sama alkio voi esiintyä monella rivillä, kuitenkin tulee valita vain yksi.
- Yhdeltä riviltä voidaan valita vain yksi alkio
- Jos kaikkia rivejä ei täytetä, tulee useita kasautuneita aukkoja välttää.
- Jos kaikkia haluttuja alkioita ei näillä säännöillä voida valita, vaan tulee päällekkäisyyksiä, ohjelman tulee ilmoittaa tästä.

Lisäksi olisi pari lisätavoitetta.
- Annetun taulukon vaihtaminen tulisi olla melko helppoa.
- Haetuille alkioiolle voidaan antaa tärkeysarvo, joka määrittää sen, valitaanko se, vai joku toinen haluttu alkio tietyltä riviltä.

Oi internetmestarit, laukokaa mielipiteenne, voiko lähes alusta lähtevä ohjelmoija tavoittaa tämän projektin vaatiman tason kuukaudessa tai parissa? En kysy teiltä nyt valmiita koodinpätkiä, vaan mielipiteitä. Vasta jos (KUN) törmään ongelmiin, pommitan teitä tai isääni kysymyksillä.

Se, joka arvaa mihin ohjelmaa tullaan käyttämään saa tajuttomasti pisteitä, vaikkei se ehkä niin hankala olekaan arvata.

Tsepa kirjoitti:

lukuteoria ja logiikka - kurssilla sain sellaisen harhaisen käsityksen, että kuka tahansa voi oppia ohjelmoimaan.

En nyt sanoisi, että mitenkään harhainen käsitys. Kyllä kuka tahansa "normaali" ihminen voi oppia ohjelmoimaan. Ihan samalla kuin voi vaikka opetella pelaamaan golfia. Eli tietenkin sen eteen pitää tehdä jonkin verran verran työtä. Toiset on sitten lahjakkaampia kuin toiset, josta syystä harjoitteluun menevän työn määräkin vaihtelee. Eikä kaikista voi tullu huippuohjelmoijia ihan niin kuin kaikista ei voi tulla Tiger Woodsiakaan.

Tsepa kirjoitti:

Oi internetmestarit, laukokaa mielipiteenne, voiko lähes alusta lähtevä ohjelmoija tavoittaa tämän projektin vaatiman tason kuukaudessa tai parissa?

No, tämä riippuu tietysti siitä kuinka lahjakas olet, ja kuinka paljon aikaa ja tarmoa laitat opiskeluun. En pidä tavoitettasi kuitenkaan mitenkään mahdottomana (vaikka en ymmärräkään mihin tuota ohjelmaa käytetään :D )

Kyseinen ohjelma ei vaikuta tarvitsevan kuin ihan perustietoa vaativaa ohjelmointia. Luulisin sen tekemisen, mikäli kiinnostusta riittää, olevan mahdollista kuukauden (tai parin) opettelulla.

Itse ohjelmoinnin aloitus taitaa monella olla se suurin ongelma. Aihe tuntuu niin laajalta ja kielien syntakseja ei muista, apuakaan ei viitsi aina kysyä kun kokeneemmat ohjelmoijat ovat välillä kovin ylimielistä ja töykeää porukkaa. Lopulta kiinnostus loppuu ja monet raapaisevat hieman vain pintaa ohjelmoinnin maailmaan ja siihen se sitten jääkin.

Intensiivistä harjoittelua se vain vaatii, kuten mikä tahansa muukin asia. Motivaatiolla on kaikista suurin merkitys, toki lahjakkuus auttaa, mutta siitä tulee hukattu lahjakkuus jos motivaatiota ei ole. Mikään asia ei tule itsestään, eikä ohjelmoimaankaan opi parissa päivässä; hyväksi tuleminen vaatii monta vuotta.

Kaikista paras motivaatio syntyy, mitä yksinkertaisimpia juttuja yrittää oikeassa harjotteluvaiheessa tehdä.
Eli ei yritä juuri sen Hello worldin jälkeen tehdä omaa Half-lifeänsä. :D

Itellä passas ku nokka naamaan alkuvaihees toi PHP, ku alon värkkäämää...
1. tiedostoontallennusta huvikseni...
2. tiedostoontallennusta $_POSTista huvikseni...
3. vieraskirjaa tosissani...
4. foorumeita vieraskirjasysteemillä. :D (Tämä oli oikeasti huono ratkaisu, mutta PHP:tä tuli opittua. ;))

Edit: Siis sitä vaan halusin sanoa, et oikeasti tuon ekan projektin valinta vaikuttaa paljon tulevaisuuden motivaatioon. :D

Edit2: Anteeksi, sorruin huomaamattani hieman offtopiciin. :S

Erään tutkimuksen mukaan looginen ajattelu ja ohjelmoinnin oppiminen korreloivat aika hyvin. Jos siis lukuteorian ja logiikan lukiokurssi sujuu hyvin, olet valinnut oikein realistisen tavoitteen.

Ohjelmoinnin kannalta yksinkertainen vaihtoehto on esimerkiksi Python. Sillä pääsee helposti suoraan asiaan, kun vaikkapa C++ vaatii alkuun aika paljon ylimääräistä. Tuloksena on tietysti hieman hitaampia ohjelmia kuin C++:lla, mutta jos ongelmaasi on olemassa tehokas ratkaisu, tällä ei ole merkitystä. (Jos ohjelma on tehty huonosti ja hitaasti, C++:n käyttäminen ei missään nimessä pelasta tilannetta.)

Ohjelman toimintaa en aivan tarkkaan ymmärtänyt. Tarkoittaako rivin täyttäminen, että valitaan siltä yksi alkio? "Aukko" sitten tarkoittaisi peräkkäisiä "tyhjiä" rivejä. Millä perusteella niitä aukkoja pitäisi välttää, ts. ovatko esimerkiksi kolmen ja viiden rivin aukot pahempi asia kuin kaksi neljän rivin aukkoa?

Järkevä lähestymistapa olisi ensin selvittää, onko valinta edes mahdollinen, ja sitten etsiä paras vaihtoehto. Luvut ja tärkeysarvot voi helposti lukea tekstitiedostosta, se ei ole tässä suurin asia.

Kyseessä lienee lukion kurssitarjotin.

Hyvä esimerkki ongelmasta, jonka voi muotoilla melko selkeästi ja jonka ratkaisemisen voisi kuvitella olevan helppoa. Totuus on kuitenkin toinen. Kyseessä on nimittäin niin kutsuttu NP-täydellinen ongelma.

Näinollen voin melko varmasti sanoa, ettet pysty tekemään moista ohjelmaa (kuukaudessa), koska kukaan muukaan ei ole siinä toistaiseksi onnistunut :)

EDIT: ... siis ongelmaa ei voi ratkaista "tehokkaasti". Kuvaamassasi tapauksessa ns. brute-force-ratkaisu saattaa kuitenkin pystyä ratkaisemaan ongelman siedettävässä ajassa, jos kurssitarjotin sattuu olemaan riittävän yksinkertainen. Tällaisen tekeminen on helppoa ja voi motivoituneelta hyvinkin onnistua kuukauden harjoittelulla.

Jos kyseinen tapa on liian hidas, on käytettävä erilaisia approksimatiivisia algoritmeja (eivät etsi parasta ratkaisua, vaan "riittävän hyvän") ja hyvän tällaisen koodaaminen onkin sitten vaikeudeltaan jo aivan toisenlainen tehtävä.

os kirjoitti:

Kyseessä lienee lukion kurssitarjotin.

Pisteet tänne. Laiskana paskana, toimivana tutorina ja huomionkipeänä houkkana sain päähäni tämän idean. Olen nähnyt jo niin monen ykkösluokkalaisen kusevan valintansa täysin ja lisäksi tahdon kokeilla ohjelmointia, joten koin tämän hyväksi ideaksi.

Metabolix kirjoitti:

Ohjelman toimintaa en aivan tarkkaan ymmärtänyt. Tarkoittaako rivin täyttäminen, että valitaan siltä yksi alkio? "Aukko" sitten tarkoittaisi peräkkäisiä "tyhjiä" rivejä. Millä perusteella niitä aukkoja pitäisi välttää, ts. ovatko esimerkiksi kolmen ja viiden rivin aukot pahempi asia kuin kaksi neljän rivin aukkoa?

Nosiis, nytkun ohjelman tarkoitus on arvattu, niin kerron suoraan, lukiossamme siis yhteen jaksoon mahtuu kuusi palkkia, ja mitä tasaisemmin kurssit ovat jakautuneet jaksoille, sitä parempi. Hieman hämäävästi kyllä sanoin, Taulukko tulee siis jakaa kuuteen kuuden rivin pätkään, joissa tulee olla suurinpiirtein saman verran tyhjiä rivejä.

Kiitos kaikille palautteesta, harkitsen kyllä Pythonia, isäkin sitä tuossa suositteli.

Ja vielä. Mielestäni tuo ei ole NP-täydellinen ongelma. Ohjelma etsii kaikki haetut kurssit taulukosta, merkkaa ne. Jos se havaitsee samassa palkissa kaksi haluttua kurssia, se eliminoi toisen annettujen periaatteiden mukaisesti. (Olkoot vaikka ne tärkeysarvot, jotka voidaan johtaa siitä, onko kurssi pakollinen vai ei, kuinka monta niitä esiintyy, ja onko käyttäjä itse painottanut niitä).

Ja lisäksi, riittäisi että ohjelma vie prosessin niin pitälle kuin pystyy. Eli tässä tapauksessa ohjelma:
1) Eliminoi kurssit joita ei haluta
2) Valitsee kurssit, joita järjestetään vain kerran ja eliminoi muut mahdolliset saman palkin käyttävät kurssit.
3 ja eteenpäin) Lisää eliminointia joidenkin tulevaisuudessa keksittävien periaatteiden mukaisesti

Lopputuloksena ei ole valmiit valinnat, vaan valintojen tekoa helpottava uusi kurssitarjotin, josta kaikki turha on riisuttu. Tämäkin helpottaisi käyttäjäkuntaa.

Jo nuo kaksi optimointiaskelta tosiaan pienentävät valikoimaa aika paljon. Kolmas triviaali vaihe on valita kaikki ne kurssit, jotka jäävät yksin palkkeihinsa. Kun kurssi on valittu, sen voi poistaa puuttuvien listasta. Algoritmia voi vielä ajaa uudestaan, kunnes se ei enää saa tarjotinta pienennettyä.

Jos jaksaa tehdä vielä kunnollisen käyttöliittymän, seuraava askel on päästää käyttäjä lukitsemaan johonkin palkkiin haluamansa kurssi, jolloin äskeinen algoritmi pystyy taas karsimaan vaihtoehtoja.

(Käyttöliittymän kannalta yksi harkittava vaihtoehto on nettisivun tekeminen. Tällöin ohjelman voi kirjoittaa joko palvelimelle esimerkiksi PHP:llä tai suoraan nettisivulle JavaScriptilla.)

Tuo on kyllä erittäin hyvä harjoitusprojekti.

Metabolix kirjoitti:

Jo nuo kaksi optimointiaskelta tosiaan pienentävät valikoimaa aika paljon. Kolmas triviaali vaihe on valita kaikki ne kurssit, jotka jäävät yksin palkkeihinsa. Kun kurssi on valittu, sen voi poistaa puuttuvien listasta. Algoritmia voi vielä ajaa uudestaan, kunnes se ei enää saa tarjotinta pienennettyä.

Jos jaksaa tehdä vielä kunnollisen käyttöliittymän, seuraava askel on päästää käyttäjä lukitsemaan johonkin palkkiin haluamansa kurssi, jolloin äskeinen algoritmi pystyy taas karsimaan vaihtoehtoja.

Tuo on kyllä erittäin hyvä harjoitusprojekti.

Aivan, juuri näin! Kiitos. Unohdin täysin, että haluttu kurssi voi olla ainoana palkissaan. Tällaista kun tapahtuu kovin harvoin oikeasti. Mutta kun valintoja tehdään, tällaiset tapaukset yleistyvät.

Tällä hetkellä järkevimmältä vaihtoehdolta tuntuu, että:

Vaihe 1: Ohjelma eliminoi ensiksi kursseja kolmen aiemmin mainitun vaiheen kautta.

Vaihe 2: Sitten laskee jonkinlaisen tärkeysarvon jäljelläoleville kursseille. Tekijöinä tässä ainakin se, kuinka monta kertaa kurssia tarjotaan vuodessa (Mitä enemmän, sitä pienempi arvo) ja kuinka monta mahdollista kurssia kyseisessä palkissa on (tämäkin kääntäen verrannollinen). Muita voisi olla vaikkapa se, onko kurssi pakollinen vai ei ja mahdollisesti käyttäjän omat painotukset. Tietenkin myös tyhjempien jaksojen kurssit saavat suuremmat arvot.

Vaihe 3: Käyttäjä valitsee kurssin. (automaattinen valinta tuottaisi ongelmia; mm. mitä tehdä, jos monella kurssilla sama tärkeysarvo)

Vaihe 4: Vaiheessa 3 valittu kurssi poistuu valittujen listalta.

Nämä vaiheet toistuvat, kunnes ollaan saatu kaikki halutut kurssit valittua. Ohjelma siis ei anna optimivaihtoehtoon, mutta johdattaa käyttäjän jossainmäärin optimoituun kurssisuunnitelmaan. Etuna tässä on se, että käyttäjä pääsee myös mukaan valintaan ja voi halutessaan esimerkiksi jättää joitakin jaksoja tyhjemmäksi kuin toisia (Kuka jaksaa istua keväällä koulussa?). Ajatus vaikuttaa toimivalta ainakin omasta mielestäni.

Tsepan kuvaama ongelma (ainakaan ilman kasautuneiden aukkojen välttämistä) kuvautuu helposti maksimaalisen parituksen (bipartite matching) ongelmaksi, johon tunnetaan tehokkaita ratkaisuja, eli ongelma ei ole NP-täydellinen. En ihan suoralta kädeltä osaa sanoa, miten tuo aukkojen välttely kannattaisi tehdä, mutta vaikea uskoa, että sekään tekisi ongelmasta NP-kovan.

Maksimaalisen parituksen ongelman täydellinen ratkaisu mahtuu tiiviisti koodattuna pariinkymmeneen riviin, mutta ratkaisun ymmärtäminen vaatii jossain määrin graafiteorian tuntemusta. En suosittele optimiratkaisun koodaamista ihan ensimmäisena harjoituksena, mutta tuo karsitun kurssitarjottimen muodostaminen on oikein hyvä lähtökohta.

Lukiossa ollessani tein vastaavan ohjelman, joka sijoitti annetut kurssit lukujärjestykseen. Se kävi läpi kaikki tavat valita kurssien paikat ja toimi riittävän nopeasti (muutamassa sekunnissa).

En tosin käyttänyt ohjelmaa itse, mutta yksi kaveri laati sillä lukujärjestyksensä ja oli tyytyväinen tulokseen.

Oho. Tulipa taas vaihteeksi puhuttua läpiä päähän. Maksimiparitushan se. Kurssit toiselle puolelle ja palkit toiselle. NP-täydellinen olikin se (koulun puolella tehtävä) oppituntien aikataulutus, johon liittyy myös sijoittelu luokkiin. Pahoittelut tästä.