Home of DISCRETE MATHEMATICS (M 205-HY 118) Problems with Greek fonts? Try going to http://www.csd.uch.gr/~kolount/discrete-vt420.html or even to http://www.csd.uch.gr/~kolount/discrete-latin.html

H selida auth brisketai sth dieu0unsh http://www.csd.uch.gr/~kolount/discrete.html opws epishs kai sth dieu0unsh http://www.math.uiuc.edu/~kolount/discrete.html

Mporeite na thn prospelasete xrhsimopoiwntas Netscape, Mosaic, Internet Explorer (auta xreiazontai termatika graphics) eite to programma lynx. Auto den apaitei graphics kai mporeite na to trejete apo sxedon opoiodhpote termatiko dinontas p.x. thn entolh
lynx http://www.csd.uch.gr/~kolount/discrete.html

Sthn periptwsh pou den exete graphics uparxei periptwsh to termatiko sas na mh xeirizetai kala tous Ellhnikous xarakthres. 0a uparxoun tote sthn korufh ths selidas enallaktikes dieu0unseis (URL) pou 0a einai panta anagnwsimes kai apo tis opoies (analoga me to ti termatiko exete) 0a mporeite na exete kanonika prosbash sth selida.

Oi pio prosfates kataxwrhseis briskontai sto telos ths selidas.

Panepisthmio Krhths -- Ma0hmatiko Tmhma

Diakrita Ma0hmatika (M 205 - HU 118)

Earino Ejamhno 1997-98

Wres: D, Te 2-4 (Amf BJ)

Didaskwn: Mixalhs N. Kolountzakhs

Proswpikh selida
E-mail: kolount@math.uch.gr
Grafeio: Z 303, Wres Grafeiou: opotedhpote eimai ekei h me rantebou.
Biblio--shmeiwseis: 0a moirastoun fwtotupies apo to biblio C.L. Liu, "Stoixeia diakritwn ma0hmatikwn", pou 0a kukloforhsei suntoma apo tis Panep. Ekdoseis Krhths. Endexomenws 0a moirastoun kai alles shmeiwseis.
Ta 0emata pou 0a kaluf0oun perilambanoun (alla den periorizontai sta)
  1. Ma0hmatikh epagwgh
  2. Metrhma (enumeration)
  3. Gennhtries sunarthseis
  4. Anadromikes sxeseis
  5. Arxh egkleismou-apokleismou (Inclusion-Exclusion Principle)
  6. Grafhmata, diktua
  7. Aploi algori0moi se grafhmata
  8. Asumptwtikes ektimhseis

Askhseis Ka0'olh th diarkeia tou ejamhnou 0a dinetai ena fulladio me 10-15 askhseis/ebdomada. Ka0e 2h bdomada kai gia 15 peripou lepta oi foithtes 0a grafoun (me kleistes shmeiwseis) mia askhsh pou exei epilegei apo to didaskonta apo ta prohgoumena 2 fulladia (h mia polu paromoia). H summetoxh twn foithtwn s'auto einai proairetikh alla sunistatai entona h summetoxh sas wste ta diagwnismata (proodos, telikos) na mhn sas er0oun duskola.

Ba0mologiko susthma: Estw I o ba0mos ths ejetashs tou Iouniou, M o ba0mos ths proodou kai T o ba0mos twn askhsewn.
O telikos ba0mos gia thn periodo tou Iouniou 0a einai to megisto twn:

  1. I
  2. 0.6 I + 0.4 M
  3. 0.6 I + 0.4 T
Gia thn periodo Septembriou o telikos ba0mos einai autos ths ejetashs kai mono.

Arxh ejamhnou: H selida auth 0a enhmerwnetai taktika gia 0emata pou aforoun ta Diakrita Ma0hmatika (M 205). Edw 0a briskete sunh0ws:

  1. Mia polu suntomh perigrafh tou ti eipw0hke ka0e mera sto ma0hma
  2. Poies askhseis sunistw na lunete kai, endexomenws, upodeijeis gia th lush tous
  3. Palia 0emata ejetasewn
  4. Shmantikes anakoinwseis (hmeromhnies diagwnismatwn, statistika stoixeia gia tis epidoseis sta diagwnismata, k.l.p.)
  5. Deiktes (links) se alles selides sto Internet me paromoia 0emata
  6. Diafora istorika stoixeia sxetika me to ma0hma, k.a.
Deite gia paradeigma mia paromoia selida gia ena ma0hma Sunduastikwn Ma0hmatikwn se pio proxwrhmeno omws epipedo opws kai th selida ths Migadikhs Analushs apo to prohgoumeno ejamhno.

Giati h selida;
Enas apo tous logous uparjhs auths ths selidas einai sa kinhtro gia thn apokthsh apo to foithth ikanothtas xrhshs tou Internet. Skopos einai na gnwrizei kaneis ti eidous plhrofories mporei na brei sto diktuo ka0ws kai to pws na tis anazhthsei.
Fusika, mia kai uparxei kosmos pou den 0elei na apokthsei tetoies gnwseis kai de 0elei na exei epafh me ton upologisth, h selida auth 0a tupwnetai kai 0a anartatai ejw apo to grafeio mou peripou mia fora th bdomada, wste na mporei kaneis na parei olh thn plhroforia apo ekei.

