http://www.csd.uch.gr/~kolount/discrete-vt420.html
or even to
http://www.csd.uch.gr/~kolount/discrete-latin.html
Ç óåëßäá áõôÞ âñßóêåôáé óôç äéåýèõíóç
http://www.csd.uch.gr/~kolount/discrete.html
üðùò åðßóçò êáé óôç äéåýèõíóç
http://www.math.uiuc.edu/~kolount/discrete.html
Ìðïñåßôå íá ôçí ðñïóðåëÜóåôå ÷ñçóéìïðïéþíôáò
Netscape
, Mosaic
,
Internet Explorer
(áõôÜ ÷ñåéÜæïíôáé ôåñìáôéêÜ graphics) åßôå
ôï ðñüãñáììá lynx
.
Áõôü äåí áðáéôåß graphics êáé ìðïñåßôå íá ôï ôñÝîåôå áðü ó÷åäüí
ïðïéïäÞðïôå ôåñìáôéêü äßíïíôáò ð.÷. ôçí åíôïëÞ
lynx http://www.csd.uch.gr/~kolount/discrete.html
Óôçí ðåñßðôùóç ðïõ äåí Ý÷åôå graphics õðÜñ÷åé ðåñßðôùóç ôï ôåñìáôéêü óáò íá ìç ÷åéñßæåôáé êáëÜ ôïõò Åëëçíéêïýò ÷áñáêôÞñåò. Èá õðÜñ÷ïõí ôüôå óôçí êïñõöÞ ôçò óåëßäáò åíáëëáêôéêÝò äéåõèýíóåéò (URL) ðïõ èá åßíáé ðÜíôá áíáãíþóéìåò êáé áðü ôéò ïðïßåò (áíÜëïãá ìå ôï ôß ôåñìáôéêü Ý÷åôå) èá ìðïñåßôå íá Ý÷åôå êáíïíéêÜ ðñüóâáóç óôç óåëßäá.
Ïé ðéï ðñüóöáôåò êáôá÷ùñÞóåéò âñßóêïíôáé óôï ôÝëïò ôçò óåëßäáò.
kolount@math.uch.gr
ÁóêÞóåéò Êáè'üëç ôç äéÜñêåéá ôïõ åîáìÞíïõ èá äßíåôáé Ýíá öõëëÜäéï
ìå 10-15 áóêÞóåéò/åâäïìÜäá.
ÊÜèå 2ç âäïìÜäá êáé ãéá 15 ðåñßðïõ ëåðôÜ ïé öïéôçôÝò èá ãñÜöïõí
(ìå êëåéóôÝò óçìåéþóåéò) ìéá Üóêçóç ðïõ Ý÷åé åðéëåãåß áðü ôï
äéäÜóêïíôá áðü ôá ðñïçãïýìåíá 2 öõëëÜäéá (Þ ìéá ðïëý ðáñüìïéá).
Ç óõììåôï÷Þ ôùí öïéôçôþí ó'áõôü åßíáé ðñïáéñåôéêÞ áëëÜ
óõíéóôÜôáé Ýíôïíá ç óõììåôï÷Þ óáò þóôå ôá äéáãùíßóìáôá (ðñüïäïò, ôåëéêüò)
íá ìçí óáò Ýñèïõí äýóêïëá.
Âáèìïëïãéêü óýóôçìá:
Åóôù I ï âáèìüò ôçò åîÝôáóçò ôïõ Éïõíßïõ,
M ï âáèìüò ôçò ðñïüäïõ êáé T ï âáèìüò ôùí áóêÞóåùí.
Ï ôåëéêüò âáèìüò ãéá ôçí ðåñßïäï ôïõ Éïõíßïõ
èá åßíáé ôï ìÝãéóôï ôùí:
Áñ÷Þ åîáìÞíïõ: Ç óåëßäá áõôÞ èá åíçìåñþíåôáé ôáêôéêÜ
ãéá èÝìáôá ðïõ áöïñïýí ôá ÄéáêñéôÜ ÌáèçìáôéêÜ (Ì 205).
Åäþ èá âñßóêåôå óõíÞèùò:
Ãéáôß ç óåëßäá;
Åíáò áðü ôïõò ëüãïõò ýðáñîçò áõôÞò ôçò óåëßäáò åßíáé
óá êßíçôñï ãéá ôçí áðüêôçóç áðü ôï öïéôçôÞ éêáíüôçôáò
÷ñÞóçò ôïõ Internet.
Óêïðüò åßíáé íá ãíùñßæåé êáíåßò ôé åßäïõò ðëçñïöïñßåò
ìðïñåß íá âñåß óôï äßêôõï êáèþò êáé ôï ðþò íá ôéò
áíáæçôÞóåé.
ÖõóéêÜ, ìéá êáé õðÜñ÷åé êüóìïò ðïõ äåí èÝëåé íá áðïêôÞóåé
ôÝôïéåò ãíþóåéò êáé äå èÝëåé íá Ý÷åé åðáöÞ ìå ôïí
õðïëïãéóôÞ, ç óåëßäá áõôÞ èá ôõðþíåôáé êáé èá áíáñôÜôáé Ýîù
áðü ôï ãñáöåßï ìïõ ðåñßðïõ ìéá öïñÜ ôç âäïìÜäá, þóôå íá
ìðïñåß êáíåßò íá ðÜñåé üëç ôçí ðëçñïöïñßá áðï åêåß.
Ãéáôß ç óåëßäá;
Åíáò áðü ôïõò ëüãïõò ýðáñîçò áõôÞò ôçò óåëßäáò åßíáé
óá êßíçôñï ãéá ôçí áðüêôçóç áðü ôï öïéôçôÞ éêáíüôçôáò
÷ñÞóçò ôïõ Internet.
Óêïðüò åßíáé íá ãíùñßæåé êáíåßò ôé åßäïõò ðëçñïöïñßåò
ìðïñåß íá âñåß óôï äßêôõï êáèþò êáé ôï ðþò íá ôéò
áíáæçôÞóåé.
ÖõóéêÜ, ìéá êáé õðÜñ÷åé êüóìïò ðïõ äåí èÝëåé íá áðïêôÞóåé
ôÝôïéåò ãíþóåéò êáé äå èÝëåé íá Ý÷åé åðáöÞ ìå ôïí
õðïëïãéóôÞ, ç óåëßäá áõôÞ èá ôõðþíåôáé êáé èá áíáñôÜôáé Ýîù
áðü ôï ãñáöåßï ìïõ ðåñßðïõ ìéá öïñÜ ôç âäïìÜäá, þóôå íá
ìðïñåß êáíåßò íá ðÜñåé üëç ôçí ðëçñïöïñßá áðï åêåß.
Äå, 16 Öåâ: ÅéóáãùãÞ óôçí ýëç ôïõ ìáèÞìáôïò êáé áíáöïñÜ óå åíäåéêôéêÜ ðñïâëÞìáôá ðïõ èá ìáò áðáó÷ïëÞóïõí áõôü ôï åîÜìçíï.
Óôçí êëåéóôÞ óõëëïãÞ ôçò âéâëéïèÞêçò ôïðïèåôÞèçêáí ôá åîÞò âéâëßá ðïõ óõíéóôÜôáé íá óõìâïõëåýåóôå.
Ôå, 18 Öåâ: ÃñÞãïñç åðáíÜëçøç ôçò ìåèüäïõ ôçò åðáãùãÞò, ðëÞèïò õðïóõíüëùí ôïõ óõíüëïõ [n] = {1, 2, ..., n}, õðïóýíïëá ìåãÝèïõò k, ìåôáèÝóåéò, ôï ôñßãùíï ôïõ Pascal, ôï Äéùíõìéêü Èåþñçìá êáé åöáñìïãÝò
ÌïéñÜóôçêå ôï 1ï öõëëÜäéï áóêÞóåùí.
Äå, 23 Öåâ: ÌåñéêÞ åðáíÜëçøç ïñéóìÝíùí âáóéêþí åííïéþí áðü ôï ðñçãïýìåíï ìÜèçìá, ëýóåéò ìåñéêþí áóêÞóåùí (áðü ôï âéâëßï, öùôïôõðßåò áðü ôï ïðïßï èá ìïéñáóôïýí ó÷åôéêÜ óýíôïìá, åëðßæù) ðïõ áöïñïýí ôï ìÝôñçìá ìåôáèÝóåùí Þ óõíäõáóìþí ðïõ ðëçñïýí ïñéóìÝíåò éäéüôçôåò. ÌÝôñçìá óõíäõáóìþí ìå åðáíÜèåóç: ôï èåþñçìá èá áðïäåé÷èåß îáíÜ óôï åðüìåíï ìÜèçìá.
Éäïý Ýíá êßíçôñï ãéá íá ìÜèåôå (áí äå ãíùñßæåôå Þäç) (i) ÁããëéêÜ êáé (ii) êáëÞ ÷ñÞóç ôïõ Internet (êõñßùò ïñïëïãßá êáé ôï ðùò ãñÜöåé êáíåßò ÌáèçìáôéêÜ óå õðïëïãéóôÞ ÷ùñßò ãñáöéêÜ). Áêïëïõèåßóôå áõôü ôï äåßêôç ðïõ èá óáò ïäçãÞóåé óå ìßá óåëßäá óõíäõáóôéêÞò óôï ÐáíåðéóôÞìéï Rutgers (Ç.Ð.Á.) üðïõ èá âñåßôå äéÜöïñåò áóêÞóåéò (êáé ôéò ëýóåéò ôïõò!) ðáñüìïéåò ìå áõôÝò ðïõ èá ìáò áðáó÷ïëÞóïõí áõôü ôï åîÜìçíï. Ðñïóðáèåßóôå íá ôéò ëýóåôå üëåò (Þ ïóåò ðéï ðïëëÝò ìðïñåßôå). (23/2/98)
Ôå, 25 Öåâ: Äåéãìáôïëçøßá ìå åðáíÜèåóç (îáíÜ), ìå ðüóïõò ôñüðïõò ìðïñåß íá ãñáöåß ôï k óáí Üèñïéóìá n ìç áñíçôéêþí áêåñáßùí, áóõìðôùôéêÝò åêôéìÞóåéò (ôé óçìáßíåé a ~ b), ï ôýðïò ôïõ Stirling, ôï ìÝãåèïò ôïõ äéùíõìéêïý óõíôåëåóôÞ C(n, k).
ÌïéñÜóôçêå ôï 2ï öõëëÜäéï áóêÞóåùí.
Ðá, 27 Öåâ: ¸ãéíå ìßá þñá áóêÞóåùí (9-10), êõñßùò ðÜíù óôï 2ï öõëëÜäéï áóêÞóåùí.
Ôï ðñþôï äéáãþíéóìá èá ãßíåé óôï ôÝëïò ôçò 2çò þñáò ôçí ÔåôÜñôç 4 Ìáñôßïõ ìå êëåéóôÝò óçìåéþóåéò êáé ãéá 20 ðåñßðïõ ëåðôÜ.
Ôå, 4 Ìáñ: ÅéóáãùãÞ óôá ãñáöÞìáôá: ÁðëÜ, êáôåõèõíüìåíá. Ðßíáêáò
óõíäåóìïëïãßáò. Ãåßôïíåò. ÄéìåñÞ ãñáöÞìáôá. ÕðïãñáöÞìáôá êáé åðáãüìåíá
õðïãñáöÞìáôá. ÌïíïðÜôéá êáé êõêëþìáôá. Åðßóçò ìïíïðÜôéá êáé êõêëþìáôá
Euler êáé Hamilton. Âáèìüò. ÓõíåêôéêÜ ãñáöÞìáôá, óõíåêôéêÝò óõíéóôþóåò.
Áðüóôáóç (êáé ôñéãùíéêÞ áíéóüôçôá), äéÜìåôñïò. ÄÝíôñá (= óõíåêôéêÜ ãñáöÞìáôá
÷ùñßò êýêëïõò).
¸ãéíå ôï ðñþôï 15èÞìåñï äéáãþíéóìá.
Êõ, 8 Ìáñ: Ôá áðïôåëÝóìáôá ôïõ 1ïõ äéáãùíßóìáôïò Ý÷ïõí áíáñôçèåß Ýîù áðü ôï ãñáöåßï ìïõ. Ôá ðëÝïí êïéíÜ ëÜèç Þôáí (á) ç Ýëëåéøç áðëïðïßçóçò ôçò ôåëéêÞò ðáñÜóôáóçò êáé (â) ç ìç äéáßñåóç äéá ôïõ n! ãéá íá áãíïçèåß ç óåéñÜ ìå ôçí ïðïßá ðáñéóôÜíïíôáé ïé ïìÜäåò.
Äå, 9 Ìáñ: ÄÝíôñï ìå n êïñõöÝò Ý÷åé n-1 áêìÝò. ÄÝíôñá ðïõ ðáñÜãïõí (spanning trees), åëÜ÷éóôá äÝíôñá ðïõ ðáñÜãïõí óå ãñáöÞìáôá ìå âÜñç. Áðüäåéîç üôé ï ìõùðéêüò áëãüñéèìïò (greedy algorithm) äßíåé åëÜ÷éóôï äÝíôñï.
Ôå, 11 Ìáñ: Éóïìïñößá ãñáöçìÜôùí. Êýêëùìá êáé ìïíïðÜôé Euler. Áíáãêáßá êáé éêáíÞ óõíèÞêç ãéá ôçí ýðáñîç êõêëþìáôïò Euler. ÁðïóôÜóåéò óå ãñáöÞìáôá ìå âÜñç. Ï áëãüñéèìïò Floyd-Warshall ãéá ôçí åýñåóç ôùí áðïóôÜóåùí áíÜìåóá óå êÜèå æåýãïò êïñõöþí. Áðüäåéîç ôïõ üôé äïõëåýåé. Ï áëãüñéèìïò Dijkstra ãéá ôçí åýñåóç ôùí áðïóôÜóåùí áðü Ýíá óôáèåñü êüìâï óå üëïõò ôïõ õðüëïéðïõò. Áðüäåéîç ôïý üôé äïõëåýåé.
Äå, 16 Ìáñ: ×ñùìáôéóìüò êïñõöþí êáé áêìþí, ÷ñùìáôéêüò áñéèìüò
÷(G) åíüò ãñáöÞìáôïò, ãñÜöçìá ãñáììþí ôïõ G. Ôï Üíù öñÜãìá
÷(G) <= d+1, üðïõ d ï ìÝãéóôïò âáèìüò ôïõ ãñáöÞìáôïò.
¸íá áðëü èåþñçìá ôýðïõ Ramsey (üôé óå êÜèå ÷ñùìáôéóìü áêìþí ôïõ
K6 õðÜñ÷åé êÜðïéï ìïíï÷ñùìáôéêü ôñßãùíï).
ÓõóôÞìáôá îÝíùí áíôéðñïóþðùí (ÓÎÁ) ãéá ïéêïãÝíåéåò õðïóõíüëùí
A1, A2, ..., An ôïõ óõíüëïõ X.
ÅðáãùãéêÞ áðüäåéîç ôïõ èåùñÞìáôïò ôïõ ÃÜìïõ (èåþñçìá Hall).
Ð Ñ Ï Ó Ï × Ç:
Äéáôýðùóá Ýíá èåþñçìá ãéá ôï ÷ñùìáôéêü áñéèìü åíüò ãñáöÞìáôïò ôï ïðïßï åßíáé
ËÁÈÏÓ. Åßðá üôé ï ÷(G) åßíáé Üíù öñáãìÝíïò áðü t+1, üðïõ t åßíáé
ï ìÝóïò âáèìüò ôïõ ãñáöÞìáôïò. Áõôü åßíáé ëÜèïò! Ðñïóðáèåßóôå íá âñåßôå
Ýíá ãñÜöçìá ìå ÷(G) áò ðïýìå ßóï ìå 100 êáé ìå t < 3.
Ç ðñþôç ðñüïäïò èá ãßíåé ôçí åâäïìÜäá ôçò 28çò Ìáñôßïõ. Ç ýëç ðïõ èá åîåôáóôåß èá åßíáé ï,ôé Ý÷ïõìå êáëýøåé ìÝ÷ñé êáé ôçí ðñïçãïýìåíç åâäïìÜäá áðü áõôÞ.
Ìßá óåëßäá óå Postscript ãéá ôï èåþñçìá ôïõ ÃÜìïõ.
Ç ðñüïäïò èá ãßíåé ôçí ÐÝìðôç, 2 Áðñéëßïõ, 8-10ìì, óôá ôñßá áìöéèÝáôñá êáé óôéò áßèïõóåò È201 êáé È207.
Ôå, 18 Ìáñ:
ÅðáíáëÞöèçêå ç áðüäåéîç ôïõ èåùñÞìáôïò ôïõ Hall ãéá óõóôÞìáôá îÝíùí
áíôéðñïóþðùí.
ÓõóôÞìáôá îÝíùí áíôéðñïóþðùí ãéá êáíïíéêÜ óõóôÞìáôá óõíüëùí.
Éóïäýíáìá, äåßîáìå üôé óå êÜèå êáíïíéêü äéìåñÝò ãñÜöçìá õðÜñ÷åé Ýíá ôáßñéáóìá
ôùí áñéóôåñþí êïñõöþí 1-1 ìå ôéò äåîéÝò.
Åðßóçò áó÷ïëçèÞêáìå ìå ôï ÷ñùìáôéêü áñéèìü ôïõ ãñáöÞìáôïò
Cn (êýêëïò ìå n êïñõöÝò).
¸ãéíå ôï äåýôåñï 15èÞìåñï äéáãþíéóìá.
Äå, 23 Ìáñ: Äåí Ýãéíå ìÜèçìá ëüãù áóèÝíåéáò ôïõ äéäÜóêïíôá.
Ôå, 25 Ìáñ: Áñãßá.
¸êôáêôï ìÜèçìá: ÐáñáóêåõÞ, 27 Ìáñôßïõ, 6-8ìì, Áìö. ÂÎ. Èá ãßíïõí êõñßùò áóêÞóåéò.
Óçìåéþóåéò: Ìéá ðïëý óýíôïìç åéóáãùãÞ óôç
èåùñßá ÃñáöçìÜôùí (Postscript).
Å÷ù äþóåé áíôßãñáöá óôï êõëéêåßï ãéá öùôïôýðçóç.
Ç ðñüïäïò èá ãßíåé ôçí ÐÝìðôç, 2 Áðñéëßïõ, 8-10ìì, óôá ôñßá
áìöéèÝáôñá êáé óôéò áßèïõóåò È201 êáé È207.
Á Í Ï É × Ô Å Ó Ó Ç Ì Å É Ù Ó Å É Ò.
Äå, 30 Ìáñ: ÌéëÞóáìå ãéá åðßðåäá ãñáöÞìáôá. Áðïäåßîáìå ôï èåþñçìá ôïõ Euler (V+F = E+2) êáé ôÝëïò ôï èåþñçìá ôùí 5 ÷ñùìÜôùí ("êÜèå åðßðåäïò ÷Üñôçò ìðïñåß íá ÷ñùìáôéóôåß ìå 5 ÷ñþìáôá þóôå ÷þñåò ðïõ ãåéôïíåýïõí íá Ý÷ïõí äéáöïñåôéêÜ ÷ñþìáôá").
Ùñåò áóêÞóåùí: Ôñßôç, 31 Ìáñôßïõ, 8-10ìì, Áìö ÂÎ.
Êõ, 5 Áðñ: Ïé âáèìïß óáò óôçí ðñüïäï âñßóêïíôáé åäþ üðùò êáé ôï éóôüãñáììá üëùí ôùí âáèìþí.
Äå, 6 Áðñ., êáé Ôå, 8 Áðñ.:
ÃåííÞôñéåò óõíáñôÞóåéò áêïëïõèéþí. Ðþò ðÜìå áðü ôçí áêïëïõèßá óôç
ãåííÞôñéá óõíÜñôçóç êáé áíôßóôñïöá. Ðþò ÷ñçóéìïðïéïýíôáé ïé ãåííÞôñéåò
óõíáñôÞóåéò ãéá ôçí åýñåóç êëåéóôïý ôýðïõ ãéá áêïëïõèßåò ìÝóù åýñåóçò
êëåéóôïý ôýðïõ ãéá ôéò ãåííÞôñéåò óõíáñôÞóåéò ôïõò êáé åöáñìïãÞ ôçò
ìåèüäïõ êõñßùò óå áíáäñïìéêÜ ïñéæüìåíåò áêïëïõèßåò.
ÌåãÜëç Ýìöáóç äßíåôáé óôçí éêáíüôçôá íá âñßóêåé êáíåßò Ýíá êëåéóôü ôýðï
ãéá ãåííÞôñéá óõíÜñôçóç ìéáò áêïëïõèßáò êáô'åõèåßáí áðü ôç óõíäõáóôéêÞ
ðåñéãñáöÞ ôçò áêïëïõèßáò.
Ôçí ÔåôÜñôç, 29 Áðñéëßïõ, èá ãßíåé ôï åðüìåíï äéáãþíéóìá ðÜíù óôçí 5ç êáé 6ç ïìÜäá áóêÞóåùí.
Äå, 27 Áðñ., êáé Ôå, 29 Áðñ.: ÅéóáãùãÞ óôç ÄéáêñéôÞ Ðéèáíüôçôá. Ï Äåéãìáôéêüò ×þñïò Ù êáé ç ðéèáíüôçôá åíüò åíäå÷ïìÝíïõ (õðïóõíüëïõ ôïõ Ù). Ðáñáäåßãìáôá. ÌïéñÜóôçêå ç 7ç ïìÜäá áóêÞóåùí.
Êõ, 3 Ìáúïõ: Ïé âáèìïß óáò ãéá ôï 3ï äéáãþíéóìá âñßóêïíôáé åäþ.