INF01203 - Estruturas de Dados - Instituto de Informática (UFRGS) - Prof. Dennis Giovani Balreira

Aula 0 - Informações Gerais

Sejam bem-vindos à disciplina de Estruturas de Dados. Nesta página encontram-se as principais informações administrativas da disciplina, incluindo sua ementa, bibliografia, organização das aulas e formas de contato. Recomenda-se consultar este material sempre que surgir alguma dúvida ao longo do semestre.

Sobre a disciplina

Estruturas de Dados é uma das disciplinas fundamentais da formação em Ciência da Computação. Seu objetivo é apresentar técnicas para representação, organização e manipulação eficiente de dados, permitindo o desenvolvimento de algoritmos escaláveis e de alto desempenho.

Ao longo do semestre estudaremos tanto estruturas armazenadas na memória principal quanto estruturas utilizadas para organização de dados em memória secundária (disco), sempre utilizando a linguagem C como linguagem de implementação.

Espera-se que o aluno já possua conhecimentos básicos de programação em C, incluindo funções, vetores, matrizes, registros (structs), ponteiros e alocação dinâmica de memória, adquiridos na disciplina de Algoritmos e Programação.

Ementa da disciplina

A disciplina aborda os principais conceitos relacionados à representação e manipulação eficiente de dados na memória principal e em memória secundária.

Os principais tópicos estudados são:

Fundamentos de Estruturas de Dados.
Algoritmos de ordenação (Insertion Sort, Shell Sort, Merge Sort e Quick Sort).
Tipos Abstratos de Dados.
Listas lineares utilizando vetores.
Listas simplesmente, duplamente e circularmente encadeadas.
Pilhas, filas e deques.
Heaps e filas de prioridade.
Árvores binárias, árvores binárias de busca e árvores balanceadas.
Estruturas para processamento de strings (Trie, Patricia e Ternary Search Tree).
Técnicas de ordenação de strings e arquivos invertidos.
Tabelas Hash e tratamento de colisões.
Árvores B e B+ para indexação em memória secundária.
Técnicas clássicas de compressão de dados (Run-Length Encoding, Huffman e LZW).

Ao final da disciplina espera-se que o aluno seja capaz de selecionar, implementar e analisar diferentes estruturas de dados, escolhendo a solução mais adequada para cada problema computacional.

Professor

Prof. Dr. Dennis Giovani Balreira

E-mail:
dgbalreira at inf.ufrgs.br

Página pessoal:
www.inf.ufrgs.br/~dgbalreira

Áreas de pesquisa

Processamento de Linguagem Natural.
Extração de Informação.
Aprendizado de Máquina.

Material da disciplina

Todo o material utilizado durante o semestre será disponibilizado por meio dos seguintes canais:

Moodle da UFRGS, utilizado para avisos, entrega de atividades e divulgação de notas.
Página da disciplina, contendo as aulas, materiais complementares e demais informações:

www.inf.ufrgs.br/~dgbalreira/ed

As páginas da disciplina funcionarão como um livro-texto eletrônico, contendo explicações detalhadas dos conteúdos apresentados em aula, exemplos em linguagem C, exercícios e materiais de apoio.

Recomenda-se acompanhar regularmente tanto o Moodle quanto a página da disciplina.

Bibliografia

Os seguintes livros serão utilizados como principais referências ao longo do semestre.

Bibliografia Básica Essencial

Thomas H. Cormen et al.
Algoritmos: Teoria e Prática.
Campus, 2002.
ISBN 8535209263.

Nina Edelweiss e Renata de Matos Galante.
Estruturas de Dados.
Bookman, 2009.
ISBN 9788577803811.

Bibliografia Básica

Nivio Ziviani.
Projeto de Algoritmos com Implementações em Pascal e C.
Bookman, 2011.
ISBN 9788522110506.

Robert Sedgewick e Kevin Wayne.
Algorithms (4th Edition).
Addison-Wesley Professional, 2011.
ISBN 032157351X.

Embora as aulas forneçam uma visão completa dos conteúdos da disciplina, recomenda-se fortemente a consulta à bibliografia para aprofundamento dos conceitos e realização dos exercícios.

Organização das aulas

A disciplina será dividida em dois tipos de encontros: aulas teóricas e aulas práticas.

Aulas teóricas

Apresentação e discussão dos conceitos fundamentais.
Resolução de exemplos em sala de aula.
Exercícios conceituais realizados pelos alunos.
Discussão de aplicações práticas das estruturas estudadas.

Aulas práticas

Implementação das estruturas em linguagem C.
Resolução de exercícios nos laboratórios.
Correção de dúvidas de implementação.
Desenvolvimento gradual das habilidades de programação exigidas pela disciplina.

A participação ativa durante as aulas é fortemente incentivada. Estruturas de Dados é uma disciplina essencialmente prática, e a implementação das estruturas é parte fundamental do processo de aprendizagem.

Critérios de avaliação

