Compressão e Codificação de Dados - LEIC

 

T - Teórica; TP - Teórico-prática; PL - Prática Laboratorial; S - Seminário; OT - Orientação Tutorial.

• Objetivos da aprendizagem

  Os estudantes que terminam com sucesso esta unidade curricular serão capazes de:

  (1) Aplicar os conceitos da teoria da informação na resolução de problemas;

  (2) Descrever as técnicas de compressão estatísticas e baseadas em dicionário;

  (3) Escolher e avaliar a aplicação de técnicas de codificação sem perda, para problemas de compressão;

  (4) Compor e desenvolver técnicas de codificação sem perda, de acordo com o domínio da sua aplicação;

  (5) Compor e desenvolver técnicas de codificação com perda usando a codificação sem perda.

• Programa

  I. Teoria da Informação de Shannon. Entropia de fontes com e sem memória. Codificação de fonte. Teorema da codificação de fonte.

  II. Codificação estatística. Código de Huffman e de Shannon Fano e codificação aritmética.

  III. Codificação de fontes com memória. Compressão universal de fonte. Algoritmos LZ77, LZ78 e suas variantes. Codificação PPM. Codificação baseada em transformada.

  IV. Normas, incluindo GZIP, ZIP, Compress e BZIP.

  V. Compactação de imagem (formatos gif, jbig, jbig2 e png).

  VI. Quantização vectorial.

  VII. Integração da codificação sem perda, no contexto da codificação com perda.

• Demonstração de coerência entre conteúdos programáticos e resultados da aprendizagem

  Esta unidade curricular visa dotar os estudantes da capacidade de utilizar a teoria da informação para resolver problemas. Perante um problema de codificação, o estudante deve saber escolher, adaptar e interligar técnicas de codificação. Visa também a compreensão das técnicas de compressão sem perda e do domínio da sua aplicação e a integração destas com as técnicas utilizadas na codificação com perda. Os tópicos principais incluem a teoria da informação, os algoritmos para compressão com e sem perda, as tecnologias actuais de compressão e as normas mais utilizadas.

• Metodologia de ensino e avaliação

  Ensino teórico-prático, estando previstas 30 aulas a que correspondem 67,5 horas de contacto (15 aulas de 3 horas e 15 de 1,5 horas). O tempo total de trabalho do estudante é de 160 horas. As aulas interactivas destinam-se à apresentação dos temas e de exemplos práticos de aplicação (aprendizagem baseada em casos). Os tópicos principais são ainda explorados através da realização de trabalhos práticos e de projectos baseados em computador (aprendizagem baseada na resolução de problemas). A realização dos trabalhos é acompanhada pelo docente para assegurar o correcto desenvolvimento dos conhecimentos e das competências dos estudantes.

  Os resultados da aprendizagem (1)(3) são avaliados individualmente através de teste escrito. Os resultados da aprendizagem (1)(5) são avaliados na discussão oral individual dos trabalhos práticos.

• Demonstração de coerência entre metodologias de ensino e resultados de aprendizagem

  A capacidade para aplicar conceitos da teoria da informação é desenvolvida em aulas interactivas e respectivos elementos de apoio, e através da realização de exercícios. Estas metodologias são também usadas para desenvolver a compreensão das técnicas de compressão e dos domínios da sua aplicação.

  As competências para compor, desenvolver e comparar técnicas de codificação, com e sem perda, obtêm-se com o estudo de casos, com demonstrações e com a realização supervisionada de trabalhos práticos e projectos e a sua avaliação crítica.

• Bibliografia principal

  Khalid Sayood, Introduction to Data Compression, fourth edition, Morgan Kaufmann Publishers, 2012, ISBN 9780124157965.

  D. Salomon, G. Motta, and D. Bryant, Handbook of Data Compression, Springer; 5th edition, 2009, ISBN 978-1848829022.

  D. MacKay, Information Theory, Inference and Learning Algorithms, Cambridge, 2003 (sixth printing 2007), ISBN 978-0521642989

  Thomas Cover and Joy Thomas, Elements of Information Theory, Wiley-Blackwell; 2nd edition, 2006, ISBN 978-0471241959.