Algoritmo guloso

Abstract

This research aims to study the Greedy Algorithm, a type of optimization algorithm, and some of its applications, in order to develop a didactic sequence to be applied with secondary level students. In the study, the construction and logic of the algorithm were related to the graph and trees, concepts which were previously studied and analyzed as requisites to the comprehension of the properties and characteristics of the algorithm. Firstly, we synthetized the elaboration of the Theory of Graphs; then, we presented some concepts about graphs in general, such as its de nition, properties, classi cations and percusses. Next, we de ned trees - a special type of graph - and studied some of its fundamentals theorems for the comprehension of the algorithm, as well as some methods of codi cation such as the Pr ufer code. Finally, we de ned the Greedy Algorithm, specially the Kruskal algorithm, using a practical setting in order to exemplify its application. After the theoretical fundaments, we develop a didactical sequence to be applied in ve classes. In this didactical sequence, activities which involve graphs and trees were progressively applied, with contextualized questions such as exercises in such a way that in the last class of the sequence, the Greedy Algorithm could be de ned and studied, and the students were able to use them to analyze a project, which would be used as a nal instrument of evaluation. This didactical sequence aims to stimulate the student's logical reasoning, as well as to introduce these concepts in their school curriculum on secondary level.