A avaliação da disciplina será composta por atividades teóricas e práticas realizadas ao longo do semestre. O objetivo é avaliar tanto a compreensão dos conceitos quanto a capacidade de implementar corretamente as estruturas de dados estudadas.

Serão atribuídas quatro notas principais:

Atividade	Peso	Descrição
P1	35%	Primeira prova teórico-prática, abrangendo os conteúdos da primeira parte da disciplina.
P2	40%	Segunda prova teórico-prática, abrangendo os conteúdos da segunda parte da disciplina.
TF	15%	Trabalho final envolvendo implementação e apresentação de um projeto utilizando estruturas de dados estudadas na disciplina.
E	10%	Exercícios realizados em aula e extraclasse.

A Média Final (MF) será calculada da seguinte forma:

MF = 0,35 × P1 + 0,40 × P2 + 0,15 × TF + 0,10 × E

A conversão da média em conceito seguirá as normas da UFRGS:

Conceito	Critério
A	MF ≥ 9,0
B	7,5 ≤ MF < 9,0
C	6,0 ≤ MF < 7,5
D	MF < 6,0
FF	Frequência inferior a 75%, independentemente da nota.

As atividades extraclasse, incluindo listas de exercícios e o trabalho final, fazem parte da carga horária da disciplina e são fundamentais para consolidar os conceitos apresentados em aula.

Recuperação

Caso o aluno não obtenha Média Final igual ou superior a 6,0, será oferecida uma prova de recuperação abrangendo todo o conteúdo da disciplina.

A nota final será recalculada utilizando a seguinte expressão:

(MF × 0,40 + Recuperação × 0,60) ≥ 6,0

Se essa condição for satisfeita, o aluno será aprovado com conceito C, conforme previsto nas normas da disciplina. Caso contrário, o aluno é reprovado com conceito D.

Frequência

A presença nas aulas é obrigatória, conforme o Regimento da UFRGS.

É necessária frequência mínima de 75% para aprovação.

Isso significa que o número máximo de faltas permitido é de 8 aulas.

Mesmo que todas as avaliações tenham sido aprovadas, frequência inferior ao mínimo exigido resulta em conceito FF.

Conduta em sala de aula

Um ambiente de aprendizagem depende da colaboração de todos. Espera-se que cada estudante contribua para manter uma sala de aula organizada e respeitosa.

Em particular:

Respeite os colegas que estão acompanhando a aula.
Evite conversas paralelas durante as explicações.
Mantenha o celular no modo silencioso.
Participe das discussões e faça perguntas sempre que necessário.
Durante as aulas práticas, procure resolver os exercícios antes de solicitar ajuda.
Respeite colegas, monitores e professor.

Dúvidas são sempre bem-vindas. Perguntar faz parte do processo de aprendizagem e normalmente ajuda diversos colegas que possuem a mesma dificuldade.

Como aproveitar melhor a disciplina

Estruturas de Dados costuma ser considerada uma das disciplinas mais importantes do curso porque fornece ferramentas utilizadas em praticamente todas as demais áreas da Computação.

Algumas recomendações podem tornar o aprendizado muito mais eficiente:

Não deixe acumular conteúdo entre as aulas.
Implemente todos os algoritmos apresentados em sala.
Teste seus programas utilizando diferentes casos de entrada.
Desenhe listas e árvores no papel antes de programá-las.
Não memorize algoritmos; procure compreender por que eles funcionam.
Compare diferentes soluções para um mesmo problema.
Leia o material da disciplina antes e depois das aulas.

O objetivo da disciplina não é apenas aprender estruturas clássicas, mas desenvolver a capacidade de analisar problemas e escolher a representação mais adequada para cada situação.

Perguntas frequentes

É necessário utilizar linguagem C?

Sim. Todas as implementações da disciplina serão realizadas em linguagem C, permitindo compreender detalhadamente como as estruturas de dados são representadas na memória.

Preciso decorar os algoritmos?

Não. É muito mais importante compreender o funcionamento, as vantagens, limitações e aplicações de cada estrutura do que memorizar código.

Vale a pena implementar novamente os exemplos vistos em aula?

Sim. A implementação é uma parte essencial do aprendizado. Muitas dificuldades aparecem apenas durante a programação e ajudam a consolidar os conceitos discutidos nas aulas teóricas.

Posso utilizar bibliotecas prontas?

Durante a disciplina o foco será compreender como as estruturas funcionam internamente. Por esse motivo, a maior parte dos exercícios exigirá implementações próprias, sem utilizar bibliotecas que já resolvam o problema.

Mensagem final

Vocês ingressaram em uma das principais universidades do país e têm a oportunidade de cursar uma disciplina fundamental para a formação em Ciência da Computação.

Aproveitem essa oportunidade. Participem das aulas, implementem os exercícios, discutam soluções com os colegas e procurem compreender os conceitos em profundidade. O conhecimento adquirido nesta disciplina será utilizado diversas vezes ao longo do curso e da carreira profissional.

Sejam todos bem-vindos e tenham um excelente semestre!