Mudanças entre as edições de "Scc-205(sandra)"

De CoteiaWiki
(→‎Avisos:)
(→‎Notas)
 
(29 revisões intermediárias por 6 usuários não estão sendo mostradas)
Linha 8: Linha 8:
 
=== <font color = "green"> Avisos: </font> ===
 
=== <font color = "green"> Avisos: </font> ===
  
−
Próximas apresentações de Learning Objects, lembrem que o LO deve ser encaminhado para mim com 1 semana de antecedência.<br/><br/>
+
Notas da REC final da página. Revisão quarta das 14:00 - 18:00 h <br/><br/> <br/><br/>  
−
Leandro e Vinícius escolheram o Problema da Mochila para provar que é NP-C <br/><br/>
 
−
Matheus Nin e Thiago Arashida escolheram o Problema do Azulejamento para provar que é indecidível<br/><br/>
 
−
Patrícia e Taiane escolhem cobertura de vértices para provar que é NP-C <br/><br/>
 
−
Nilton Palmeira Pacífico Junior e Willian Gustavo Pinch escolheram o PCP para provar que é indecidível<br/><br/>
 
−
Vinícius Silva e ? escolheram 3-coloring para provar que é NP-C <br/><br/>  
 
−
Denis e ? escolheram o caminho hamiltoniano <br/><br/>
 
  
−
1) os 2 grupos que apresentarão problemas indecidíveis, escolham um dentre a lista abaixo (SEM REPETIÇÃO).
+
Médias e Frequencias REVISADAS (freq contando as 3 provas) disponíveis. <br/><br/> <br/><br/>  
−
MANDEM um e-mail para assim, tão logo escolherem: <br/><br/>
 
−
PCP (Post Correspondence Problem)<br/><br/>
 
−
Azulejamento <br/><br/>
 
−
Equivalência de programas (ou de 2 MT)<br/><br/>
 
−
Busy Beaver <br/><br/>
 
−
Ambigüidade de GLC <br/><br/>
 
−
Se 2 GLC são equivalentes <br/><br/>
 
−
Propriedade da linguagem da MT ser: Regular, Finita, Livre de Contexto <br/><br/>
 
  
−
2) Os 4 grupos que apresentarão problemas NP-c, escolham um dentre os da lista abaixo (SEM REPETIÇÃO).
+
Notas da P3 disponíveis. REVISÃO segunda 13/12 das 8:30- 18:00 h <br/><br/> <br/><br/>
−
MANDEM um e-mail para assim, tão logo escolherem: <br/><br/>
+
 
−
3SAT, <br/><br/>
+
Notas dos LO disponíveis. <br/><br/> <br/><br/>
−
NAESAT (not-all-equal SAT), <br/><br/>
+
 
−
Cobertura de vértices, <br/><br/>
+
Notas da P2 disponíveis. Revisão na quinta das 8:30- 18:00 h.
−
CAMINHO HAMILTONIANO (ou CICLO HAMILTONIANO), <br/><br/>
+
−
podem também escolher CAIXEIRO VIAJANTE pela importante prática deste e de  
+
Lista 4 disponível: teoria da computabilidade e teoria da complexidade. LO´s disponíveis para a PROVA 3. <br/><br/>
−
como vem sendo resolvido com heurísticas (embora seja um exemplo de CAM-CICLO HAM –  
+
Próximas apresentações de Learning Objects, lembrem que o LO deve ser encaminhado para mim com 1 semana de antecedência.<br/><br/>
−
as vezes a prova usa problemas diferentes para a redução), <br/><br/>
+
Leandro e Vinícius escolheram o Problema da Mochila para provar que é NP-C <br/><br/>
−
mochila (knapsack), <br/><br/>
+
Matheus Nin e Thiago Arashida escolheram o Problema do Azulejamento para provar que é indecidível<br/><br/>
−
soma de subconjuntos, <br/><br/>
+
Patrícia e Taiane escolhem cobertura de vértices para provar que é NP-C <br/><br/>
−
3-coloring (pode um mapa ser colorido com 3 cores?), <br/><br/>
+
Nilton Palmeira Pacífico Junior e Willian Gustavo Pinch escolheram o PCP para provar que é indecidível<br/><br/>
−
Partição em grafos (cut). <br/><br/>
+
Vinícius Silva e Alex escolheram 3-coloring para provar que é NP-C <br/><br/>
 +
Denis e Allan escolheram o caminho hamiltoniano para provar que é NP-C<br/><br/>
 +
 
 +
