Algorithmics and Combinatorics in Graphs. Heuristic Methods
Code: 104388 ECTS Credits: 6| Degree | Type | Year |
|---|---|---|
| 2503740 Computational Mathematics and Data Analytics | FB | 1 |
Contact
- Name:
- Albert Ruiz Cirera
- Email:
- albert.ruiz@uab.cat
Teachers
- Albert Ruiz Cirera
Teaching groups languages
You can view this information at the end of this document.
Prerequisites
It is recommended that the student has taken Mathematics in the two baccalaureate courses and has examined this matter in the PAU.
[Translated from the Catalan version by Google translator]
Objectives and Contextualisation
- Know the combinatorial graphs and their terminology.
- Know the different search algorithms and movement in graphs.
- Know the types of dynamic data for representation of graphs and their implemtation in C.
- Know the basic algorithms of optimal searches in graphs and their complexity.
[Translated from the Catalan version by Google translator]
Learning Outcomes
- KM02 (Knowledge) Distinguish the objects of calculus with functions and their properties and uses.
- KM05 (Knowledge) Describe the mathematical concepts and objects specific to the graph theory.
- SM05 (Skill) Develop independent strategies to solve problems specific to numerical calculus, probability and graph theory.
Content
- Combinatorial algorithms for graphics.
- Combined graphs and graph searches.
- Theory of graphs: introduction.
- Search in graphs: Depth-first and Breadth-first.
- Greedy Algorithms.
- Recursion.
- Abstract data types: Dynamic lists and trees.
- Graphic representation algorithms. Advantatges and disadvantages of each of the options.
- Abstract and dynamic data types for graphs and their implementation in C.
- Basic algorithms for optimal search graphs and their complexity.
- Calculation of distances from latitude and longitude.
- Algorithm of Dijkstra for optimal routes in graphs.
- Algorithm A *: heuristic search for optimal paths in graphs.
[Translated from the Catalan version by Google translator]
Activities and Methodology
| Title | Hours | ECTS | Learning Outcomes |
|---|---|---|---|
| Type: Directed | |||
| Attend the theoretical and practical classes | 49 | 1.96 | |
| Type: Supervised | |||
| Completion of the practices | 62 | 2.48 | |
| Type: Autonomous | |||
| Resolution of complementary exercises | 30 | 1.2 |
The weekly sessions of the subject will be divided, usually, in two parts:
- A theoretical part in which the teacher will introduce the concepts, methods and examples related to the syllabus of the subject.
- A practical part in which students will be proposed a series of problems or exercises in which they will be shown and a concrete work will be worked on that which has been seen in the theoretical part. Each practice will have a different statement, which will be published on the Virtual Campus and will involve the delivery of the answers to some questions raised.
Complementary exercises will also be proposed as an autonomous activity to help them understand the applied part of the subject.
[Translated from the Catalan version by Google translator]
Annotation: Within the schedule set by the centre or degree programme, 15 minutes of one class will be reserved for students to evaluate their lecturers and their courses or modules through questionnaires.
Assessment
Continous Assessment Activities
| Title | Weighting | Hours | ECTS | Learning Outcomes |
|---|---|---|---|---|
| Delivery of practical exercices | 25% | 0 | 0 | KM02, KM05, SM05 |
| End of term exam | 40% | 4 | 0.16 | KM02, KM05, SM05 |
| Individual practical work | 35% | 5 | 0.2 | KM02, KM05, SM05 |
The evaluation will consist of the following activities:
- A final exam, which accounts for 40% of the note.
- An individual practical work with a delivery period where it will be necessary to develop and implement algorithms, which account for 35% of the note.
- Delivery, during practical sessions, of practical exercises that will be carried out in groups of two. They count 25% of the note. This is a continuous evaluation activity and is not recoverable.
The minimum grade in each of the three evaluation activities to be able to pass the subject is 3.5 points out of 10.
Final exam and individual practical work are recoverable for those studients who have participated in the three items of the evaluation but have not passed the subject.
[Translated from the Catalan version by Google translator]
Bibliography
- Fundamentos de programación (algoritmos, estructuras de datos y objetos), Luis Joyanes, McGraw-Hill, Madrid etc. (2003).
- Algoritmos y estructuras de datos – una perspectiva en C, Luis Joyanes y Ignacio Zahonero, McGraw-Hill, Madrid etc. (2004).
- Grafs combinatòris i cerques en gràfs:Wikipedia
- Tipus abstractes de dades i programació orientada a objectes: Llistes dinàmiques i arbres; Tipus abstractes i dinàmics de dades per a grafs i la seva implementació en C.
- Notes del curs
- Algoritmos + Estructura de datos = Programas, Niklaus Wirth, Ediciones del Castillo, Madrid (1986).
- C algoritmos, programación y estructuras de datos, Luis Joyanes Aguilar et al., McGraw-Hill, Madrid etc. (2005).
- Algorismes de representació de grafs. Avantatgews inconvenients de cada una de les opcions: Wikipedia i notes del curs
- ACàlcul de distàncies a partir de la latitud i la longitud: Wikipoedia i notes del curs
- Algorisme de Dijkstra per a rutes òptimes en grafs: Presentació d'Eric Demaine
- Algorisme A*: cerca heurística per a rutes òptimes en grafs
- Heuristics: Intelligent Search Strategies for Computer Problem Solving, Judea Pearl
Addison-Wesley Pub (Sd) | ISBN: 0201055945 | 1984-04 | djvu (ocr) | 399 pages | 3.66 Mb
Pagines: 33 to 46, 48, 49, 64, 65, 73--85.L'exemple a les pàgines 52--54 pot ser relevant.
Software
C
Language list
| Name | Group | Language | Semester | Turn |
|---|---|---|---|---|
| (PLAB) Practical laboratories | 1 | Catalan | second semester | morning-mixed |
| (SEM) Seminars | 1 | Catalan | second semester | morning-mixed |
| (TE) Theory | 1 | Catalan | second semester | morning-mixed |