Giati h selida;
Enas apo tous logous uparjhs auths ths selidas einai sa kinhtro gia thn apokthsh apo to foithth ikanothtas xrhshs tou Internet. Skopos einai na gnwrizei kaneis ti eidous plhrofories mporei na brei sto diktuo ka0ws kai to pws na tis anazhthsei.
Fusika, mia kai uparxei kosmos pou den 0elei na apokthsei tetoies gnwseis kai de 0elei na exei epafh me ton upologisth, h selida auth 0a tupwnetai kai 0a anartatai ejw apo to grafeio mou peripou mia fora th bdomada, wste na mporei kaneis na parei olh thn plhroforia apo ekei.

De, 16 Feb: Eisagwgh sthn ulh tou ma0hmatos kai anafora se endeiktika problhmata pou 0a mas apasxolhsoun auto to ejamhno.

Sthn kleisth sullogh ths biblio0hkhs topo0eth0hkan ta ejhs biblia pou sunistatai na sumbouleueste.

  1. L.O. Katzoff and A.J. Simone, Finite Mathematics, McGraw Hill, 1965.
  2. A.W. Goodman and J.S. Ratti, Finite Mathematics with Applications, 3rd edition, Macmillan, 1979.

Te, 18 Feb: Grhgorh epanalhyh ths me0odou ths epagwghs, plh0os uposunolwn tou sunolou [n] = {1, 2, ..., n}, uposunola mege0ous k, meta0eseis, to trigwno tou Pascal, to Diwnumiko 0ewrhma kai efarmoges

Moirasthke to 1o fulladio askhsewn.

De, 23 Feb: Merikh epanalhyh orismenwn basikwn ennoiwn apo to prhgoumeno ma0hma, luseis merikwn askhsewn (apo to biblio, fwtotupies apo to opoio 0a moirastoun sxetika suntoma, elpizw) pou aforoun to metrhma meta0esewn h sunduasmwn pou plhroun orismenes idiothtes. Metrhma sunduasmwn me epana0esh: to 0ewrhma 0a apodeix0ei jana sto epomeno ma0hma.

Idou ena kinhtro gia na ma0ete (an de gnwrizete hdh) (i) Agglika kai (ii) kalh xrhsh tou Internet (kuriws orologia kai to pws grafei kaneis Ma0hmatika se upologisth xwris grafika). Akolou0eiste auto to deikth pou 0a sas odhghsei se mia selida sunduastikhs sto Panepisthmio Rutgers (H.P.A.) opou 0a breite diafores askhseis (kai tis luseis tous!) paromoies me autes pou 0a mas apasxolhsoun auto to ejamhno. Prospa0eiste na tis lusete oles (h oses pio polles mporeite). (23/2/98)

Te, 25 Feb: Deigmatolhyia me epana0esh (jana), me posous tropous mporei na grafei to k san a0roisma n mh arnhtikwn akeraiwn, asumptwtikes ektimhseis (ti shmainei a ~ b), o tupos tou Stirling, to mege0os tou diwnumikou suntelesth C(n, k).

Moirasthke to 2o fulladio askhsewn.

Pa, 27 Feb: ¸gine mia wra askhsewn (9-10), kuriws panw sto 2o fulladio askhsewn.

To prwto diagwnisma 0a ginei sto telos ths 2hs wras thn Tetarth 4 Martiou me kleistes shmeiwseis kai gia 20 peripou lepta.

Te, 4 Mar: Eisagwgh sta grafhmata: Apla, kateu0unomena. Pinakas sundesmologias. Geitones. Dimerh grafhmata. Upografhmata kai epagomena upografhmata. Monopatia kai kuklwmata. Epishs monopatia kai kuklwmata Euler kai Hamilton. Ba0mos. Sunektika grafhmata, sunektikes sunistwses. Apostash (kai trigwnikh anisothta), diametros. Dentra (= sunektika grafhmata xwris kuklous).
¸gine to prwto 150hmero diagwnisma.

Ku, 8 Mar: Ta apotelesmata tou 1ou diagwnismatos exoun anarth0ei ejw apo to grafeio mou. Ta pleon koina la0h htan (a) h elleiyh aplopoihshs ths telikhs parastashs kai (b) h mh diairesh dia tou n! gia na agnoh0ei h seira me thn opoia paristanontai oi omades.

De, 9 Mar: Dentro me n korufes exei n-1 akmes. Dentra pou paragoun (spanning trees), elaxista dentra pou paragoun se grafhmata me barh. Apodeijh oti o muwpikos algori0mos (greedy algorithm) dinei elaxisto dentro.

