Combinatória e Teoria de Códigos (Coding Theory and Combinatorics) (Semestre 2 - 2020-2021)

 
Licenciatura em Matemática Aplicada e Computação e Mestrado em Matemática Aplicada



Docente: Pedro Martins Rodrigues - pmartins@math.tecnico.ulisboa.pt



Information and News        Program     Bibliography       Notes and Problems

Evaluation       Grades



Information and News

13/07 A pauta foi actualizada após a realização de provas de segunda época. Como sabem, o exame de época especial, marcado para dia 23/07, pode ser feito por todos os alunos inscritos. Solicito por isso que me indiquem até dia 19/07 se pretendem usar essa possibilidade.

05/07 A Pauta foi actualizada após revisão dos Testes e alteração da nota de avaliação contínua. Esta última alteração seguiu o critério de valorizar o pior TPC em 2.4 valores e cada um dos outros em 4.4 valores.

Pede-se aos alunos que ainda não o fizeram que me confirmem se pretendem realizar exame ou recuperar algum dos testes na segunda época.

02/07 Foram publicadas as classificações do Teste 2 e uma pauta com os resultados finais, até este momento. Na próxima segunda-feira, 05/07, às 17:00 horas, haverá uma sessão Zoom, com o mesmo Meeting ID das últimas (ver nos anúncios do Fenix) para esclarecimentos sobre o Teste e eventual pedidos de revisão de prova.

Agradeço que me enviem até lá, uma mensagem a indicar se pretendem na segunda época fazer exame ou recuperar um dos testes (e qual), indicando também a data preferida.

28/06 Foi publicada uma pauta com os resultados dos TPC.

22/06 - Teste: Pede-se a cada um dos alunos que confirme, por mensagem, até às 12:00 horas de amanhã, se prefere realizar o Teste amanhã, 23/06, ou na quinta-feira. Em qualquer caso, o Teste será enviado, por mensagem para o endereço utilizado para aquela confirmação, cerca das 15:00 horas.

20/06 - Foi publicada a pauta com os resultados do Teste 1.

17/06 - Caso pretendam esclarecer dúvidas nas aulas de revisões, seria útil enviá-las por mensagem antes.

15/06 - As aulas de revisões decorrerão em sistema misto (presencial/remoto): 17/06 - 16:00 - sala P1, e 18/06 - 11:00, sala P12.

14/06 - As aulas de revisões anunciadas terão lugar, em princípio, nos dias 17/06, às 16:00, e 18/06, às 11:00. Estes horários podem ser ajustados caso seja necessário, pelo que peço que me avisem até amanhã caso haja incompatibilidades. Estas aulas decorrerão online e as sessões Zoom serão anubnciadas, como de costume, no Fenix. Na aula de sexta-feira acertamos a data do segundo teste, pelo que é particularmente imposrtante a presença de todos. Espero publicar mais informação sobre a avaliação brevemente.

02/06 - Antes do mais, as minhas desculpas por avisar do cancelamento da aula de ontem em cima da hora. Preciso também de cancelar a aula da próxima sexta-feira. Proponho a realização de duas aulas de duas horas cada, nos dias 16/06 e 18/06, entre as 11:00 e as 13:00. Estes dias e horas podem ser alterados em função de incompatibilidades de horário. Estas aulas serão dedicadas a revisões. As minhas desculpas por estas alterações e por todas as perturbações do normal funcionamento das aulas.

01/06 - Foi publicada uma versão provisória das Notas sobre códigos de convolução. Devido a um problema inesperado, terei que me ausentar por umas horas e não poderei dar a aula de hoje. As minhas desculpas. Iremos marcar aulas de substituição para a semana de 14/06 a 18/06, que serão dedicadas a revisões. Darei mais notícias nos próximos dias.

24/05 - A sala para a aula de terça-feira foi alterada, passando a ser a V0.09.

21/05 - As Notas X foram actualizadas de novo, ainda sem exemplos. Conforme referido na aula de hoje, a partir da próxima segunda-feira as aulas serão, em princípio, leccionadas na sala atribuída no Fenix para o efeito. Evidentemente, podem continuar a assistir remotamente.