1) os 2 grupos que apresentarão problemas indecidíveis, escolham um dentre a lista abaixo (SEM REPETIÇÃO).
 +
MANDEM um e-mail para assim, tão logo escolherem: <br/><br/>
 +
PCP (Post Correspondence Problem), Azulejamento , Equivalência de programas (ou de 2 MT)<br/><br/>
 +
Busy Beaver, Ambigüidade de GLC, Se 2 GLC são equivalentes <br/><br/>
 +
Propriedade da linguagem da MT ser: Regular, Finita, Livre de Contexto <br/><br/>
 +
 
 +
2) Os 4 grupos que apresentarão problemas NP-c, escolham um dentre os da lista abaixo (SEM REPETIÇÃO).
 +
MANDEM um e-mail para assim, tão logo escolherem: <br/><br/>
 +
3SAT, NAESAT (not-all-equal SAT), Cobertura de vértices, <br/><br/>
 +
CAMINHO HAMILTONIANO (ou CICLO HAMILTONIANO), <br/><br/>
 +
podem também escolher CAIXEIRO VIAJANTE pela importante prática deste e de  
 +
como vem sendo resolvido com heurísticas (embora seja um exemplo de CAM-CICLO HAM –  
 +
as vezes a prova usa problemas diferentes para a redução), <br/><br/>
 +
mochila (knapsack), soma de subconjuntos, 3-coloring (pode um mapa ser colorido com 3 cores?), <br/><br/>
 +
Partição em grafos (cut). <br/><br/>
  
  
  
−
Não haverá aula nesta sexta, 15/10, pois estarei em reunião na reitoria da USP.  
+
Não haverá aula nesta sexta, 15/10, pois estarei em reunião na reitoria da USP.  
 
  Lista 3 disponível (ACP, ALL e MT).<br/><br/><br/><br/>
 
  Lista 3 disponível (ACP, ALL e MT).<br/><br/><br/><br/>
  
Linha 106: Linha 109:
  
 
  Aula 17: (19/11) Problemas Indecidíveis e Parcialmente Indecidíveis - Métodos de Prova: [[Arquivo:ind_dec_2010_.pdf]]
 
  Aula 17: (19/11) Problemas Indecidíveis e Parcialmente Indecidíveis - Métodos de Prova: [[Arquivo:ind_dec_2010_.pdf]]
 +
