Informações da Disciplina

 Preparar para impressão 

Júpiter - Sistema de Gestão Acadêmica da Pró-Reitoria de Graduação


Instituto de Matemática e Estatística
 
Ciência da Computação
 
Disciplina: MAC0121 - Algoritmos e Estruturas de Dados I
Algorithms and Data Structures I

Créditos Aula: 4
Créditos Trabalho: 0
Carga Horária Total: 60 h
Tipo: Semestral
Ativação: 01/01/2016 Desativação:

Objetivos
Introduzir técnicas básicas de programação, estruturas de dados básicas, e noções de projeto e análise de algoritmos, por meio de exemplos.
 
Introduce basic programming techiques, data structures, and notions of design and analysis of algorithms, through examples.
 
 
Docente(s) Responsável(eis)
47490 - Arnaldo Mandel
91288 - Carlos Eduardo Ferreira
55029 - Cristina Gomes Fernandes
26472 - Paulo Feofiloff
88134 - Yoshiharu Kohayakawa
 
Programa Resumido
Noções de correção e desempenho de algoritmos. Noções de tipos abstratos de dados. Vetores e matrizes. Alocação dinâmica de memória. Apontadores. Listas ligadas. Árvores binárias. Pilhas e filas. Noções de filas de prioridade. Recursão. Algoritmos de ordenação. Processamento elementar de texto. Tabelas de símbolos elementares, incluindo árvores binárias de busca. Noções de estratégias algorítmicas.
 
Notions of correctness and performance of algorithms. Notions of abstract data types. Arrays. Dynamic memory allocation. Pointers. Linked lists. Binary trees. Stacks and queues. Notions of priority queues. Recursion. Sorting algorithms. Elementary text pocessing. Elementary symbol tables, including binary search trees. Notions of algorithmic strategies.
 
 
Programa
Noções informais de prova de correção e medida do desempenho de algoritmos. Noções de tipos abstratos de dados. Vetores e matrizes. Strings (cadeias de caracteres). Alocação dinâmica de memória e redimensionamento de vetores. Apontadores. Listas ligadas. Estruturas ligadas não lineares. Árvores binárias. Pilhas e filas (implementadas com vetores e listas ligadas). Aplicações. Filas de prioridade (implementadas com heaps). Aplicações. Recursão. Aplicações. Algoritmos de ordenação elementares. Algoritmo quicksort. Algoritmo mergesort. Algoritmo heapsort. Algoritmo radixsort (ordenação digital). Ordenação indireta (ordenação de apontadores). Processamento elementar de texto. Aplicações. Tabelas de símbolos elementares: implementações baseadas em vetores, listas ligadas, busca binária, e árvores binárias de busca. Aplicações. As aplicações podem envolver várias estruturas de dados compostas (como vetores de listas ligadas) e várias estratégias algorítmicas (gulosa, divisão e conquista, programação dinâmica, backtracking, busca em largura, etc.).
 
Informal notions of proof of correctness and evaluation of performance of algorithms. Notions of abstract data types. Arrays. Strings. Dynamic memory allocation and array resizing. Pointers. Linked lists. Non-linear linked structures. Binary trees. Stacks and queues (implemented with arrays an linked lists). Applications. Priority queues (implemented with heaps). Applications. Recursion. Applications. Elementary sorting algorithms. Quicksort. Mergesort. Heapsort. Radixsort. Indirect sorting (pointer sorting). Elementary text processing. Applications. Elementary symbol tables: implementations based on arrays, linked lists, binary search, and binary search trees. Applications. The applications may involve various composite data structures (such as arrays of linked lists) and various algorithmic strategies (greedy, divide-and-conquer, dynamic programming, backtracking, breadth-first-search, etc.).
 
 
Avaliação
     
Método
Método:Aulas expositivas e tarefas que podem ou não envolver programação.
Critério
Média ponderada de provas e exercícios.
Norma de Recuperação
Norma de Recuperação: Média ponderada da nota final e de provas e/ou trabalhos de recuperação.
 
Bibliografia
     
P. Feofiloff, Algoritmos em Linguagem C, Elsevier, 2009.
E.S. Roberts, Programming Abstractions in C: a Second Course in Computer Science, Addison-Wesley, 1997.
R. Sedgewick, Algorithms in C, 3rd. ed., Parts 1-4, Addison-Wesley, 1998.
R. Sedgewick, K. Wayne, Introduction to Programming in Java, Addison-Wesley, 2008.
R. Sedgewick, K. Wayne, Algorithms, 4th. ed., Addison-Wesley, 2011.
 

Clique para consultar os requisitos para MAC0121

Clique para consultar o oferecimento para MAC0121

Créditos | Fale conosco
© 1999 - 2024 - Superintendência de Tecnologia da Informação/USP