°­ÀÇ °³¿ä

   ÀÌ»ê¼öÇÐ(Discrete Mathematics, ìÆߤâ¦ùÊ)À̶õ ¿¬¼ÓÀû ¼ºÁúÀ» °®´Â ´ë»ó°ú´Â ´Þ¸® ÀÌ»êÀûÀÎ ¾ç ¶Ç´Â À̻걸Á¶¸¦ °®´Â ´ë»ó¿¡ ´ëÇÏ¿©  ¼öÇÐÀûÀ¸·Î ºÐ·ùÇÏ°í Á¤¸®Çϸç, ³í¸®ÀûÀ¸·Î »ç°íÇÏ¿© ¹®Á¦¸¦ ÇØ°áÇÏ´Â ¿©·¯ ÀÌ·ÐÀ» ÅëƲ¾î ´Ù·ç´Â Çй®À» ¸»ÇÑ´Ù. ¶Ç,±¸Ã¼ÀûÀÌ°í ÀÌ»êÀûÀÎ ¿©·¯ ¹®Á¦¸¦ ´Ù·ç¹Ç·Î Concrete Mathematics¶ó°íµµ ºÎ¸¥´Ù.  

   º» °­Á¿¡¼­´Â ÀÌ»ê¼öÇÐÀÇ ¿©·¯ ÀÌ·Ð Áß¿¡¼­ ÀüÅëÀû Á¶ÇÕ·ÐÀÇ ¿µ¿ªÀÎ ¼±Åðú ¹è¿­ÀÇ ´Ù¾çÇÑ ÀÌ·Ð, Fibonacci ¼ö¿­°ú °ü·ÃÇÑ ¿©·¯ ÀÌ·Ð, ¿©·¯ °¡Áö recursion¿¡ °üÇÑ ÀÌ·Ð, ±×·¡ÇÁÀÌ·Ð, ¾Ë°í¸®Áò, µðÀÚÀΰú ÃÊµî ¾ÏÈ£ÀÌ·Ð, ÃÖÀûÈ­¹®Á¦ µîÀ» ÇнÀÇÔÀ¸·Î½á Çö´ë¼öÇÐÀÇ »õ·Î¿î ¿µ¿ªÀ¸·Î ¿©·¯ °¡Áö Áß¿äÇÑ ÀÀ¿ëÀ» °®°í ÀÖ´Â ÀÌ»ê¼öÇаú Á¶ÇÕ·ÐÀÇ ±âÃʸ¦ °øºÎÇÏ´Â °ÍÀ» ÁÖµÈ ÇнÀ¸ñÇ¥·Î ÇÑ´Ù.

 

 ÇнÀ ¸ñÇ¥

 Á¦ 7Â÷ ±³À°°úÁ¤¿¡¼­ »õ·Î µ¶¸³°ú¸ñÀ¸·Î ¿î¿µµÇ´Â ÀÌ»ê¼öÇÐ ±³°ú¿¡¼­ ´Ù·ç´Â ´Ù¾çÇÑ ÀÌ·ÐÀ» ÇнÀÇÏ°í  È¿À²Àû Áöµµ¹æ¹ý¿¡ °üÇÏ¿© ¿¬±¸ÇÏ´Â °ÍÀ» ÁÖµÈ ÇнÀ¸ñÇ¥·Î ÇÑ´Ù.

 ±¸Ã¼Àû ³»¿ë±³À°À» »ìÆ캸¸é, ¿©·¯ °¡Áö ¼¼±âÀÇ ¹æ¹ý, ÀÌÇ×Á¤¸®¿Í ´ÙÇ×Á¤¸®, Æ÷ÇÔ ¹èÁ¦ÀÇ ¿ø¸®, Fibonacci ¼ö¿­¿Í ±× ÀÀ¿ë¿¡ °üÇÑ ÀÌ·Ð, ¸ðÇÔ¼öÀÌ·Ð, ±×·¡ÇÁÀÌ·Ð, ¾ÏÈ£ÀÌ·Ð µî ´Ù¾çÇÑ ÀÌ»ê¼öÇÐÀÇ ³»¿ëÀ» ÇнÀÇÏ°í ÀÌ»ê¼öÇÐ ±³À°°úÁ¤ µîÀ» ¾Ë¾Æº»´Ù.  Æ¯È÷,  Çö´ë¼öÇÐÀÇ ¿©·¯ ºÐ¾ß¿¡¼­ Áß¿äÇÑ ÀÀ¿ëÀ» °®°í ÀÖ´Â ÀÌ»ê¼öÇÐÀÇ ´Ù¾çÇÑ ³»¿ëÀ» ÇнÀÇÏ°í È¿À²ÀûÀÎ Áöµµ¹æ¹ýÀ» Ž±¸Çϴµ¥ ±³À°ÀÇ ÁßÁ¡À» µÐ´Ù.

 

 ±³Àç ¹× Âü°íµµ¼­

 

   ´ÙÀ½¿¡ Á¦½ÃµÈ ±³À縦 ÁÖ¿äÇÑ Âü°íµµ¼­·Î »ç¿ëÇϱ⠹ٶó¸ç,   Æ¯º°È÷ Á¤ÇØÁø ±³°ú¼­´Â ¾ø½À´Ï´Ù.  ÀÌ»ê¼öÇР¶Ç´Â Á¶ÇÕ·Ð;  ¶Ç ¿µ¹®À¸·Î´Â Discrete Mathematics ¶Ç´Â Combinatorial  Theory µîÀÇ Á¦¸ñÀ» °¡Áø ¼­ÀûÀ»Âü°íÇÏ¿© ÇнÀÇϱ⠹ٶø´Ï´Ù.   

   ¾Æ·¡¿¡ Á¦½ÃµÈ Âü°í¹®Çå Áß¿¡¼­  B. Kolman, R.C. Bussy & S. RossÀÇ Àú¼­´Â ƯÈ÷ 9Àå 1-3Àý°ú 11Àå 1-2Àý °­ÀÇ¿¡  Âü°íÇϱ⠹ٶø´Ï´Ù.