Slides Extra sobre Teoria da Complexidade: Análise Assintótica [[Arquivo:comp_ass.pdf]] e Análise de Algoritmos [[Arquivo:analise_alg.pdf]]
 
  Aula 18: (23/11) Problemas NP-C - Métodos de Prova: [[Arquivo:complex_tempo_2010.pdf]]
 
  Aula 18: (23/11) Problemas NP-C - Métodos de Prova: [[Arquivo:complex_tempo_2010.pdf]]
 
  Material de Suporte: Aulas do Prof. David Evans da University of Virginia (http://www.cs.virginia.edu/evans)
 
  Material de Suporte: Aulas do Prof. David Evans da University of Virginia (http://www.cs.virginia.edu/evans)
Linha 176: Linha 180:
 
26/10: Máquina de Turing Determinística
 
26/10: Máquina de Turing Determinística
 
http://contentbuilder.merlot.org/toolkit/users/cchagas/mtd
 
http://contentbuilder.merlot.org/toolkit/users/cchagas/mtd
 +
 +
Prova 3:
 +
 +
26/11: Análise de Algoritmos e o comportamento Assintótico de Funções
 +
http://contentbuilder.merlot.org/toolkit/html/stitch.php?s=27229034274098
 +
 +
26/11: Maquina de Turing Universal
 +
http://contentbuilder.merlot.org/toolkit/html/stitch.php?s=57031840045966
 +
 +
26/11: PCP
 +
http://contentbuilder.merlot.org/toolkit/users/npjunior/pcp
 +
 +
26/11: Tiling
 +
http://contentbuilder.merlot.org/toolkit/users/arashidanin/tilingproblem
 +
 +
30/11: 30/11
 +
Caminho Hamiltoniano
 +
http://contentbuilder.merlot.org/toolkit/html/stitch.php?s=9549717744393
 +
 +
30/11: Mochila
 +
http://contentbuilder.merlot.org/toolkit/users/vgobbo/knapsack
 +
 +
30/11: 3-Coloring
 +
http://contentbuilder.merlot.org/toolkit/users/alexvinicius/icmc3coloring
 +
 +
30/11: Cobertura de Vértices
 +
http://contentbuilder.merlot.org/toolkit/html/stitch.php?s=34941899063943
  
 
=== <font color = "green"> Listas de Exercícios </font> ===
 
=== <font color = "green"> Listas de Exercícios </font> ===
Linha 186: Linha 217:
  
 
LISTA 3: [[Arquivo:Lista3_205.pdf]]
 
LISTA 3: [[Arquivo:Lista3_205.pdf]]
 +
 +
LISTA 4: [[Arquivo:Lista4_205.pdf]]
  
−
=== <font color = "green"> Notas </font> ===
+
=== <font color = "green"> Regras para a REC: </font> ===
 +
 
 +
Data da Prova Rec: 31/1/2011
 +
 
 +
Horário: 14:00 - 16:00
  
−
Notas da P1: [[Arquivo:P1_SCC_205_2010.pdf]]
+
Local: sala 4003
  
−
=== <font color = "green"> Regras para a REC: </font> ===
+
Notas da PROVA REC: <br/><br/> <br/><br/>  
  
−
Data da Prova Rec: ~15/12/10
+
Eduardo Alberice -- 8.0 <br/><br/>
 +
Thiago Barreto -- 1.8 <br/><br/> 
 +
Vitor Rossi -- 3.0 <br/><br/>
 +
Willian Pinch -- 8.0 <br/><br/>
 +
Alex Fragoso -- 5.7 <br/><br/> 
 +
Rodrigo Koga -- 4.3 <br/><br/> 
 +
Gabriel Lima -- 3.8  <br/><br/> 
 +
Bruno Ribeiro -- 4.6 <br/><br/> 
 +
Daniela Canuta -- 5.3
  
−
Horário:
 
  
−
Local:
 
  
 
Nota Final (regra USP)   
 
Nota Final (regra USP)   

Edição atual tal como às 18h55min de 20 de setembro de 2024

No Jupiter-web: [ementa]

SCC-205 - Teoria da Comp. e Linguagens Formais (BCC-B)

  • Local: Sala (5004) - Horário: Ter. 08:10/09:50 e Sex. 10:10/11:50
    • Atendimento da Profa. Sandra Aluisio: via e-mail: sandra [arroba] icmc.usp.br; presencial: Sala: 4-208 nas quintas das 14:00 - 17:00
    • Monitora: Carolina Scarton; carol.scarton [arroba] gmail.com; quartas das 16:00-18:00 no NILC.

Avisos: 

Notas da REC final da página. Revisão quarta das 14:00 - 18:00 h 

 

 

Médias e Frequencias REVISADAS (freq contando as 3 provas) disponíveis. 

 

 

Notas da P3 disponíveis. REVISÃO segunda 13/12 das 8:30- 18:00 h 

 

 

Notas dos LO disponíveis. 

 

 

Notas da P2 disponíveis. Revisão na quinta das 8:30- 18:00 h.

Lista 4 disponível: teoria da computabilidade e teoria da complexidade. LO´s disponíveis para a PROVA 3. 


Próximas apresentações de Learning Objects, lembrem que o LO deve ser encaminhado para mim com 1 semana de antecedência.


Leandro e Vinícius escolheram o Problema da Mochila para provar que é NP-C 

 
Matheus Nin e Thiago Arashida escolheram o Problema do Azulejamento para provar que é indecidível

 
Patrícia e Taiane escolhem cobertura de vértices para provar que é NP-C 

 
Nilton Palmeira Pacífico Junior e Willian Gustavo Pinch escolheram o PCP para provar que é indecidível


Vinícius Silva e Alex escolheram 3-coloring para provar que é NP-C 

 
Denis e Allan escolheram o caminho hamiltoniano para provar que é NP-C



1) os 2 grupos que apresentarão problemas indecidíveis, escolham um dentre a lista abaixo (SEM REPETIÇÃO).
MANDEM um e-mail para assim, tão logo escolherem: 


PCP (Post Correspondence Problem), Azulejamento , Equivalência de programas (ou de 2 MT)


Busy Beaver, Ambigüidade de GLC, Se 2 GLC são equivalentes 


Propriedade da linguagem da MT ser: Regular, Finita, Livre de Contexto 



2) Os 4 grupos que apresentarão problemas NP-c, escolham um dentre os da lista abaixo (SEM REPETIÇÃO).
MANDEM um e-mail para assim, tão logo escolherem: 


3SAT, NAESAT (not-all-equal SAT), Cobertura de vértices, 


CAMINHO HAMILTONIANO (ou CICLO HAMILTONIANO), 