16/05 - Foi publicada uma nova versão das Notas X. O exercício 27 deve ser entregue como trabalho de casa até sexta-feira, dia 21/05.

14/05 - Bom dia. Devido a um problema de saúde inesperado, é possível que me atrase hoje para a aula. As minhas desculpas.

11/05 - Foi publicada uma primeira versão das Notas X. Devido aos esmos motivos pessoais, precisava de cancelar o horário de dúvidas de hoje. Se for necessário, podemos marcar um horário alternativo para outro dia. A aula de hoje será dedicada a exemplos de concatenação de códigos.

10/05 - O horário de dúvidas de hoje tem que ser cancelado, por motivos pessoais. As minhas desculpas pelo inconveniente. Até amanhã.

07/05 - Teste: Conforme combinado, o Teste vai decorrer esta tarde. O enunciado estará disponível através da plataforma Fenix, na secção Teste 1, ou directamente do link Teste 1 , a partir das 15.30. As respostas devem ser enviadas até às 22.30 de hoje. Caso haja alguma dificuldade ou dúvida sobre o enunciado, podem comunicar comigo por mensagem.

03/05 - Foi publicada uma primeira versão das Notas IX. A matéria para o Teste é a das Notas I a VI.

28/04 - O TPC tinha uma gralha e foi corrigido.

28/04 - Trabalho de casa: O seguinte trabalho de casa deve ser entregue até às 12.00 da próxima segunda-feira: Notas VII, demonstração da Proposição 71 e problema 78; Notas VIII, problemas 54 e 55.

25/04 - Foi publicada uma primeira versão das notas sobre Códigos Cíclicos.

21/04 - O prazo de entrega do trabalho de casa é alargado até sexta-feira, $agrave; mesma hora, Além disso, a demonstração da Proposição 37 ou 38 é retirada. Serão dadas mais explicações sobre o assunto na próxima aula.

16/04 - Foram publicadas as Notas VII.

14/04 - Trabalho para casa: As Notas VI foram corrigidas em alguns pontos. O seguinte trabalho de casa, baseado nessas notas, deve ser entregue até às 19.00 horas de dia 21/04: Proposição 33 ou 34; Proposição 37 ou 38; problemas 53 e 54.

13/04 - Só agora pude entrar no horário de dúvidas de hoje. As minhas desculpas. Se for necessário, posso marcar um horário alternativo. No seguimento da aula de hoje, venho pedir a todos que confirmem por escrito a sua concordância com a data de 07/05 para o Teste. Vou marcar uma aula de substituição para o dia 23/04, sexta-feira, às 16.00. Os dados de acesso serão, como de costume, publicados em anúncio no Fenix.

11/04 - As Notas VI foram actualizadas.

08/04 - Foi publicada uma primeira versão de Notas sobre Teoria de Informação e Códigos.

07/04 - Foi publicada uma primeira versão de Notas sobre sistemas de incidência (designs) e tópicos relacionados.

29/03 - Foi publicada uma primeira versão das Notas sobre Enumeradores de pesos.

24/03 - Trabalho de casa: confirmo que o TPC consiste nos exercícios 59 e 60 e demonstração da Proposição 66, das Notas II. O prazo de entrega é até às 19.00 horas do dia 26/03, sexta-feira.

24/03 - Foi publicada uma primeira versão das Notas sobre majorantes e minorantes.

21/03 - Novo Horário: Os dados de acesso às sessões Zoom dos novos hoários estão publicados num anúncio na plataforma Fenix.

17/03 - Trabalho de casa: O prazo de entrega do TPC foi prolongado até amanhã à mesma hora. Quem já entregou pode, se o desejar, enviar uma nova versão.

17/03 - Foi publicada uma nova versão das Notas II que inclui secções novas.

13/03 - O horário de dúvidas fica marcado para segunda e terça- feiras, entre as 17:00 e as 18:30. Os dados de acesso às sessões Zoom serão publicados num anúncio na Fenix.

13/03 - Trabalho de casa: Foi publicada a nova versão das Notas I e uma primeira versão de Notas II.

