Hledá se Sbírka úloh z programování (diskuse)

[xxx]

Podivej se na skripta na TIN.

[Fluttershy, yay!]

Ehm, co je to TIN?

[miro]

google

Lepsie asi bude navstivit web matematickej olympiady, kategoria P. Tam su fakt zaujimave ulohy. Popripade nejaky korespondencny seminar pre stredne skoly.

[Fluttershy, yay!]

Já použil Seznam a nic...

Koukal jsem na to a něco jsem už dělal. Díky.

[deda.jabko]

matematicke olympiady byly docela sranda... bohuzel jsem casem (po par letech) zjistil, ze nektere priklady nejspis nemely rozumne reseni... ale aspon to protocilo zavity...

[xxx]

Teoreticka informatika. Sem asi nemuzes co? Jinak nejake odkazy (zadani semestralek) jsou tam na tohle.

[Fluttershy, yay!]

Nemůžu.

Díky.

[Kyosuke]

Jednoznačně KSP.

[Fluttershy, yay!]

Děkuji mnohokrát. Jen se mi to zdá hodně matematické... no, nevadí!

[Kyosuke]

Ale programování není nic než převlečená zvláštní odnož matematiky...

[pht]

+1 KSP je formulace celkem jednoduchych VS problemu pro ty, kteri jeste nemeli poradnou vyuku algoritmu (stredoskolaci apod.) V rocenkach jsou pak i vzorova reseni, ale zajimavejsi je prihlasit se do aktualniho kola KSP a soutezit.

Nicmene KSP apod. _je_ aspon programovani, zatimco vyrobit klikatko v GTK _neni_ programovani ale remeslo.

Matematicky zapis problemu nutne neznamena ze je to mnoho matematiky. Je to jen pouziti jineho jazyka namisto cestiny.

[Radek Miček]

KSP je formulace celkem jednoduchych VS problemu

Pro složitější úlohy mohu doporučit mezinárodní olympiádu z programování

[CEST]

No, ja osobne bych asi zacal cist cizi zdrojaky, treba nejakej projekt v pythonu, velikost si vyber podle sebe. Osobne bych docela rad nakouknul do Gentoo portage, ale bohuzel jsem se k pythonu zatim nejak vic nepriblizil. A pokud se ti bude zdat, ze jsi tomu porozumnel, tak to muzes zacit treba lehce upravovat a pripadne se pripojit do projektu. Jooo,ted me napadlo!! Docela se pohnul LUMA (LDAP broser a editor). Prestoze ma pluginy Browser s editorem atributu, pak search a user management, porad se daji prevazne editovat jenom atributy, ale nenasel jsem zpusob, jak v tom browseru pridat uplne novej jakejkoliv objekt. Tak to bych si rad pridelal, ale jak jsem psal, python zatim nezvladam tak dobre, abych se v tom nejak vic vyznal. Co jsem koukal, pouzivaji se tam i objekty, ma to Qt rozhrani, takze s tim by ses mohl docela vyblbnout Tak jestli mas chut, muzes to zkusit. Vyhod oproti tem ruznym cvicenim je nekolik: realnej priklad pouziti, skutecny funkcni projekt, nepotrebujes na to znalosti matematiky (max. tak LDAP a ten je fakt docela jednoduchej, navic dulezity LDAP veci jsou uz naprogramovany), a pokud se pridas, tak to prinese uzitek a ty se naucis opravdu neco skutecnyho (a pripadne to muzes pouzit do referenci)

pamatuju, jednou jsem potreboval nejakej python upravit, neco fakt simple, nejakej debug print, jedna radka, tak jsem tam mrsknul (tusim jeste snad copy&paste) jeden radek a desne me vytocilo, kdyz to nechodilo, protoze puvodni autor pouzival k odsazeni mezery, kdezto ja mam nastaveny (mam to radsi) TABY, takze jeho 8 mezer bylo jiny odsazeni nez mych 4 tabu (pouzivam 2 mezery na tab). Tim me python dost odradil, ikdyz na nej ctu samou chvalu. Nastesti si na spoustu admin veci vystacim s perlem/awkem/sedem/grepem. A navic jsem jeste nevidel priklad python scriptu na prikazovou radku podobne jako perl -e 'skript'

