강 의 계 획 서

2009 학년도 제 1 학기

교과구분	정보과학과	학점	3	담당교원	김용주	강의실	창조관 701호
교과목명	이산구조	담당시수	3	연구실		수강대상
				창조관 707호		07학번

목 표	집합론, 조합론, 그래프이론 그리고 대수학 등에서 컴퓨터과학을 연구하는데 있어서 기본적이고도 유용한 집합과 증명, 계산가능과 순열 조합, 관계 와 함수, 그래프, 트리 등의 구조와 오토마타, 알고리즘의 분석, 수열, 재귀식과 Group, Ring, boolean algebra등의 algebraic system등에 대한 추상적인 개념들을 다룬다. 학생들은 본 교과목의 학습을 통하여 컴퓨터 과학에서 수학이 어떻게 응용되는지에 대하여 학습하고 몇 가지 수학적인 강력한 도구들을 학습함과 동시에 수학적인 문제들을 이해하고 정형화하여 풀어내는 능력을 개발하며 알고리즘적 관점에서 몇 가지 주제에 대하여 학습한다
단 원	주 요 내 용
Sets and Logic Proof Functions, Sequences, and Relations Algorithms Introduction to Number Theory Counting Methods and the Pigeonhole Principle Recurrence Relations Graph Theory Tree Network Models Boolean Algebras Automata, Grammars, and Languages Computational Geometry	Sets, Propositions, Conditional Propositions and Logical Equivalence, Arguments and inference rules of Inference, Quantifiers, Nested Quantifiers Mathematical Systems, Direct Proofs, and Cunter examples, More Methods of Proof Resolution Proofs, Mathematical Induction, Strong Form of Induction and the Well-Ordering Property, Functions, Sequences and Strings Relations, Equivalence Relations, Matrices of Relations, Relational Databases Analysis of Algorithms, Recursive Algorithms Divisors, Representations of Integers and Integer Algorithms, The Euclidean Algorithm, The RSA Public-Key Cryptosystem Basic Principles, Permutations and Combinations, Generalized Permutations and Combinations, Algorithms for Generating Permutations and Combinations, Discrete Probability Theory, Binomial Coefficients and Combinatorial Identities, The Pigeonhole Principle Solving Recurrence Relations, Applications to the Analysis of Algorithms Paths and Cycles, Hamiltonian Cycles and the Traveling Salesperson Problem A Shortest-Path Algorithm, Representations of Graphs Isomorphisms of Graphs, Planar Graphs, Instant Insanity Terminology and Characterizations of Trees Spanning Trees, Minimal Spanning Trees, Binary Trees, Tree Traversals Decision Trees and the Minimum Time for Sorting, Isomorphisms of Trees, Game Trees, A Maximal Flow Algorithm, The Max Flow, Min Cut Theorem, Matching Combinatorial Circuits, Properties of Combinatorial Circuits, Boolean Algebras Boolean Functions and Synthesis of Circuits, Applications Sequential Circuits and Finite-State Machines, Finite-State Automata Languages and Grammars, Nondeterministic Finite-State Automata Relationships Between Languages and Automata The Closest-Pair Problem, An Algorithm to Compute the Convex Hull

1.  교과목의 개요

2.  교재 및 참고도서

가.  교    재  :

-	Richard Johnsonbaugh, Discrete mathematics (6Ed), Prentice Hall

나.  참고도서  :

-	B. Kolman, R. C. Busby, and S. C. Ross, Discrete Mathematical Structures, (4th edition.), Prentice-Hall

-  K. L. Rosen, Discrete Mathematics and its Applications, (5th edition), McGraw-Hill

3.  평가방법

수행평가			중간평가	기말평가	출 결 및 수업태도	합 계	비 고
개별과제	퀴즈
25%	10%		25%	30%	10%	100%

4.  주별 강의계획서

주 별	강 의 및 실 험 내 용	과제 및 기타 참고사항
제1주	Sets and logic	개별과제, 발표
제2주	Proofs	개별과제, 발표
제3주	Functions, sequences, and relations	개별과제, 발표
제4주	Algorithms	개별과제, 발표
제5주	Introduction to Number Theory	개별과제, 발표
제6주	Counting Methods and the Pigeonhole Principle	개별과제, 발표
제7주	Recurrence Relations	개별과제, 발표
제8주	mid-term exam
제9주	Graph Theory	개별과제, 발표
제10주	Trees	개별과제, 발표
제11주	Network Models	개별과제, 발표
제12주	Network Models, Boolean Algebras	개별과제, 발표
제13주	Boolean Algebras	개별과제, 발표
제14주	Automata, Grammars, and Languages	개별과제, 발표
제15주	Computational Geometry	개별과제, 발표
제16주	final exam

♣ 작성요령 : 1란의 “교과목 개요”는 상세하게 작성한다.

3란의 “평가방법”의 평가요소와 반영비율은 학과별 협의에 따른다.