Důkazy u Kučery

Odeslat odpověď

Smajlíci
:D :) :( :o :shock: :? 8) :lol: :x :P :oops: :cry: :evil: :twisted: :roll: :wink: :!: :?: :idea: :arrow: :| :mrgreen:

BBCode je zapnutý
[img] je zapnutý
[flash] je vypnutý
[url] je zapnuté
Smajlíci jsou zapnutí

Přehled tématu
   

Rozšířit náhled Přehled tématu: Důkazy u Kučery

od twoflower » 5. 2. 2006 11:33

twoflower píše:
Eubie píše:Ad Kučera: ke Golbergovi se mam učit to hafo lemmat co je na pět stránek?
Je toho hodne, ale fakt jednoduchy, jednou dvakrat si to prectes a das to v pohode.
Dodatek: je to jednoduche az na to posledni lemma, to jsem v tichosti ignoroval :)

od Debugger » 4. 2. 2006 21:01

Eubie píše:Ad Kučera: ke Golbergovi se mam učit to hafo lemmat co je na pět stránek?
F podstate staci jen princip a zakladni vety... na slozitost se PRY nepta.

od twoflower » 4. 2. 2006 17:14

Eubie píše:Ad Kučera: ke Golbergovi se mam učit to hafo lemmat co je na pět stránek?
Je toho hodne, ale fakt jednoduchy, jednou dvakrat si to prectes a das to v pohode.

od Eubie » 4. 2. 2006 17:11

Taky bych nejraděj měl nějakou práci v oboru, ale až na MFF mi došlo, že pracovat v oboru nejčastěj znamená prosedět 8h/denně za kompem, drtit nějakej kód a to se mi ani za mák nelíbí (ani to, že po pár letech takovýho života se mlže člověk stát manažerem) - třeba taky proto,že sem už za počem naseděl tolik, že mam uschlý voči a vodrovnaný záda:) Navíc pár lidí "z oboru" sem poznal a až na výjimky mi přijde, že pořádně nežijou nebo maj uplně zvrácený hodnoty.

Ad Kučera: ke Golbergovi se mam učit to hafo lemmat co je na pět stránek?

od Debugger » 4. 2. 2006 16:41

twoflower píše:Me vlastne stve jedina vec, a za tu si muzu sam. Jsem dost velka lemra a nedokazu vyuzit vsechny ty znalosti, ktere tady mam na dosah ruky, misto toho se radsi flakam. Treba se nekdy donutim :)
I have the same problem. :cry:

od twoflower » 4. 2. 2006 13:59

Me vlastne stve jedina vec, a za tu si muzu sam. Jsem dost velka lemra a nedokazu vyuzit vsechny ty znalosti, ktere tady mam na dosah ruky, misto toho se radsi flakam. Treba se nekdy donutim :)

od LuKu » 4. 2. 2006 13:57

twoflower píše:Lidi, kdo jste dostali binarni scitani, co jste mu tam vykladali? Mam tady Kuceruv studijni text z 2003, to je na 3 stranky, docela v pohode, neklade se tam moc duraz na spojitost dukazu s tim logickym obvodem.

Pak tady mam ten novejsi, co ma ted na strankach a tam je ten dukaz o dost rozvleklejsi a pracuje tam o dost vic se stavbou toho obvodu.

Co mu staci ke stesti? Myslel jsem ze bych mu jen ukazal, jak asi ten obvod vypada, pricemz bych to ale nedokazoval tim zpusobem jakym to ma v tom novejsim textu...
Ja jsem mela binarni scitani na prvnim predterminu, ucila jsem se na to z tech jeho novych materialu a sily k jejich cteni mi dosly v okamziku, kdy to zacal formalne popisovat, tzn. docetla jsem jen Prochazku appletem, Laborator uz ne. Kdyz jsem mu to pak u zkousky nejak odvypravela, nabidl mi dvojku, coz mi stacilo, takze jsem radsi vypadla. Predpokladam, ze na jednicku by ty formalni veci chtel...

Re: Důkazy u Kučery

od Almer » 4. 2. 2006 11:07

Eubie píše: P.S. Změnil někomu život na MFF pohled na informatiku tak, že s informatikou nechce mít v pracovním životě nic společnýho, nebo sem sám?:)
Myslim, ze i muj pohled se trosku zmenil. Ale ono to vychazi z toho, ze na strednich skolach, byla vetsina nas povazovana za programatorske GURU, protoze sme v mnoha pripadech vedeli vice, nez ucitele co nas meli na pocitacove predmety ucit. Zlom nastal s prichodem sem, tady clovek zjisti, ze najednou toho umi tak malo, a tak malo vi, a ze to, ze byl na svoji skole dobre, neznamena, ze musi byt dobrej i tady.

Druha vec je, ze nechceme mit s informatikou nic spolecneho? A kde je duvod? Je to proto, protoze najednou "nas" se snazi predelat, ze nam vnucuji "jejich" zpusob a ten se nam nelibi? A nebo je to tim, ze momentalne se ucime jazyky ktere nas "nezajimaji". Ale no tak? kolikrat se budeme jeste ucit veci, ktere podle nas budou "na nic". Nejen na tehle skole...