¹ÚÁ¾¾È ¿Ü 2ÀÎ, ÀÌ»ê¼öÇÐ, °æ¹®»ç, 2006.

±è¿ø±Ô, ÀÏÁ¤°­½À °­ÀÇ·Ï, ÃæºÏ´ë ÁߵÀ°¿¬¼ö¿ø, 2005.

ÀÌ»ê¼öÇÐ ¹× ±³»ç¿ë Áöµµ¼­ (±³À°ºÎ, Á¦7Â÷ ±³À°°úÁ¤)  

ÀüÁ¾¿ì.±è¿ìö,  È®·ü·Ð ÀÔ¹®, ¿µÁö¹®È­»ç, 1986.

Àü¹®¼®, ÀÌ»ê¼öÇÐ,  È«¸ª°úÇÐÃâÆÇ»ç, 1992.

 

M.O. Albertson & J.P. Hutchinson,  Discrete Mathematics with Algorithms,  Wiley, 1988.

 R. Graham, D. Knuth & O. Patashnik,  Concrete Mathematics,  Addison-Wesley, 1989.

 B. Kolman, R.C. Bussy & S. Ross,  Discrete Mathematical Structures, Prentice Hall, 1987.

 N. L. Biggs,   Discrete  Mathematics,  Oxford Science Publications, 1989.

 R.C. Bose & B. Manvel, Introduction to Combinatorail Theory, John Wiley & Sons, 1984.

 R. Brualdi,  Introductory Combinatorics, North-Holland, 1977.

 M. Hall, Combinatorial Theory, Wiley Interscience, 1986.

  R.M. Young, Excursions in Calculus, MAA, 1992.


  Course  Perspective 

 

 Interests  in computer science and the use of computer applications, together with connections to many real-world situations, have helped make topics of discrete mathematics more commonplace  in  school and university curricula.   A topic of widespread application and interest is combinatorics,  the study of counting techniques.  Enumeration, or counting, may strike one as an obvious process that a student learns when first studying arithmetic. But then, it seems, very little attention is paid to further developments in counting as the student turns to "more difficult" areas in mathematics, such as algebra, geometry, trigonometry, and calculus. . . . Enumeration [however] does not end with arithmetic. It also has applications in such areas as coding theory, probability, and statistics (in mathematics) and in the analysis of algorithms (in computer science). [Ralph P. Grimaldi, in Discrete and Combinatorial Mathematics, 1994, p. 3]   

  Combinatorial Analysis is an area of mathematics concerned with solving problems for which the number of possibilities is finite (though possibly quite large). These problems may be broken into three main categories: determining existence, counting, and optimization. Sometimes it is not clear whether a problem has a solution or not. This is a question of existence. In other cases solutions are known to exist, but we want to know how many there are. This is a counting problem. Or a solution may be desired that is "best" in some sense. This is an optimization problem. [John A. Dossey, Albert D. Otto, Lawrence E. Spence, & Charles V. Eynden, in Discrete Mathematics, 1987, p. 1]

   Current documents that support the reform of school mathematics education suggest the need for increased attention to topics in discrete mathematics as well as in probability and statistics. The topic of combinatorics--counting--is mentioned in the National Council of Teachers of Mathematics standards documents and in the Mathematical Association of America's recommendations for teacher preparation as a topic area worthy of study by middle school and high school teachers.

   This quarter, we will study and apply combinatorial techniques in a variety of settings.  In doing so, we will make connections to algebra, probability, and many other topics in mathematics. During the course, we may also study the process of proof by induction, the use of recursion, and the graph theory and knot theory and more.


 Contact Information

 

Room 82-105,  ÃæºÏ´ëÇб³ »ç¹ü´ëÇÐ
Wednesday  3:00-5:00 pm
E-mail: wkkim@chungbuk.ac.kr
FAX:  043-275-2715

 

 Course Requirements and Grading Scale

 