[Fluttershy, yay!]

To jasně, ale mě zajímají běžné algoritmy, knihovny apod.

[CEST]

Hmmm, tak pokud ti jde o takovy veci jako treba quicksort atd, tak to bych asi moc nezkousel.

Bud to bude hodne zavisly na matice (kterou jak pises zatim moc nedelas), nebo to bude naopak spis teoreticky popsany nejakym pseudokodem. To bys i napsat v pythonu mohl, ale bud to bude pomaly (protoze v realu se pouzijou ruzny triky na zvyseni rychlosti, ke kterym je zapotrebi taky vyssi matematika nebo logika), nebo to bude tak jednoduchy, ze se na tom moc nic nenaucis.

A nebo jsem spatne pochopil, co se chces naucit Ja osobne bych se asi fakt nejvic o jazyku naucil z jinych projektu a prikladu, protoze ulohy na programovani byvaji spis jenom o tom, jestli znas teoretickej postup, pak uz to napises v jakymkoliv jazyku, s pouzitim zakladnich prikazu.

[Kyosuke]

Quicksort je přece trivka:

  def qsort(a)
    return [] if a.empty?
    lo, hi = a[1..-1].partition{|x| x<a[0]} 
    qsort(lo) + [a[0]] + qsort(hi)
  end

Takže na tom se fakt nic nenaučí. Ale ty "ruzny triky na zvyseni rychlosti, ke kterym je zapotrebi taky vyssi matematika nebo logika" se podle mě jmenujou "algoritmy".

[Jardík]

Tohle je snad ta nejpomalejší inplementace quicksortu, která existuje. Jakmile se používá rekurze, je to špatné.

[Kyosuke]

1) To je snad docela běžné, že jednoduché implementace nejsou zrovna optimální, a ty nejlepší nejsou zrovná jednoduché, ne? (Navíc typická rychlá implementace Cčkovského quicksortu určitě nebude natolik pěkná, aby ji dali do učebnic jako ilustraci toho, jak to funguje.) 2) Huh? Nechápu. Jak chceš implementovat divide-and-conquer algoritmy bez rekurzivního kroku? A proč by rekurze měla být špatná?

[miro]

Rekurzie sa osobne tiez nestranim, dnesne prekladace hadam optimalizuju volania metod ovela lepsie nez tomu bolo v minulosti. Ked ale mozem rekurziu nahradit cyklom a malou zmenou algoritmu, tak to radsej spravim.

[deda.jabko]

muzete nastinit reseni quicksortu bez rekurze? a pridavam se s dotazem: co je na rekurzi spatne?

[Lu-Tze]

Je otázka, co se myslím tím "bez rekurze". Quicksort bez rekurze to zní dost divně Ale quicksort s konstantní pamětí (tedy bez zásobníku) existuje, hledej pána Ďuriana.

[deda.jabko]

prave proto jsem se tak divil... ;-] nemate nekde ten clanek? docela by me to zajimalo... bohuzel se me podarilo najit jenom abstrakty a citace toho textu... :-/ a nez se dostanu do knihovny... abych se podival jestli tam neni 20 let stary sbornik, tak na to zapomenu... ;-]

[Kyosuke]

Hmm, to bych rád viděl. I Wikipedie tvrdí, že paměťové nároky na quicksort jsou prinejlepším O(log n), což je stejné, jako se zásobníkem.

[Lu-Tze]

No, tak to by se v té wikipedii mělo tedy opravit

Ten článek mám, na požádání ho pošlu.

[deda.jabko]

hm... mohl bych vas pozadat? mateho v el. nebo papirove podobe? pokud je to el. podoba, mohl byste mi jej poslat na email deda.jabko@centrum.cz dekuji

[Lu-Tze]

No vám a Kyosukemu jsem na to už ráno poslal odkaz (na edisk.cz, kam jsem to nahrál) přes formulář tady na ábíčku, nevím proč to nedošlo. Tak jsem to poslal ještě na deda.jabko@centrum.cz.

Dejte vědět, jestli to došlo.

[deda.jabko]

bohuzel mne nic nikam nedoslo.... :-/

[Lu-Tze]

