Métodos de Programação III Matemática e Ciências da Computação Engenharia de Sistemas e Informática 2005/2006
Equipa Docente e Horário Estrutura e Funcionamento Objectivos Avaliação Programa Fichas Teórico-Práticas Software Contribuições dos Alunos Exames Trabalhos Práticos Sumários Bibliografia	Esta página contém informação relativa à cadeira de Métodos de Programação III a decorrer no ano lectivo 2005-2006 . Métodos de Programação III é uma cadeira do 1º Semestre do 3º Ano das licenciaturas em Engenharia de Sistemas e Informática e em Matemática e Ciências da Computação. Referências para páginas de instâncias anteriores podem ser encontradas nos seguintes endereços: Ano Lectivo 2004-2005: Página Ano Lectivo 2003-2004: Página Ano Lectivo 2002-2003: Página Ano Lectivo 2000-2001: Página Ano Lectivo 1999-2000: Página Esta página está a ser gerada a partir de um documento XML, por uma ferramenta que utiliza os métodos de programação leccionados neste curso (eg, expressões regulares, autómatos finitos e gramáticas independentes do contexto). A partir da especificação XML é produzida esta página, bem como a sua representação em LaTeX. O formato LaTeX dá origem aos seguintes documentos em postscript e pdf: [ ps ] , [ pdf ] Novidades e Avisos (03-02-06) As notas da época de recurso estão disponíveis em notas recurso . (03-02-06) As notas da 1ª e 2ª chamadas estão disponíveis em 1ª e 2ª Chamadas . Na 2ª feira (dia 6) de tarde os alunos poderão ver os testes. (02-02-06) Devido a um pequeno atraso na correcção da 2ª chamada, as notas da 1ª e 2ª chamadas serão aqui disponibilizadas amanhã de manhã (6a feira). (30-01-06) As notas práticas finais estão disponíveis em Notas Práticas Finais Os grupos que ainda aparecem com a nota de 18 valores suspensa ( * ) deverão enviar o trabalho devidamente documentado ao docente João Saraiva até 5a feira. Caso contrário, ficarão com essa nota. As notas da 1ª e 2ª Chamadas serão aqui disponibilizadas 5a feira. (05-01-06) As notas do segundo trabalho prático estão disponíveis em notas_tp2.html Os grupos que pretenderem fazer melhoria da nota deste trabalho deverão fazê-lo até à data da 2ª Chamada (24 de Janeiro). Terão para tal de combinar a apresentação com o Tiago Alves. (04-01-06) Um texto sobre cálculo parcial aplicado a gramáticas independentes do contexto LL(1) está disponível em calculoParcial_LL.pdf (03-01-06) Os exames do ano anterior estão disponíveis na página de MPIII desse ano lectivo (ver link acima). Um texto sobre cálculo parcial aplicado a autómatos finitos está disponível em calculoParcial_FA.pdf Amanhã será disponibilizado um texto sobre cálculo parcial e gramática LL(1) (matéria teórica da última semana) (19-12-05) Os segundo trabalho prático deverá ser submetido até às 24:00 no sistema de submissão de trabalhos. A página para submissão dos trabalhos está disponível aqui Submissão dos Trabalhos Online (16-12-05) Uma nova versão dos combinadores de Pretty Printing de tabelas está já disponível. Incluí o pretty printing em HTML. Substituam a directoria Tables em UMinho_Haskell_Libs/PrettyPrint pela nova versão disponível Tables.tgz Os critérios de avaliação do trabalho prático estão disponíveis em Criterios e na Entrega do Trabalho prático: A entrega será feita no sistema de submissão online até às 24:00 de segunda-feira, dia 19 . Este sistema estará disponível na segunda-feira. As apresentações serão feitas nos dois dias seguintes, isto é terça e quata-feira. As marcações estarão disponíveis sexta-feira dia 16, a partir das 12:00 na recepção do DI. (07-12-05) O módulo DfaUtils.hs da biblioteca HaleX tem um erro: o tipo das funções isint e isident é [ Char ] - > Bool (e não Char - > Bool). Por favor, corrijam ou substituam o ficheiro por este DfaUtils.hs (05-12-05) A Ficha-Teórico-Prática nº12 já está disponível As notas do 1º Trabalho Prático já estão disponíveis (ver secção Trabalhos Práticos) (29-11-05) Uma vez que os exercícios de autómatos com reacções de IO e estado não foram resolvidos nas aulas TPs, e para ajudar na resolução do trabalho, a solução da ficha prática nº8 é disponibilizada aos alunos (ver secção Fichas Teórico Práticas). No trabalho prático inclui-se vários ficheiro para os alunos completarem, nomeadamante o próprio enunciado, o ficheiro readme e ainda a Makefile. A ideia é criarem, re-utilizando as bibliotecas HaLeX, HaGLR e de Pretty Printing, uma ferramenta hall (com funcionamento similar ao halex). A directoria HaLL poderá ser usada, por exemplo, para aí produzir o seu binário. (28-11-05) O Trabalho Prático nº2 já está disponível (25-11-05) A Ficha-Teórico-Prática nº11 já está disponível (21-11-05) Entrega do 1º Trabalho Prático: A entrega será realizada na 4ª e 5ª feira, dias 23 e 24 de Novembro. A folha para marcação da apresentação está disponível hoje e amanhã na recepção do DI , tal como definido na aula teróric de hoje. Os alunos deverão trazer o relatório em papel e a versão electrónica do trabalho que submeteram Todos os elementos do grupo têm de estar presentes na apresentação (18-11-05) A Ficha-Teórico-Prática nº10 já está disponível O ficheiros fonte (i.e., LaTeX) das fichas nº 7 e 9 estão agora também disponíveis (11-11-05) A página para a submissão do 1º Trabalho Prático está disponível em entrega trabalho prático A Ficha-Teórico-Prática nº9 já está disponível (04-11-05) A Ficha-Teórico-Prática nº8 já está disponível (28-10-05) A Ficha-Teórico-Prática nº7 já está disponível Existe um bug na versão do sistema HaLeX disponibilizada: a função de visualização de autómato finitos não deterministas estava desactualizada. A versão correcta está agora disponível em HaLeX_1.1.tgz (ou na página do sistema). Congelamento de notas práticas ver secção sobre trabalhos práticos (21-10-05) A Ficha-Teórico-Prática nº6 já está disponível (18-10-05) A Ficha-Teórico-Prática nº5 já está disponível Esta ficha será apresentada/resolvida na aula teórica de 5a. feira (20-11-05) O período de apoio laboratorial aos alunos é às 4a. feiras, lab 1.09, das 14:00 às 16:00 (14-10-05) A Ficha-Teórico-Prática nº4 já está disponível (11-10-05) O Trabalho Prático nº1 já está disponível O Trabalho Prático será apresentado/discutido na aula teórica de 5a feira, 13-11-05 Uma nova versão do sistema HaLeX (usada/referida) no trabalho será disponibilizada esta 5a. feira. Não usar a versão disponibilizada actualmente (07-10-05) A Ficha-Teórico-Prática nº3 já está disponível (30-09-05) A Ficha-Teórico-Prática nº2 já está disponível (23-09-05) A Ficha-Teórico-Prática nº1 já está disponível A página da disciplina está no "ar". 1- Equipa Docente e Horário João Saraiva Teóricas: LESI/MCC T1 2ª Feira - 11:00-12:00 sala CP2-102 T2 5ª Feira - 10:00-11:00 sala CP2-104 Teórica-Prática: MCC TP1 4ª Feira - 11:00-13:00 sala DI 0.02 MCC TP2 5ª Feira - 11:00-13:00 sala DI 0.02 Dúvidas LESI/MCC 2ª Feira - 14:00-18:00 Pedro Rangel Henriques Teórica-Prática: LESI TP1 2ª Feira - 14:00-16:00 sala DI-0.02 Teórica-Prática: LESI TP2 2ª Feira - 16:00-18:00 sala DI-0.02 Dúvidas LESI/MCC 2ª Feira - 11:00-13:00 Tiago Alves Teórica-Prática: LESI TP1 3ª Feira - 9:00-11:00 sala DI-A1 Apoio Laboratorial LESI/LMCC 4ª Feira - 14:00-16:00 Sala de atendimento do DI 2- Estrutura e Funcionamento Exposição da matéria fundamental -- motivação, conceitos, definições, métodos e justificações -- a nível das aulas teóricas. Resolução de exercícios de consolidação, a nível das aulas teórico-práticas, no quadro e no computador. Realização, no computador, extra aulas de trabalhos concretos de aplicação, recorrendo à linguagem Haskell. 3- Objectivos É objectivo deste curso levar os alunos a: Aprofundar e interiorizar os conceitos fundamentais e os métodos de programação em larga escala e a reutilização de programas, dando especial relevo ao paradigma funcional. Aprender o conceito de Autómato Finito e a teoria associada, bem como a sua aplicação à simulação de Sistemas de Controlo e à especificação e reconhecimento de Linguagens Regulares. Compreender os conceitos de cálculo parcial ou especialização de programas Aprender o conceito de gramática e como descrever estruturas de linguagens através de gramáticas. Compreender o conceito: embeber linguagens de dominio especifico (eg, gramáticas) numa linguagem de dominio geral (eg, Haskell). Reforçar a aptidão dos alunos para desenvolver programas correctos e eficientes (quer no paradigma funcional quer em qualquer outro paradigma de programação). 4- Avaliação A Avaliação tem uma componente teórica e uma componente prática, ambas obrigatórias. De acordo com o regulamento actualmente em vigor na UM, a nota teórica (NT) será obtida através da realização de 1 prova individual escrita . Essa prova tem as instâncias a seguir indicadas (um aluno só poderá fazer melhoria na época de recurso): Exame, realizado na 1ª chamada da época normal, no fim do 1º semestre Exame, realizado na 2ª chamada da época normal, no fim do 1º semestre Exame, realizado na época de recurso A componente prática será formada por 2 componentes 2 trabalhos práticos ( P1 e P2 ) a realizar durante o semestre Uma prova individual escrita ( PE ) sobre os trabalhos práticos com 15 minutos de duração. Esta prova escrita será realizada imediatamente antes (ou depois) da avaliaçao teórica da disciplina. A nota prática ( NP ) será obtida de acordo com a seguinte fórmula: NP = P1 * 0.4 + P2 * 0.4 + PE * 0.2 A nota final será determinada de acordo com a seguinte fórmula: NF = ( NT + NP )/2 Exige-se 8 valores como nota mínima em cada uma das partes. 5- Programa Linguagens Resulares Noções básicas Expressões Regulares Expressões Regulares como uma Linguaguem de Domínio Específico Expressões Regulares Embebidas em Haskell Autómatos Finitos Autómatos finitos deterministas (AFD) Autómatos finitos não-deterministas (AFND) Cálculo Parcial aplicado a Autómatos Deterministas Conversão de ANFDs em AFDs Conversão de AFND am AFD através de cálculo parcial Minimização de Estados de AFD Autómatos reactivos Aplicação dos autómatos à simulação de Sistemas de Controlo Aplicação dos autómatos ao reconhecimento de Linguagens Regulares Autómatos Reactivos como AFDs Monádicos em Haskell Linguagens Não Regulares Conceitos e exemplos Estrutura concreta e abstracta das linguagens formais Gramáticas Independentes do Contexto Introdução ao Conceito de Parsing Gramáticas LL(1) e Parsers Top-Down Funções First , Follow e LookAhead Modelação de Gramáticas Independente de Contexto em Haskell Modelação de Parsers Top-Down em Haskell Cálculo Parcial aplicado a Parsers Top-Down Combinadores de Parsing 6- Fichas Teórico-Práticas As fichas a realizar em cada aula teórico-prática são disponibilizadas nesta secção. As fichas estarão disponíveis na sexta-feira da semana anterior à aula a que se destinam. Ficha Teórico-Prática nº 1: Expressões Regulares literate haskell ficha1.lhs. e pdf ficha1.pdf. Ficha Teórico-Prática nº 2: Autómatos Finitos Deterministas literate haskell ficha2.lhs. e pdf ficha2.pdf. Ficha Teórico-Prática nº 3: Autómatos Finitos Não Deterministas literate haskell ficha3.lhs. e pdf ficha3.pdf. (esta ficha usa uma figura que está disponível em ndfa.ps ) Ficha Teórico-Prática nº 4: Conversão de Autómatos Finitos Não Deterministas em Deterministas literate haskell ficha4.lhs. e pdf ficha4.pdf. Ficha Teórico-Prática nº 5: Conversaõ de Expressões Regulares em Autómatos Finitos Não Deterministas literate haskell ficha5.tgz. e pdf ficha5.pdf. (esta ficha usa várias figuras, daí o ficheiro tgz). Ficha Teórico-Prática nº 6: Cálculo Parcial de Autómatos Finitos literate haskell ficha6.lhs. e pdf ficha6.pdf. Ficha Teórico-Prática nº 7: Autómatos Finito Deterministas Reactivos pdf ficha7.pdf. e tgz ficha7.tgz. (esta ficha não usa Haskell) Ficha Teórico-Prática nº 8: Autómatos Finito Deterministas Reactivos em Haskell literate haskell ficha8.tgz. e pdf ficha8.pdf. (esta ficha usa várias figuras, daí o ficheiro tgz). Possível Solução: Ficha8.lhs. e pdf Ficha8.pdf. Ficha Teórico-Prática nº 9: Gramáticas Independentes do Contexto pdf ficha9.pdf. e Latex ficha9.tex. (esta ficha não usa Haskell) Ficha Teórico-Prática nº 10: Gramáticas Independentes do Contexto em Haskell literate haskell ficha10.lhs. e pdf ficha10.pdf. Ficha Teórico-Prática nº 11: Propriedades de Gramáticas Independentes do Contexto em Haskell literate haskell ficha11.lhs. e pdf ficha11.pdf. Ficha Teórico-Prática nº 12: Função de Aceitação LL(1) em Haskell literate haskell ficha12.lhs. e pdf ficha12.pdf. 7- Software O seguinte software utilizado/recomendado nesta disciplina está já disponível: Sistema HaLeX: O sistema HaLeX está disponível na página oficial do sistema HaLeX.html e em HaLeX_1.1.tgz . 8- Contribuições dos Alunos Resolução dos trabalhos práticos propostos nesta disciplina por alguns grupos de trabalho: Grupo constituído por: Bruno Matos (33147), Bruno Dias (35286) e Pedro Rodrigues (35362). Resolução: solução do 1º trabalho prático Grupo constituído por: Henrique Coelho (40622) e Miguel Lopes (42153). Resoluções: solução do 1º trabalho prático e solução do 2º trabalho prático Grupo constituído por: Eduardo Brito (42148), Samuel Alpoim (40663) e Tiago Fernandes (42149). Resolução: solução do 1º trabalho prático Grupo constituído por: Elísio Simão (41032), Filipa Neves (34172) e José Carmo (28154). Resolução: solução do 1º trabalho prático Grupo constituído por: David Vieira (40628), João Rui Cunha (24709) e Pedro Marques (40645). Resoluções: soluções do 1º e 2º trabalho prático Grupo constituído por: Carlos Vilhena (35812), Bruno Sousa (35806) e Rui Samuel Valinho (36867). Resoluç ôes: solução do 1º trabalho prático e solução do 2º trabalho prático Grupo constituído por: Mário Duarte (41833), João Silva (35322) e Duarte Rocha (40667). Resoluções: solução do 1º trabalho prático e solução do 2º trabalho prático Grupo constituído por: Moisés Soares (40614), Rui Silva (41670) e Rita Bezerra (28123). Resolução: solução do 2º trabalho prático Grupo constituído por: Jácome Cunha (35825). Resoluções: solução do 1º trabalho prático e solução do 2º trabalho prático Grupo constituído por: Marco Campos (40656), Marcio Moreira(40655) e Nuno Pojo (40625). Resolução: solução do 2º trabalho prático 9- Exames 1ª Chamada, 9 de Janeiro: Enunciado 2ª Chamada, 24 de Janeiro: Enunciado Prova individual escrita sobre os trabalhos práticos Enunciado 1 Enunciado 2 10- Trabalhos Práticos Algumas resoluções destes trabalhos estão disponíveis na secção Contribuições dos Alunos Os alunos que fizeram a parte prática da disciplina no ano lectivo 2004-2005 poderão congelar a nota que obtiveram e estão dispensados de realizar os trabalhos práticos neste ano lectivo. Para tal deverão contactar o responsável da disciplina antes do dia 11 de Novembro (data de entrega do 1º trabalho). Só serão congeladas as notas dos alunos que constam da seguinte lista: Notas Congeladas. Trabalho Prático nº 1: Simplificação de Expressões Regulares no Sistema HaLeX texto fonte tp1.tgz. e pdf tp1.pdf. Notas: Notas do Trabalho. Trabalho Prático nº 2: HaLL: Um Gerador de Parsers LL(1) texto fonte tp2.tgz. e pdf tp2.pdf. 11- Sumários Aulas Teóricas e Teórico-Práticas de LMCC Engenharia de Sistemas e Informática Matemática e Ciências da Computação Teórico-Práticas TP1 e TP2 de LESI TP1 e TP2 de LESI Bibliografia John Hopcroft, Rajeev Motwani and Jeffrey Ullman Introduction to Automata Theory, Languages and Computation Addison-Wesley 2nd Edition Edicao [HTML] 2001 João Saraiva Language Processing (with a Functional Flavour) DI/UM 1ª Edicao 2000 L.S. Barbosa Elementos da Teoria dos Autómatos DI/UM [PS] 1996 João Saraiva Especificação e Processamento de Linguagens DI/UM 1ª Edicao [PS] [HTML] 1995 R. Floid and R. Beigel The Language of Machines: An Introduction to Computability and Formal Languages Computer Science Press 1994 S.P.Jones, et al Report on the Programming Language Haskell 98 [HTML] [PS] [PDF] 1999 R. Bird Introduction to Functional Programming using Haskell Prentice Hall 1998 S. Thompson Haskell - The Craft of Functional Programming Addison-Wesley 2ª Edicao 1999 N. Jones, C. Gomard and P. Sestoff Partial Evaluation and Automatic Program Generation Prentice Hall [HTML] 1993 E. Horowitz and S. Sahni Fundamentos de Estruturas de Dados Editora Campus 1984 J. Carroll and D. Long Theory of Finite Automata Prentice Hall 1989
Pagina mantida por: João Saraiva jas@di.uminho.pt	Page produced by a Tool generated by LRC from the XML document pagina_mpiii.xml Last Change on Tue Mar 7 13:38:40 2006