Informações da Disciplina

 Preparar para impressão 
Júpiter - Sistema de Graduação

Instituto de Ciências Matemáticas e de Computação
 
Sistemas de Computação
 
Disciplina: SSC0602 - Introdução à Ciência de Computação II
Introduction to Computer Science II

Créditos Aula: 4
Créditos Trabalho: 2
Carga Horária Total: 120 h
Tipo: Semestral
Ativação: 01/01/2015 Desativação:

Objetivos
Apresentação de conceitos avançados que levem o aluno a uma maturidade em programação estruturada, com conhecimento de uma linguagem de programação com recursos avançados. Aprendizado de técnicas para construção de algoritmos e para análise da complexidade de algoritmos. Aprendizado de algoritmos clássicos de ordenação e busca em memória interna. Prática de Programação.
 
Presentation of advanced concepts that take the student to a maturity level of structured programming, with knowledge of a programming language with advanced features. Learning techniques for constructing algorithms and for analysis of the algorithms' complexity. Learning classical sorting and internal memory searching algorithms. Practice of Programming.
 
 
Programa Resumido
Análise de algoritmos: conceitos básicos, critérios de complexidade de tempo e espaço.notação assintótica, análise de pior caso, melhor caso e caso médio, técnicas de contagem de operações e análise de recorrências. prática e discussão com problemas computacionais relevantes. Algoritrnos de ordenação interna simples e avançados: conceitos básicos, métodos de ordenação bubblesort. quicksort, inserção, shellsort, seleção, heapsort, mergesort. contagem de menores, contagem de tipos e radixsort, análise dos algoritmos de ordenação, prática e discussão com problemas computacionais relevantes. Algoritmos de busca interna: conceitos básicos,métodos de busca seqüencial, seqüencial indexada, binária e por interpolação, análise dos algoritmos de busca anteriores e considerações sobre busca em árvores, prática e discussão com problemas computacionais relevantes. Hashing interno: conceitos básicos. tipos de.hashing, funções hash, tratamento de colisões, análise dos algoritmos de busca. inserção e remoção com base em hashing. Paradigmas de projeto de algoritmos: conceitos básicos, paradigmas de indução, recursividade. tentativa e erro, divisão e conquista, programação dinâmica, algoritmos gulosos e algoritmos aproximados, prática e discussão com problemas computacionais relevantes.
 
Analysis of algorithms: basic concepts, complexity criteria of time and space, asymptotic notation, analysis on the worst case, best case and average case, techniques for counting operations and recurrences analysis, practice and discussion with relevant computational problems. Simple and advanced sorting algorithms in internal memory: basic concepts, bubble sort, quick sort, insertion sort, shell sort, selection sort, heap sort, merge sort, minor counting, type counting and radix sort, analysis of sorting algorithms, practice and discussion with relevant computational problems. Internal searching algorithms: basic concepts, methods for sequential search, indexed and sequential search, binary and interpolation search, analysis of previous search algorithms and considerations on search trees, practice and discussion with relevant computational problems. Internal Hashing: basic concepts, types of hash, hash functions, collision handling, analysis of search algorithms, insertion and removal based on hashing. Algorithm design paradigms: basic concepts, paradigms of induction, recursion, trial and error, divide and conquer, dynamic programming, greedy algorithms, and approximation algorithms, practice and discussion with relevant computational problems.
 
 
Programa
Introdução de conceitos avançados em linguagem de programação estruturada. Análise de algoritmos: critérios de complexidade. Notação Assintótica. Análise do pior caso, melhor caso e caso médio. Paradigmas de Projeto de algoritmos (indução, recursividade, divisão e conquista, etc.). AIgoritmos de ordenação (por inserção, seleção, partição) diretos e avançados, e de busca (direta, seqüencial, indexada) em memória interna. Espalhamento (hashing).
 
Introduction to advanced concepts in structured programming language. Analysis of algorithms: complexity criteria. Asymptotic notation. Analysis on the worst case, best case and average case. Paradigms of algorithms design (induction, recursion, divide and conquer, etc.). Direct and advanced sorting algorithms (insertion sort, selection sort, partition sort). Searching algorithms in internal memory (direct, sequential, indexed). Scattering (hashing).
 
 
Avaliação
     
Método
Aulas expositivas e de resolução de exercícios.
Critério
Desenvolvimento de exercícios e trabalhos práticos dentro e fora de classe. A nota final será calculada pela média ponderada das notas obtidas pelo aluno nos trabalhos e provas.
Norma de Recuperação
-Critério de Aprovação: NP+(Mrec/2,5), se Mrec ou =7,5; ou Max {NP,Mrec}, se Mrec ou = 5,0; ou 5,0, se 5,0 ou = Mrec 7,5.( NP=1ª avaliação, Mrec=prova)
 
Bibliografia
     
Livro Texto:
CORMEN, T.H. et al.: AIgoritmos: Teoria e Prática. Elsevier e Campus (tradução). ISBN 853520926-3.
CORMEN, T.H.; LEISERSON, C.E.; RIVEST, R.L.; STEIN, C. Algoritmos: Teoria e Prática. Editora Campus.2002.
WIRTH,N. Algorithrns + Data Structures = Programs, Prentice-Hall, 1986.
KELLEY, A.; POHL, L - A Book on C, 2a. edição, The BenjanminJCummings Pub. Co., lnc. 1990.
ZIVIANI, N. Projeto de Algoritmos, 2a. edição, Thornson, 2004 .
Bibliografia Complementar:
GRIES,D. The Science of Programming. Berlin. Springer, 1981.
KERNIGHAM,B.: RLTCHlE,D. The C Programming Language, Prentice-Hall, 1988.
SZWARCFTTER, J. L.; MARKENZON, L. Estruturas de Dados e seus Algoritmos, Livros Técnicos e Científicos, 1994.
HOROWLTZ E.. SAHNI, S. - Fundamentos de Estrutura de Dados. Rio de Janeiro, Editora Campus, 1986.
 

Clique para consultar os requisitos para SSC0602

Clique para consultar o oferecimento para SSC0602

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