Problem Sets & Quizzes (20%)
These will be weekly assignments by webboard,  and several quizzes during the course.

Test  (20%)
One exam will be given during the course.
The test is tentatively scheduled for the mid week of the Quarter.

Final Examination (60%)

The test is scheduled for the last week of the Quarter.

 

  °­ÀÇ ÀÏÁ¤

 

 1 ÁÖ

ÀÌ»ê¼öÇп¡¼­ ÀüÇüÀûÀÎ ³× °¡Áö ¹®Á¦

1Àå 1Àý MAGIC CARD¹®Á¦

1Àå 2Àý ºñµÑ±âÁýÀÇ ¿ø¸®

1Àå 3Àý ÇϳëÀÌž ¹®Á¦

1Àå 4Àý °ÝÀÚ´Ù°¢Çü ¹®Á¦

 2 ÁÖ

´Ù¾çÇÑ ¼¼±â ¹æ¹ý

2Àå 1Àý µÎ°¡Áö ¼¼±â(counting)ÀÇ ¹æ¹ý

2Àå 2Àý ¼ø¼­°¡ ¾ø´Â ¼±ÅÃÀÇ ¹®Á¦

2Àå 3Àý  È®·ü(probability)°ú ±× ÀÀ¿ë

2Àå 4Àý  Á¶°ÇºÎ È®·ü°ú ±×  ÀÀ¿ë  

 3 ÁÖ

ÀÌÇ×Á¤¸®¿Í ±× ÀÀ¿ë

3Àå 1Àý  ÀÌÇ×Á¤¸®

3Àå 2Àý  ´Ù¾çÇÑ ÀÌÇ×Ç×µî½Ä

3Àå 3Àý  ´ÙÇ×Á¤¸®

3Àå 4Àý  ´ÙÇ×Á¤¸®¿Í ±× ÀÀ¿ë

 4 ÁÖ

Enumeration

4Àå 1Àý  Fibonacci ¼ö¿­°ú ±× ÀÀ¿ë

4Àå 2Àý  ¼±Çü Diophantine ¹æÁ¤½Ä

4Àå 3Àý  Æ÷ÇÔ¹èÁ¦ÀÇ ¿ø¸®

4Àå 4Àý  Æ÷ÇÔ¹èÁ¦ÀÇ ¿ø¸®ÀÇ ÀÀ¿ë

 5 ÁÖ

More Enumeration

5Àå 1Àý  PascalÀÇ »ï°¢ÇüÀÇ ÀÀ¿ë   

5Àå 2Àý  ºÐÇÒ 

5Àå 3Àý  Generating functions 

5Àå 4Àý  Golden ratio and Fibonacci NumberI

6 ÁÖ

recursion°ú  

±× ÀÀ¿ë I

6Àå 1Àý  Fibonacci ¼ö¿­°ú Á¡È­½Ä  I

6Àå 2Àý  Fibonacci ¼ö¿­°ú  Á¡È­½Ä  I I  

6Àå 3Àý  ¼öÇÐÀû ±Í³³¹ý°ú À¯ÇÑÂ÷ºÐ

6Àå 4Àý  Æ÷ÇÔ¹èÁ¦ÀÇ ¿ø¸® I I  

7 ÁÖ

recursion°ú  

±× ÀÀ¿ë II

7Àå 1Àý  Recursion°ú  Sierpinski Gasket  

7Àå 2Àý  Recursion°ú  Zeno's Paradox

7Àå 3Àý  Recursion and Fractal

7Àå 4Àý  Recursion and Chaos

8 ÁÖ

±×·¡ÇÁÀÌ·Ð

8Àå 1Àý  ±×·¡ÇÁÀÇ °³³ä

8Àå 2Àý  subgraphI

8Àå 3Àý  regular & bipartite graph  

8Àå 4Àý  Eulerian & Hamiltonian graphI

9 ÁÖ

¿©·¯ °¡Áö discreteÇÑ

±¸Á¶µé

9Àå 1Àý  ¿©·¯ °¡Áö ÇÔ¼ö °³³ä 

9Àå 2Àý  Relations and Digraphs

9Àå 3Àý  Order Relations and Lattices

9Àå 4Àý Iterated Function

10ÁÖ

¾ÏÈ£À̷аú ±× ÀÀ¿ë 

10Àå 1Àý  Coding Theory

10Àå 2Àý  An Error-Correcting Code

10Àå 3Àý Hamming 1-Error Correcting Code

10Àå 4Àý Hamming 1-Error Correcting Code

11ÁÖ

Four Color Problem and Knot Theory 

11Àå 1Àý  Semigroups and Groups

11Àå 2Àý  Finite State Machines

11Àå 3Àý  Four Color Problem

11Àå 4Àý  Knot  Theory

12ÁÖ

Final Examination