Material - Turma X

O plano de curso das disciplinas podem ser visualizados nos seguintes links:

• • DCC199 - Algoritmos 

  • DC5199 - Algoritmos - Prática

Segue abaixo o material didático relativo a cada conteúdo da disciplina:

• • Aula 00 - Apresentação da disciplina; Primeiros passos do processo de desenvolvimento de algoritmos (slides e link para a ferramenta ELoS, que será utilizada na aula prática).

  • Aula 01 - Algoritmos; Introdução à programação  (slides e capítulo 1 do livro).

  • Aula 02 - Variáveis, tipos de dados, comandos de I/O, atribuição, teste de mesa (slides, capítulo 2 do livro e videoaula).

  • Aula 03 - Funções (slides, capítulo 3 do livro e videoaula).

  • Aula 04 - Estruturas de controle condicionais (slides, capítulo 4 do livro e videoaula).

  • Aula 05 - Estruturas de controle com repetições (capítulo 5 do livro / Parte I: slides e videoaula / ParteII: slides e videoaula).

  • Aula 06 - Vetores Numéricos (slides, capítulo 6 do livro e videoaula).

  • Aula 07 - Strings (slides, capítulo 7 do livro e videoaula).

  • Aula 08 - Matrizes (slides, capítulo 8 do livro e videoaula).

  • Aula 09 - Estruturas de dados heterogêneas (slides, capítulo 9 do livro e videoaula).

Videoaulas de exercícios elaboradas pelo professor Ronney Castro.

Listas de exercícios:

• • Lista de exercícios para a primeira prova

  • Lista de exercícios para a segunda prova

  • Lista de exercícios para a terceira prova

  • Lista de exercícios para a quarta prova

Revisões para as avaliações:

• TVC 1: enunciado, gabarito e videoaula com a solução

• TVC 2: enunciado, gabarito e videoaula com a solução

• TVC 3: enunciado, gabarito e videoaula com a solução

• TVC 4: enunciado, gabarito e videoaula com a solução

Para alunos curiosos (e alunos da computação):

• • Tutorial sobre Debug no CodeBlocks (elaborado pelo Prof João Paulo Scoralick)

  • Comentários sobre leiaute (Prof Paulo Feofiloff - USP)

  • Números randômicos (Prof Paulo Feofiloff - USP)

  • Tutorial sobre OnlineGDB

  • Instalação do MinGW no Windows

  • Instalação do VSCode no Windows

  • Configuração do VSCode para compilar programas em C/C++

  • The Missing Semester of Your CS Education (em inglês)

  • Ambiente de Desenvolvimento (elaborado por Gabriel Malosto)

Projeto: Implementação do Algoritmo K-Means em C++

Implemente o algoritmo k-means em C++, utilizando apenas as bibliotecas previamente apresentadas em aula.

O k-means é um algoritmo de aprendizado não supervisionado que separa um conjunto de dados em k grupos. Esse processo é realizado de forma iterativa, seguindo os passos principais:

1. Inicialização dos centros dos grupos (clusters), cujas posições podem ser escolhidas de diversas maneiras, como seleção aleatória de pontos do conjunto de dados ou estratégias mais avançadas.

2. Atribuição de cada ponto de dados ao cluster cujo centro está mais próximo, de acordo com uma métrica de distância (como distância Euclidiana).

3. Atualização das posições dos centros dos clusters, calculando a média dos pontos atribuídos a cada cluster.

4. Repetição dos passos 2 e 3 até que um critério de parada seja atingido, como um número máximo de iterações ou quando os centros dos clusters não mudarem significativamente entre iterações.

O trabalho deve incluir:

• Um código em C++ que lê um conjunto de dados de um arquivo .txt.

• A implementação do agrupamento dos dados em k grupos, onde k e o número máximo de iterações são parâmetros informados pelo usuário (utilize 100 iterações como padrão).

• Uma avaliação prática do modelo utilizando o conjunto de dados da íris (disponível em: https://archive.ics.uci.edu/dataset/53/iris). Para isso, deve-se executar o algoritmo para:

  • Todos os pares de variáveis possíveis entre as 4 disponíveis no conjunto de dados (ou seja, 6 combinações);

  • Todas as 4 variáveis simultaneamente.

Critérios de Avaliação

1. Leitura do arquivo: O código deve ser capaz de abrir e processar corretamente o arquivo .txt contendo os dados.

2. Organização e otimização do código: A implementação deve seguir boas práticas de programação, como modularidade, clareza e eficiência.

3. Comentários no código: Adicione comentários explicativos detalhando o funcionamento de cada parte do algoritmo.

4. Escolha de hiperparâmetros e métrica de distância: A escolha da métrica de distância e os critérios para a inicialização dos clusters devem ser documentados e justificados.

5. Análise dos resultados: O trabalho deve incluir uma análise dos agrupamentos gerados no conjunto de dados da íris. Compare os agrupamentos com as classes reais (embora o k-means seja não supervisionado) e discuta os resultados, indicando possíveis limitações do modelo.

Entrega:
Submeta o código em um arquivo compactado, incluindo:

• O código-fonte em C++.

• O arquivo .txt usado para testes (caso seja diferente do conjunto de dados da íris).

• Um relatório em PDF com as justificativas para as escolhas realizadas, os resultados obtidos (incluindo gráficos, se possível), e uma discussão crítica sobre o desempenho do algoritmo.

Código inicial: https://onlinegdb.com/mb8YNmzA4