A tedka co se tyce toho kouzla, ze "jeeee programovani". Podle mne je to tak se vsim. Ja velmi rad varim, ci pecu, bavi mne to, zpusob jakym relaxujem. Ale vim, ze kdybych sel na kuchare, misto na informatiku, tak by se mi to zhnusilo a degradovalo na pouhou povinnost v praci. Mozna, ze s informatikou je to tak nejak podobne.

Nevim, jestli po MFF budu delat programatora, a nebo ne, jestli mne mi spolubydlici nezdeptaji natolik, ze se budu citit stale, ze nic neumim, ale to necham az osudu. Bylo by dobre, kdybych delal neco v oboru, protoze, proto sme primarne delali tuhle skolu, a pokud sme nevypadli po prvnim roce, tak sme si asi vsichni rekli, ze to stoji za to delat tohle, a ma to budoucnost.

Uff...tak to asi k tematu:)

Re: Důkazy u Kučery

od Debugger » 4. 2. 2006 09:53

Eubie píše: P.S. Změnil někomu život na MFF pohled na informatiku tak, že s informatikou nechce mít v pracovním životě nic společnýho, nebo sem sám?:)
Jo změnil. Nejsi v tom sám. MFF změnila můj pohled nejen na informatiku, ale taky na život celkově... asi se pro tyhle věci nehodím.. ;) :roll:

od jaruch » 4. 2. 2006 09:21

kdesi som tu cital, ze to dakto dostal a stacilo postavit scitacku a vysvetlit principy, bloky etc... a to na dva... tak ja neviem... pozri sa do inych tem...

od twoflower » 4. 2. 2006 09:11

Lidi, kdo jste dostali binarni scitani, co jste mu tam vykladali? Mam tady Kuceruv studijni text z 2003, to je na 3 stranky, docela v pohode, neklade se tam moc duraz na spojitost dukazu s tim logickym obvodem.

Pak tady mam ten novejsi, co ma ted na strankach a tam je ten dukaz o dost rozvleklejsi a pracuje tam o dost vic se stavbou toho obvodu.

Co mu staci ke stesti? Myslel jsem ze bych mu jen ukazal, jak asi ten obvod vypada, pricemz bych to ale nedokazoval tim zpusobem jakym to ma v tom novejsim textu...

Re: Důkazy u Kučery

od Isidor » 3. 2. 2006 12:26

Eubie píše:P.S. Změnil někomu život na MFF pohled na informatiku tak, že s informatikou nechce mít v pracovním životě nic společnýho, nebo sem sám?:)
Az uplne tak drasticky by som to nevidel, ale je fakt, ze by sa asi nasla vhodnejsia skola nez tato... ale menit neplanujem :)

od jaruch » 3. 2. 2006 12:24

Treba si pozhanat nejake materialy, co ma bud na webe, alebo aj z minulych rokov, tam su dokazy, ktore chce (a ktore sa diametralne odlisuju od toho, co povedal na prednaske)... Ja som mal vyhladavanie v texte a chcel nejaky dokaz toho, ze aho a knuth si linearne, a nemyslim, ze by stacilo povedat "plynie z algoritmu"... ale zas vobec nechcel dokazy stavby automatu...

Re: Důkazy u Kučery

od hippies » 3. 2. 2006 12:17

Eubie píše: P.S. Změnil někomu život na MFF pohled na informatiku tak, že s informatikou nechce mít v pracovním životě nic společnýho, nebo sem sám?:)
Spolubydla říká, že sám nejsi. Jinak já jsem spokojen, přesně to, co jsem čekal :)

od Tuetschek » 3. 2. 2006 12:05

No...
z tech prednasek se neda uplne jednoznacne rict co je uplny dukaz a co jen naznak, takze trochu odhadem (za uplnost nerucim!):

bin. scitani - slozitost
FFT - slozitost
Knuth-Morris-Pratt - nevim tam jsem nebyl, ale neni tezky
Aho-Corrasic - spis hlavne jak to funguje, slozitost z toho vyplyne
Rabin-Kapp - tak zrychlene
Tridici sit - slozitost
Konvexni obal - slozitost
Voronoi - jen jak to funguje, slozitost bez dukazu
Toky v sitich:
  • Ford-Fulkerson: min.rez = max.tok
    Dinic - kompletni dukaz slozitosti
    Goldberg: dukaz, ze tok je opravdu max., dukaz ze zadny vrchol nezvednu vys nez 2n-1 & celkovy dukaz slozitosti pomoci nasycenych a nenasycenych prevedeni
NP
  • prevod 3-SAT, barevnost, nez. mnozina
    prevod cehokoliv na splnitelnost
    aproximacni algoritmy - zrychlene, spis naznaky nebo bez dukazu
DES - spis co to je
RSA - jak funguje, dukaz ze funguje (priblizny)

Tohle delal na prednasce, ty toky je asi dobry vedet do detailu, co vsechno zkousi z NP uplnosti a zda zkousi i RSA, nemam Ahnung. :roll:
Kdyby si nekdo jeste na neco vzpomnel, necht me doplni :) .

Nahoru