Algorithmics and Combinatorics in Graphs. Heuristic Methods
Code: 104388 ECTS Credits: 6| Degree | Type | Year |
|---|---|---|
| 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.
Teh final marks will be:
- The weighted average according to the weight of each part for those students who have obtained 3.5 or more in all parts.
- The minimum between 3.5 and the weighted average according to the weight of each part for those students who have done any of the individual evaluations and in any of the parts does not reach 3.5.
- Not assessable for those students who have not done any of the individual evaluations.
Those who have been evaluated in all three parts and do not pass the subject may present themselves for a retake of the final exam and the individual practical work. In particular, those who have not submitted the individual practical work and the final exam will not be able to present themselves for retake.
This subject does not allow a unique evaluation procedure.
[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. Avantatges inconvenients de cada una de les opcions: Wikipedia i notes del curs
- Cà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
Groups and Languages
Please note that this information is provisional until 30 November 2025. You can check it through this link. To consult the language you will need to enter the CODE of the subject.
| 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 |