OK, takže: http://www.edisk.cz/stahni/54844/durian.pdf_250.39KB.html

[deda.jabko]

diky, mrknu na to.

[Kyosuke]

Díky! Vypadá to důvěryhodně, až na ty řeči o "nejoblíbenějším algoritmu, kvůli jednoduchosti, eleganci, účinnosti a univerzálnímu charakteru" - jestli není stable, tak zase tak superuniverzální nebude, a stabilitou se v nadpisu autor nechlubí. Ale určitě si to projdu.

[Billy The Pilgrim]

Jestli Ti jde o obecnou algoritmizaci, doporucuju projit prvni rocniky informatickych fakult. Materialy byvaji na netu. U nas na FITu to byly nejake zaklady programovani (obecne o sprave pameti, ukazatele, seznamy - vsechno demonstrovane na Pascalu, ale pry uz presli na C) a potom Abstraktni Datove Struktury (seznamy, stromy, razeni, etc.).

Co se ale tyka te matematiky - v nejakych pokrocilejsich konstrukcich se bez alespon zakladu teorie grafu moc neobejdes - hodne uloh se prevadi prave na tohle (pozn. strom je taky graf). Na druhou stranu zaklady teorie grafu jsou oblibenou hrackou pro deticky na ruznych matematickych olympiadach, takze dost z toho uz mozna znas, jenom to neumis pojmenovat.

Co se tyka OOP (a ted nemluvim o pratelich pana Arafata), to bych do toho nemichal. OOP je o navrhu a o stylu programovani. Pokud nebudes umet klasicky (linearni) styl, OOP Ti nepomuze - spis Ti naopak zamota hlavu.

Osobne bych doporucoval trochu neco zjistit o dynamicke alokaci pameti (nejlepe styl Ccka, at vis zhruba o cem to je), potom abstraktni struktury (seznam, zasobnik, fronta) a na nich si vyzkousej nejake razeni (dobre vedet, ze existuji i jine algoritmy, nez bubble sort). Na zaver si zkus par algoritmu se stromem (pruchody stromem, vkladani/mazani prvku) a pokud se dostanes i pres to, mel bys v prubehu mit dost zkusenosti, abys vedel cemu se venovat dal (treba to OOP, hrani s typy, etc.)

[Fluttershy, yay!]

Děkuji mnohokrát.

Ony ty dynamické struktury apod. jsou v Pythonu trošku hůře proveditelné na nižší úrovni (ukazatele), na to je dobré C, ale do něj se mi moc nechce. Vyzkoušení ale jasná věc.

[Kyosuke]

"Co se tyka OOP (a ted nemluvim o pratelich pana Arafata), to bych do toho nemichal. OOP je o navrhu a o stylu programovani. Pokud nebudes umet klasicky (linearni) styl, OOP Ti nepomuze - spis Ti naopak zamota hlavu."

Jo, a navíc je to ještě jen podmnožina návrhu a stylu programování, která se v SICP odbyde jako jedna z několika možností. Jinak se na algoritmy doporučuje i tahle knížka.

[Radek Miček]

Ja mohu zase doporucit knizku Introduction to Algorithms, bohuzel neni vsak zdarma na webu.

[Kyosuke]

Ta je dobrá k nahlížení na konkrétní věci, ale jako učebnice IMHO zas až tak neexceluje.

[Tom.š Ze.le.in]

Knuthovo TAOCP obsahuje v každém díle spoustu velmi zajímavých úloh :)

[Jardík]

Hledám programátora, který by mi byl ochoten přepsat poměrně prasácký zdrojový kód komponenty ZipTV (kompresní a dekompresní komponenta) pro delphi do C++ (objektově) a zároveň ho udělal thread-safe. Cena do 5000 Kč, spěchá, pište na e-mail.

[Deleted [8409]]

jestli nemáte co dělat, podívejte se třeba na django nebo cherrypy. Web je oblast, kam se podle mě python docela hodí a tyto frameworky nejsou vůbec špatné.

[Lu-Tze]

Kdy bude pokračování seriálu o Scheme? Už skoro přestávám doufat...

[Fluttershy, yay!]

Už jsem panu šéfredaktorovi poslal pokračování. ^_^