O trabalho de casa consiste nos seguintes problemas: Notas I - 29, 31 (uma alínea), 34 (uma alínea), 35; Notas II - 24, 39, 41. Este TPC deve ser entregue até dia 17/03, às 19:00 horas.

Na próxima aula discutiremos alguns outros problemas destes dois conjuntos de Notas.

12/03 - Ao contrário do que foi prometido na aula, só amanhã poderei publicar a versão actualizada das Notas I, a primeira versáo das Notas II, e a lista de problemas para o trabalho de casa. O prazo deste será ajustado a este atraso. As minhas desculpas.

11/03 - Horário: No seguimento da conversa no fim da aula de hoje, peço a todos que preencham, até à próxima segunda-feira, nesta tabela os vossos horários de aulas, excluindo CTC, de modo a procurarmos uma possível alternativa para a aula de quinta-feira.

08/03 - Foi publicada uma primeira versão das Notas I. Para não atrasar a publicação, não se inclui uma subsecção de problemas sobre àrvores de decisão, que será acrescentada brevemente.

01/03 - A first file of warm-up notes is now available.

25/02 - The Meeting ID and passcodes for the Zoom sessions of classes have been published in an announcement in Fenix.

23/02 - A short presentation. The main theme of this course is the theory of error-correcting codes, giving emphasis to its algebraic and combinatorial aspects, and with an introduction to information theory. Topics include source encoding and entropy, linear Codes, combinatorial and algebraic constructions of codes, code parameters, probability of error and Shannon's theorem, an introduction to finite fields, cyclic codes, convolutional codes, etc. The course covers also a review of enumeration, based on generating functions. The prerequisites are very modest: a basic knowledge of linear algebra and rudiments of probability theory are sufficient.

The notes, homework, exams, etc, as well as oral presentation in class, will be in English. Naturally, questions in class and solutions for homework and exams may be given in English or Portuguese (or French, if necessary). For the moment, classes will be remote. The meeting ID and passcode for the Zoom sessions will be announced in Fenix.

The course is intended to depend strongly on the autonomous work of students, encouraging independent study and exploration of subjects. With this purpose, course notes will be given, whenever feasible, in advance, and as most as possible in the form of problems. Error-correcting codes is, by its own nature, both a theoretical and practical area. In order to perform computations and experiment with concrete codes, students are encouraged to use appropriate software (Mathematica or MatLab, for example). However, this is not a course on computation; its essence is on the understanding, deduction and proof of general properties of codes and of its encoding and decoding capabilities.



Program

Matemática Discreta Enumerativa: Princípio de inclusão-exclusão. Funções geradoras. Relações de recorrência. Teoria de Códigos: O problema principal da Teoria de Códigos. Corpos finitos e espaços vectoriais sobre corpos finitos. Códigos lineares. Códigos cíclicos.




Bibliography

A Course in Error-Correcting Codes, J. Justensen & T. Høholdt, EMS Textbooks in Mathematics, 2017.

Coding Theory, a First Course, San Ling & Chaoping Xing, Cambridge University Press, 2004.

Fundamentals of Error-Correcting Codes, W. Cary Huffman & Vera Pless, Cambridge University Press, 2003.

Coding and Information Theory, Steven Roman, Springer-Verlag, 1992.

Notes and Problems

Warm-up notes 1       NotesI: Introduction. Source Coding

Notes II: Channel Coding. Linear Codes. Operations on codes.

Notes III: Bounds on codes.

Notes IV: Weight Enumerators.

Notes V: Designs and related topics.

Notes VI: Information Theory and Coding. Shannon's theorem.

Notes VII: Finite fields

Notes VIII: Cyclic Codes

Notes IX: Reed-Solomon Codes

Notes X: Algebraic Construction of Codes

Notes XI: Convolutional Codes



Evaluation
The main evaluation consists of two tests (29/04 and 23/06) and an optional exam (09/07), supplemented by homework assignments. Students may attend both the two tests and the exam, and the best grade prevails.

The final grade, in a scale 0-20, will be given by max(max(Tests, Exam), 0.6 max(Tests, Exam)+0.4 Homework).



Grades

TPC

Teste 1

Teste 2

Pauta Final