podem também escolher CAIXEIRO VIAJANTE pela importante prática deste e de 
como vem sendo resolvido com heurísticas (embora seja um exemplo de CAM-CICLO HAM – 
as vezes a prova usa problemas diferentes para a redução), 


mochila (knapsack), soma de subconjuntos, 3-coloring (pode um mapa ser colorido com 3 cores?), 


Partição em grafos (cut). 





Não haverá aula nesta sexta, 15/10, pois estarei em reunião na reitoria da USP. 
Lista 3 disponível (ACP, ALL e MT).





MUDANÇAS: (1) a PROVA 2 será no dia 9/11, devido a feriados em São Carlos.
(2) Teremos aula no dia 23/11 ENTÃO o Tema 24 (Máquina de Turing Universal) vai ser apresentado dia 26/11 e 
o Tema 29 (Análise de Algoritmos e o comportamento Assintótico de Funções) no dia 30/11. 



Links das apresentações já realizadas já estão disponíveis no link "Links no MERLOT". 


Enviem o link do MERLOT para a profa (sandra@icmc.usp.br) 1 semana antes da apresentação. 


Lista 1 e 2 disponíveis no Link LISTAS. 


Data de Início das aulas: 03/agosto.

Aula a aula (slides): 

Aula 1 (3/8): Arquivo:SCC 205 Apres Curso 2010.pdf

Aula 1 (3/8) Teoria das LF e Automatos: Arquivo:Aula1 Visão Geral LFA 2010.pdf

Aula 2, Aula 3 (6 e 10/8): Arquivo:Gramatica0 2010.pdf

Aula 3 (10/8): Arquivo:Apresentação do MERLOT Content Builder.pdf

Aula 4 (13/8): Arquivo:Gramatica1 2010.pdf

Aula 5 (17/8): Arquivo:Gramatica2 2010.pdf

Aula 5 (17/8): Arquivo:Exer resolvidos G 2010.pdf

Aula 6 (20/8): Arquivo:Aut 1 2010.pdf

Aula 6 (20/8): Arquivo:Aut 2 2010.pdf

Aula 7 (24/8): Arquivo:Aut 3 2010.pdf

Aula 8 (27/8): Arquivo:Aut 4 2010.pdf

Aula 8 (27/8): Arquivo:Exer resolvidos A 2010.pdf

Aula 8 (27/8): Arquivo:LB 2010.pdf

Aula 9 (31/8): Arquivo:ER1 2010.pdf

Aula 9 (31/8): Arquivo:ER2 2010.pdf

Aula 10 (03/9): Arquivo:Minimização AF 2010.pdf

Aula 11 (28/9): Arquivo:ACP parte1 2010.pdf

Aula 12 (01/10): Arquivo:ACP parte2 2010.pdf

Aula 13 (05/10): Arquivo:Gramatica 3.pdf
Aula 13 (05/10): Arquivo:Gramatica 4.pdf
Aula 13 (05/10): Arquivo:Exer resolvidos GLC.pdf

Aula 14 (08/10): Arquivo:MT1 2010.pdf

Aula 15 (19/10): Arquivo:MT2 2010.pdf
Aula 15 (19/10): Arquivo:MT3 2010.pdf

Aula 16 (16/11) Overview da Teoria da Complexidade: Arquivo:Aula1 T Complex.pdf
Aula 16 (16/11) Overview da Teoria da Computabilidade: Arquivo:Aula1 T Comp.pdf

