Informações da Disciplina

 Preparar para impressão 

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


Instituto de Ciências Matemáticas e de Computação
 
Ciências de Computação
 
Disciplina: SCC0201 - 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/2024 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.
 
 
Docente(s) Responsável(eis)
6116132 - Moacir Antonelli Ponti
 
Programa Resumido
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.). Algoritmos 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).
 
 
Programa
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. Algoritmos 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 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.

Atividades de extensão: Divulgação de conteúdo sobre algoritmos e sua computabilidade. Por exemplo é quase senso comum que um computador pode resolver tudo imediatamente, o que não é verdade. Algoritmos usados na prática podem ser abordados para o público geral e interessados (ordenação, busca, hashing) e sua complexidade. A carga horária corresponde a 5 horas.
 
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.
 
 
Avaliação
     
Método
Aulas expositivas e de resolução de exercícios.
Critério
A nota final será calculada pela média ponderada das notas de provas e exercícios obtidas pelo aluno no decorrer no semestre.
Norma de Recuperação
Realização: Até a primeira semana de aulas do semestre posterior -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.: Algoritmos: 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.
- KELLEY, A.; POHL, I. A Book on C. 2a. edição, The Benjanmin/Cummings Pub. Co., Inc. 1990.
- SCHILDT, H. "C.Completo e Total". MakronBooks, 1997.
- TENENBAUM, A.M., e outros Data Structures Using C. Prentice-Hall, 1990.
- ZIVIANI, N. Projeto de algoritmos. 2a. edição, Thomson, 2004

· Bibliografia Complementar:

- GRIES, D. The Science of Programming. Berlin, Springer, 1981.
- KERNIGHAM, B.; RITCHIE, D. The C Programming Language. Prentice-Hall, 1988.
- KERNIGHAM, B.W.; RITCHIE, D.M.C. A Linguagem de Programação Padrão ANSI. Editora Campus, 1995.
- HOROWITZ E.; SAHNI, S. Fundamentos de Estrutura de Dados. Rio de Janeiro, Editora Campus, 1986.
- ROBERTS, E. Programming Abstractions in C. Addison Wesley, 1996.
- SEDGEWICK, R. Algorithms in C. Addison-Wesley, 1990.
- SHOOMAN, M.L. Software Engineering. New York, McGraw-Hill, 1983.
- SZWARCFITER, J. L.; MARKENZON, L. Estruturas de Dados e seus Algoritmos. Livros Técnicos e Científicos, 1994.
- WIRTH, N. Algorithms + Data Structures = Programs. Prentice-Hall, 1986.
 

Clique para consultar os requisitos para SCC0201

Clique para consultar o oferecimento para SCC0201

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