AEDII-aula01

Prévia do material em texto

1
Aula 01 – Apresentação
MC3305
Algoritmos e Estruturas de Dados II
Prof. Jesús P. Mena-Chalco
jesus.mena@ufabc.edu.br
2Q-2014
2
Apresentação
Professor:
Jesús P. Mena-Chalco (CMCC)
Formação: 
- Engenheiro da Computação.
- Mestre e Doutor em Ciência da Computação.
Instituto de Matemática e Estatística da USP.
Sala 517-A, torre 2, 5º Andar.
Áreas de pesquisa:
- Reconhecimento de padrões, Bibliometria, e Cientometria.
3
Apresentação
Árvore de genealogia:
81.768 vértices (matemáticos)
88.955 arestas (relacionamentos)
Johann Bernoulli (1667-
1748)
4
Apresentação
Fuga/Migração de pessoas 
Aplicação de estruturas de dados 
eficientes para a análise de dados.
5
Sobre a disciplina
6
Requisito: Algoritmo e Estrutura de Dados I
Ementa:
Breve introdução à linguagem C (ou C++).
Noções básicas de análise de complexidade de tempo de 
algoritmos. 
Representação, organização e gerenciamento de dados em 
memória primária: listas, filas, pilhas, árvores.
Algoritmos de busca: busca sequencial, busca binária.
Algoritmos de ordenação: inserção, seleção, bolha, 
mergesort, heapsort, quicksort.
Árvores de busca, árvores balanceadas de busca.
7
Algoritmo e Estrutura de Dados II
Representação, organização e gerenciamento de dados em 
memória primária: técnicas de pesquisa; noções de 
complexidade: hashing; union-find; árvores AVL, árvores 
rubro-negras.
Representação, organização e gerenciamento de dados em 
memória secundária: técnicas de pesquisa; noções de 
complexidade: árvores B;
Algoritmos de ordenação mergesort e keysort; arquivos 
indexados.
Algoritmos de codificação e decodificação de dados; 
Compressão de dados; noções de complexidade: algoritmo 
de Huffman.
8
Bibliografia
CORMEN, T. H.; LEISERSON, C. E.; RIVEST, R. L. e STEIN, C. 
Introduction to Algorithms, 3a edição, MIT Press, 2009.
FOLK, M.; ZOELLICK, B.; RICCARDI, G. File Structures, An 
Object-Oriented Approach Using C++, 3a edição, Addison-
Wesley, 1998.
ZIVIANI, N. Projeto de Algoritmos: com implementações em 
Pascal e C, 2a edição, Cengage Learning, 2009
FOLK, M.; ZOELLICK B. File Structures, 2a edição, Addison-
Wesley, 1992.
SEDGEWICK, R. Algorithms in C, Parts 1-4: Fundamentals, Data 
Structures, Sorting, Searching, 3a edição. Addison-Wesley, 1997.
SZWARCFITER, J. L.; MARKEZON, L. Estruturas de Dados e 
seus Algoritmos, 2a edição, LTC, 1994.
9
Algoritmo e Estrutura de Dados II
TIDIA-AE: MC3305-AED2-noturno
TPI: 2 - 2 - 4 
É muito importante considerar as ~4 horas de estudo fora da 
aula. 
→ Fall in love with mathematics (pratique matemática)
→ Be self-motivated (trabalhe com pares)
→ Never back down (seja persistente)
→ Become a master (ensine aos colegas)
→ Be a bookworm (seja leitor ávido)
Leia as seguintes sugestões:
http://www.wikihow.com/Learn-a-Programming-Language
10
Alguns livros importantes para a carreira
11
Sobre a linguagem de programação
Atualmente existem várias linguagens que são consideradas 
para este tipo de disciplinas...
(Python, C, C++, Java, Haskell, Ruby)
Também vários paradigmas de programação (e.g. procedural, 
orientado a objetos,) podem ser consideradas...
Todo programador competente deve saber/entender a 
linguagem C/C++.
Tradicionalmente é utilizada a linguagem C/C++.
Nessa disciplina usaremos C/C++.
12
Sobre o IDE (Integrated development environment)
Ambiente de desenvolvimento integrado:
●Kdevelp
●Code Blocks
●Netbeens C++
●Eclipse CDT
●Dev C++
●C-Free 
●Vi
●Emacs
http://designzum.com/2014/02/26/best-compilers-and-ides-for-cc-programmers/
13
Sobre os exercícios
Para a avalição de exercícios-problema usaremos a 
plataforma UVa Online Judge
(University of Valladolid,Spain)
É um repositório de mais de 3500 problemas de 
computação.
O aluno pode enviar soluções (em código fonte) para a 
plataforma e este determinará se a solução é correta 
ou não.
Semanalmente serão solicitados, de 2 a 4, exercícios desse 
repositório de problemas, para que o aluno pratique e 
obrigatoriamente submeta à plataforma.
Os problemas estarão ligados aos tópicos estudados em aulas.
14
Sobre os exercícios
Para comprovar a solução de cada exercício-problema, o 
aluno deverá submeter à areao do Tidia:
O código fonte enviado ao UVa, e
O email de confirmação da solução.
Veja a seguir um exemplo:
O código fonte servirá para detectar plágio entre diferentes soluções.
15
Sobre os exercícios
Faça seu registro na seguinte página:
http://uva.onlinejudge.org/
Utilize seu nome real (como registrado na Prograd)
Veja uma introdução à plataforma em:
http://www.mathblog.dk/uva-online-judge/
Quais problemas desenvolver?
http://uhunt.onlinejudge.org/
16
Sobre os exercícios
17
Sobre a avaliação
18
Sobre a avaliação
Prova 01: 24 de julho → 30%
Prova 02: 28 de agosto → 30%
Exercícios-problema → 25%
Monografia + apresentação de tópicos especiais →15%
Atribuição de conceitos:
A: nota ≥ 8,5
B: 7 ≤ nota < 8,5
C: 5,5 ≤ nota < 7
D: 5,0 ≤ nota < 5,5
F: nota < 5,0
Substitutiva (apenas de prova): 11 de setembro
19
Material e atividades
Os slides das aulas, enunciados de atividades, e outras 
comunicações da disciplina serão publicadas no Tidia-ae.
[MC3305-AED2-noturno]
Página web com outras informações:
http://professor.ufabc.edu.br/~jesus.mena/courses/mc3305-2q-2014/
Email: jesus.mena@ufabc.edu.br
Dúvidas no último dia de entrega (<=24hrs) sobre as 
atividades/exercícios não serão respondidas.
20
Primeiro problema
21
Primeiro problema (11567)
Para S=7 teremos como resposta 5.
22
Primeiro problema (uma possível solução)
23
Primeiro problema (uma possível solução)
← scanf: “scan formatted” 
24
scanf
25
scanf
26
Primeiro problema (uma possível solução)
27
Primeiro problema
Compilando o programa:
28
Primeiro problema
Compilando o programa:
Testando o programa:
Teste em batch:
29
Exercícios-Problema (EPs) para esta semana
11567 - Moliu Number Generator (ok) 
10055 - Hashmat the Brave Warrior
458 - The Decoder
100 - The 3n + 1 problem
10327 - Flip Sort 
Data: 30/Junho (segunda-feira) até às 23h50.
Arquivos: 
Para cada exercício-problema deverá submeter:
O código fonte: nome do arquivo → RA_nroDoProblema.cpp
O comprovante de aceitação (Uva) → RA_nroDoProblema.pdf
Exemplo: 10123456_11567.cpp
 10123456_11567.pdf
30
Páginas importantes
Quick access, info and search:
http://acm.uva.es/local/online_judge/search_uva.html
Faça seu registro na seguinte página:
http://uva.onlinejudge.org/
Utilize seu nome real (como registrado na Prograd)
Veja uma introdução à plataforma em:
http://www.mathblog.dk/uva-online-judge/
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27
	Slide 28
	Slide 29
	Slide 30