Since discrete mathematics was considered to have begun some 275 years ago, it has evolved into a subject with a fascinating
history, a host of interesting problems and numerous diverse applications.
While discrete mathematics has developed ever-increasing connections with other areas of mathematics, engineering, and a variety of scholarly fields, it is its beauty that has attracted so many to it.
In this lecture, you will learn techniques to efficiently solve discrete mathematical problems.
In particular, we will introduce some topics such as combinatorial geometry, visibility, object packing problems, Job-scheduling problems, and shortest path network.
While discrete mathematics has developed ever-increasing connections with other areas of mathematics, engineering, and a variety of scholarly fields, it is its beauty that has attracted so many to it.
In this lecture, you will learn techniques to efficiently solve discrete mathematical problems.
In particular, we will introduce some topics such as combinatorial geometry, visibility, object packing problems, Job-scheduling problems, and shortest path network.
- To understand some results on combinatorial geometry.
- To understand some problems on visibility and its application.
- Master the fundamental of the shortest network and to understand its application.
- Master the fundamental of the packing problem and to understand its application.
| Class schedule | HW assignments (Including preparation and review of the class.) | Amount of Time Required | |
|---|---|---|---|
| 1． | Set of points with integer distance, and the number of occurrences of integer distance. | Check this syllabus. | 10minutes |
| Read Section 1.1 and 1.2 of the textbook. | 170minutes | ||
| Verify the properties of trigonometric functions and determinants. | |||
| 2． | Relationship the set of points and that of lines. | Read Section 1.3 and 1.4 of the textbook. | 90minutes |
| Confirm the definition "general position". | 20minutes | ||
| For a set with integer distances, summarize the difference between a finite number of point sets and infinite number of point sets. | 70minutes | ||
| 3． | Geometric arrangements. | Read Section 2.1, 2.2 and 2.3 of the textbook. | 90minutes |
| Enumerate and compare the numbers and shapes of points to be encapsulated that appear in each theorem. | 100minutes | ||
| 4． | Intersection Patterns of Convex sets. | Read Section 2.4 and 2.5 of the textbook. | 90minutes |
| Confirm the definition "convex polygon". | 30minutes | ||
| Consider the unsolved problems expected from the theorems in Section 2.1 - 2.3 of the textbook. | 60minutes | ||
| 5． | Visibility (Art gallery problem) | Read Chapter 3 of the textbook. | 120minutes |
| Confirm terms in graph theory such as "maximal plane graph" and "coloring". | 70minutes | ||
| 6． | Visibility (Gard-person problem) | Read Chapter 4 of the textbook. | 90minutes |
| Confirm a term in graph theory "1-factor". | 30minutes | ||
| Confirm the difference between art gallery problems and fortress problems. | 70minutes | ||
| 7． | Shortest path network (Spanning tree and Steiner tree) | Read Section 5.1, 5.2 and 5.3 of the textbook. | 90minutes |
| Confirm a term in graph theory "tree". | 30minutes | ||
| Confirm the difference between art gallery problems, fortress problems, and gard-person problems. | |||
| 8． | Shortest path network (Melzak's Algorithms) | Read Section 5.4 and 5.5 of the textbook. | 90minutes |
| Confirm the definition "Steiner tree". | 30minutes | ||
| Confirm the difference between the minimum spanning tree problem and the Steiner problem. | 70minutes | ||
| 9． | Packing problems（circles) | Read Section 6.1 and 6.2 of the textbook. | 90minutes |
| Confirm the definition of "Voronoi diagram" and "close-packing". | 30minutes | ||
| Investigate the modified results of Melzak's algorithm. | 70minutes | ||
| 10． | Packing problems（rectangles) | Read Section 6.3 of the textbook. | 90minutes |
| Consider if Theorem 6.10 can be improved. | 40minutes | ||
| Summarize the packing method the unit circle in the 3 * 1000 area. | 60minutes | ||
| 11． | Job-scheduling problems (independent tasks) | Read Section 7.1 of the textbook. | 90minutes |
| Confirm the difference between LIST and LIST DEC. | 100minutes | ||
| 12． | Job-scheduling problems (order-restricted tasks) | Read Section 7.2 and 7.3 of the textbook. | 90minutes |
| Confirm the differences from independent task problems. | 100minutes | ||
| 13． | Unsolvable problems by computer 1 | Read Section 8.1 and 8.2 of the textbook. | 90minutes |
| Investigate the person A. Turing. | 100minutes | ||
| 14． | Unsolvable problems by computer 2 | Read Section 8.3 and 8.4 of the textbook. | 90minutes |
| Examine P and NP in computation theory. | 40minutes | ||
| Solve the problem on page 154. | 60minutes | ||
| Total. | - | - | 2560minutes |
| term papers | Total. | |
|---|---|---|
| 1. | 25% | 25% |
| 2. | 25% | 25% |
| 3. | 25% | 25% |
| 4. | 25% | 25% |
| Total. | 100% | - |
Introduction to discrete mathematics (in Japanese)，J. Akiyama and R.L.Graham, Asakura publishing co.
- Course that cultivates an ability for utilizing knowledge
- Course that cultivates a basic problem-solving skills
Last modified : Wed Oct 17 07:46:17 JST 2018