Aula 17: (19/11) Problemas Indecidíveis e Parcialmente Indecidíveis - Métodos de Prova: Arquivo:Ind dec 2010 .pdf
Slides Extra sobre Teoria da Complexidade: Análise Assintótica Arquivo:Comp ass.pdf e Análise de Algoritmos Arquivo:Analise alg.pdf 
Aula 18: (23/11) Problemas NP-C - Métodos de Prova: Arquivo:Complex tempo 2010.pdf
Material de Suporte: Aulas do Prof. David Evans da University of Virginia (http://www.cs.virginia.edu/evans)

Avaliação:

3 Provas com pesos 40%, 30% e 30%.

  • Datas: PROVA 1 (17/9); PROVA 2 (5/11); PROVA 3 (3/12)
  • MUDANÇA: a PROVA 2 será no dia 9/11, devido a feriados em São Carlos.

Trabalhos Práticos: 1 trabalho prático e sua apresentação, feito em grupo de 2 alunos. O trabalho é a criação de um learning object a ser postado no site MERLOT (http://www.merlot.org/) da California State University.

Links e referências

Material de Apoio do Livro Texto de Ramos, Neto & Vega, 2009 (Linguagens Formais: Teoria, Modelagem e implementação): [1]

Links no MERLOT 

 Prova 1:

3/9: Gramáticas: definições e a Hierarquia de Chomsky http://contentbuilder.merlot.org/toolkit/users/formais/formais

3/9: Sistemas de Estados Finitos e AF Determinísticos http://contentbuilder.merlot.org/toolkit/users/MKE/afd

3/9: AF Não-Determinísticos e a Equivalência entre AF Não-Determinísticos e AF Determinísticos http://contentbuilder.merlot.org/toolkit/html/snapshot.php?id=5749174697091

14/9: Operações Fechadas sobre LR http://contentbuilder.merlot.org/toolkit/users/tts/operacoesfechadas

14/9: Autômatos Finitos com Movimentos Vazios & Equivalência entre Gramática Regular e Autômato Finito http://contentbuilder.merlot.org/toolkit/html/snapshot.php?id=9809792106794

14/9: Lema do Bombeamento http://contentbuilder.merlot.org/toolkit/html/stitch.php?s=57516836801094

14/9: Utilitário LEX e ERs estendidas http://contentbuilder.merlot.org/toolkit/users/gilaraujo/lexnxre 

Prova 2:

22/10: Formas Normais & ACP Não Determinísticos http://contentbuilder.merlot.org/toolkit/users/fnormais/tema14

22/10: Automatos com pilha determinístico e não-determinísticos http://contentbuilder.merlot.org/toolkit/html/stitch.php?s=82839271596483

22/10: Árvores de Derivação e Ambigüidade em Linguagens Livre de Contexto http://contentbuilder.merlot.org/toolkit/html/stitch.php?s=33425235872553&id=5300135868881

26/10: Máquinas de Turing com Múltiplas Fitas: http://contentbuilder.merlot.org/toolkit/users/dannycanuta/multitapesturingmachine

26/10: Procedimentos & Algoritmos - Tese de Church-Turing http://contentbuilder.merlot.org/toolkit/html/snapshot.php?id=74454342829487

26/10: Máquinas de Turing com Fita Limitada (Autômatos limitados linearmente) http://contentbuilder.merlot.org/toolkit/html/stitch.php?s=4401969476046&id=99966187868236

26/10: Máquina de Turing Determinística http://contentbuilder.merlot.org/toolkit/users/cchagas/mtd 

Prova 3:

26/11: Análise de Algoritmos e o comportamento Assintótico de Funções http://contentbuilder.merlot.org/toolkit/html/stitch.php?s=27229034274098

26/11: Maquina de Turing Universal http://contentbuilder.merlot.org/toolkit/html/stitch.php?s=57031840045966

26/11: PCP http://contentbuilder.merlot.org/toolkit/users/npjunior/pcp

26/11: Tiling http://contentbuilder.merlot.org/toolkit/users/arashidanin/tilingproblem

30/11: 30/11 Caminho Hamiltoniano http://contentbuilder.merlot.org/toolkit/html/stitch.php?s=9549717744393

30/11: Mochila http://contentbuilder.merlot.org/toolkit/users/vgobbo/knapsack

30/11: 3-Coloring http://contentbuilder.merlot.org/toolkit/users/alexvinicius/icmc3coloring

30/11: Cobertura de Vértices http://contentbuilder.merlot.org/toolkit/html/stitch.php?s=34941899063943

Listas de Exercícios

LISTA 1: Arquivo:Lista 1 205.pdf

LISTA 2: Arquivo:Lista 2 205.pdf

LISTA 3: Arquivo:Lista3 205.pdf

LISTA 4: Arquivo:Lista4 205.pdf

Regras para a REC:

Data da Prova Rec: 31/1/2011

Horário: 14:00 - 16:00

Local: sala 4003

Notas da PROVA REC:



Eduardo Alberice -- 8.0

Thiago Barreto -- 1.8

Vitor Rossi -- 3.0

Willian Pinch -- 8.0

Alex Fragoso -- 5.7

Rodrigo Koga -- 4.3

Gabriel Lima -- 3.8

Bruno Ribeiro -- 4.6

Daniela Canuta -- 5.3


Nota Final (regra USP)

= Nota Anterior + (Nota Rec / 2.5); se Nota Rec >= 7.5 ; ou

= max(Nota Anterior, Nota Rec); se Nota Rec < 5.0 ; ou

= 5.0, se 5 <= Nota Rec < 7.5

Disponível em "http://wiki.icmc.usp.br/index.php?title=Scc-205(sandra)&oldid=50834"