Te, 11 Mar: Isomorfia grafhmatwn. Kuklwma kai monopati Euler. Anagkaia kai ikanh sun0hkh gia thn uparjh kuklwmatos Euler. Apostaseis se grafhmata me barh. O algori0mos Floyd-Warshall gia thn euresh twn apostasewn anamesa se ka0e zeugos korufwn. Apodeijh tou oti douleuei. O algori0mos Dijkstra gia thn euresh twn apostasewn apo ena sta0ero kombo se olous tou upoloipous. Apodeijh tou oti douleuei.

De, 16 Mar: Xrwmatismos korufwn kai akmwn, xrwmatikos ari0mos x(G) enos grafhmatos, grafhma grammwn tou G. To anw fragma x(G) <= d+1, opou d o megistos ba0mos tou grafhmatos. ¸na aplo 0ewrhma tupou Ramsey (oti se ka0e xrwmatismo akmwn tou K6 uparxei kapoio monoxrwmatiko trigwno). Susthmata jenwn antiproswpwn (SJA) gia oikogeneies uposunolwn A1, A2, ..., An tou sunolou X. Epagwgikh apodeijh tou 0ewrhmatos tou Gamou (0ewrhma Hall).
P R O S O X H:
Diatupwsa ena 0ewrhma gia to xrwmatiko ari0mo enos grafhmatos to opoio einai LA0OS. Eipa oti o x(G) einai anw fragmenos apo t+1, opou t einai o mesos ba0mos tou grafhmatos. Auto einai la0os! Prospa0eiste na breite ena grafhma me x(G) as poume iso me 100 kai me t < 3.

H prwth proodos 0a ginei thn ebdomada ths 28hs Martiou. H ulh pou 0a ejetastei 0a einai o,ti exoume kaluyei mexri kai thn prohgoumenh ebdomada apo auth.

Mia selida se Postscript gia to 0ewrhma tou Gamou.

H proodos 0a ginei thn Pempth, 2 Apriliou, 8-10mm, sta tria amfi0eatra kai stis ai0ouses 0201 kai 0207.

Te, 18 Mar: Epanalhf0hke h apodeijh tou 0ewrhmatos tou Hall gia susthmata jenwn antiproswpwn. Susthmata jenwn antiproswpwn gia kanonika susthmata sunolwn. Isodunama, deijame oti se ka0e kanoniko dimeres grafhma uparxei ena tairiasma twn aristerwn korufwn 1-1 me tis dejies. Epishs asxolh0hkame me to xrwmatiko ari0mo tou grafhmatos Cn (kuklos me n korufes).
¸gine to deutero 150hmero diagwnisma.

De, 23 Mar: Den egine ma0hma logw as0eneias tou didaskonta.

Te, 25 Mar: Argia.

¸ktakto ma0hma: Paraskeuh, 27 Martiou, 6-8mm, Amf. BJ. 0a ginoun kuriws askhseis.

Shmeiwseis: Mia polu suntomh eisagwgh sth 0ewria Grafhmatwn (Postscript).
Exw dwsei antigrafa sto kulikeio gia fwtotuphsh.

H proodos 0a ginei thn Pempth, 2 Apriliou, 8-10mm, sta tria amfi0eatra kai stis ai0ouses 0201 kai 0207.
A N O I X T E S S H M E I W S E I Ò.

De, 30 Mar: Milhsame gia epipeda grafhmata. Apodeijame to 0ewrhma tou Euler (V+F = E+2) kai telos to 0ewrhma twn 5 xrwmatwn ("ka0e epipedos xarths mporei na xrwmatistei me 5 xrwmata wste xwres pou geitoneuoun na exoun diaforetika xrwmata").

Wres askhsewn: Trith, 31 Martiou, 8-10mm, Amf BJ.

Ku, 5 Apr: Oi ba0moi sas sthn proodo briskontai edw opws kai to istogramma olwn twn ba0mwn.

De, 6 Apr., kai Te, 8 Apr.: Gennhtries sunarthseis akolou0iwn. Pws pame apo thn akolou0ia sth gennhtria sunarthsh kai antistrofa. Pws xrhsimopoiountai oi gennhtries sunarthseis gia thn euresh kleistou tupou gia akolou0ies mesw eureshs kleistou tupou gia tis gennhtries sunarthseis tous kai efarmogh ths me0odou kuriws se anadromika orizomenes akolou0ies.
Megalh emfash dinetai sthn ikanothta na briskei kaneis ena kleisto tupo gia gennhtria sunarthsh mias akolou0ias kat'eu0eian apo th sunduastikh perigrafh ths akolou0ias.

Thn Tetarth, 29 Apriliou, 0a ginei to epomeno diagwnisma panw sthn 5h kai 6h omada askhsewn.

De, 27 Apr., kai Te, 29 Apr.: Eisagwgh sth Diakrith Pi0anothta. O Deigmatikos Xwros W kai h pi0anothta enos endexomenou (uposunolou tou W). Paradeigmata. Moirasthke h 7h omada askhsewn.

Ku, 3 Maúou: Oi ba0moi sas gia to 3o diagwnisma briskontai edw.

Pros thn arxh ths selidas.