|
|
Main menu for Browse IS/STAG
Course info
KIV / VAM-E
:
Course description
Department/Unit / Abbreviation
|
KIV
/
VAM-E
|
Academic Year
|
2023/2024
|
Academic Year
|
2023/2024
|
Title
|
Selected Algorithmical Methods
|
Form of course completion
|
Exam
|
Form of course completion
|
Exam
|
Accredited / Credits
|
Yes,
5
Cred.
|
Type of completion
|
Combined
|
Type of completion
|
Combined
|
Time requirements
|
Lecture
2
[Hours/Week]
Tutorial
2
[Hours/Week]
|
Course credit prior to examination
|
Yes
|
Course credit prior to examination
|
Yes
|
Automatic acceptance of credit before examination
|
No
|
Included in study average
|
YES
|
Language of instruction
|
English
|
Occ/max
|
|
|
|
Automatic acceptance of credit before examination
|
No
|
Summer semester
|
0 / -
|
0 / -
|
1 / -
|
Included in study average
|
YES
|
Winter semester
|
0 / -
|
0 / -
|
0 / -
|
Repeated registration
|
NO
|
Repeated registration
|
NO
|
Timetable
|
Yes
|
Semester taught
|
Summer semester
|
Semester taught
|
Summer semester
|
Minimum (B + C) students
|
10
|
Optional course |
Yes
|
Optional course
|
Yes
|
Language of instruction
|
English
|
Internship duration
|
0
|
No. of hours of on-premise lessons |
|
Evaluation scale |
1|2|3|4 |
Periodicity |
každý rok
|
Evaluation scale for credit before examination |
S|N |
Periodicita upřesnění |
|
Fundamental theoretical course |
No
|
Fundamental course |
No
|
Fundamental theoretical course |
No
|
Evaluation scale |
1|2|3|4 |
Evaluation scale for credit before examination |
S|N |
Substituted course
|
None
|
Preclusive courses
|
KIV/VAM
|
Prerequisite courses
|
N/A
|
Informally recommended courses
|
N/A
|
Courses depending on this Course
|
KIV/GAM, KMA/TIS
|
Histogram of students' grades over the years:
Graphic PNG
,
XLS
|
Course objectives:
|
To learn students fundamental algorithms for the area of applied computational geometry, but also to create their own algorithms for the problems from the given area, to lead the students to thinking.
|
Requirements on student
|
Processing of a set of middle-size projects oriented to development, implementation or presentation of algorithms from the area of applied computational geometry. The student chooses an amount, topics and a type of work (theoretical, presentational, implementational) him or herself from the given list in such a way to achieve at least the minimum required ammount of points. Other points can be obtained for activity in seminars. Points are included in the exam evaluation. The exam is written and oral.
|
Content
|
1. Examples of solved problems, application areas, degeneracy and robustness, complexity and evaluation of algorithms, fundamental techniques, geometric predicates
2.-3. Geometric location - point location, range search, applications
4. Convex hulls - 2D, 3D, on-line problem, applications
5.-6. Voronoi diagrams - properties, construction, applications, dualization, less usual types of Voronoi diagrams
7.-8. Triangulations in 2D - Delaunay, greedy, MWT, DDT, multicrietria-optimized, constrained triangulations, applications
9. Triangulations in 3D - complications against 2D, properties, applications, Delaunay 3D triangulation
10. Triangulation and partition of polygons, art gallery problem
11. Intersections of basical geometric shapes - lines, polygons
12. Motion planning for robots - a point robot movement, a disk, convex polygon and ledder translation in 2D
13. Other interesting geometric algorithms and data structures, trends and news in computational geometry
|
Activities
|
|
Fields of study
|
Podklady přednášek (soubory formátu pdf).
|
Guarantors and lecturers
|
|
Literature
|
|
Time requirements
|
All forms of study
|
Activities
|
Time requirements for activity [h]
|
Contact hours
|
52
|
Preparation for an examination (30-60)
|
35
|
Presentation preparation (report) (1-10)
|
5
|
Individual project (40)
|
40
|
Total
|
132
|
|
Prerequisites
|
Knowledge - students are expected to possess the following knowledge before the course commences to finish it successfully: |
Knowledge of algorithmics and programming at least on the level of the KIV/PPA2 course and knowledge of English at least on the level enabling to read articles in English are expected. |
|
Learning outcomes
|
Knowledge - knowledge resulting from the course: |
Knowledge of fundamental problems and their typical solutions in the area of applied computational geometry, ability to develop a suitable original solution. The graduate of the course should be able to choose or develop an algorithm suitable for the given problem and to be able to estimate how the given algorithm will behave in real life. |
|
Assessment methods
|
Knowledge - knowledge achieved by taking this course are verified by the following means: |
Combined exam |
Portfolio |
Seminar work |
Project |
Individual presentation at a seminar |
|
Teaching methods
|
Knowledge - the following training methods are used to achieve the required knowledge: |
Interactive lecture |
Multimedia supported teaching |
Project-based instruction |
Self-study of literature |
Individual study |
Students' portfolio |
Seminar classes |
|
|
|
|