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

 
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

15/07 - The Final Grades were updated after the oral examinations and final exam. This finishes the activities of the course. This webpage will no longer be updated. I wish everyone a nice summer vacation and all the best in your personal and academic lives.

26/06 - I recall that the date of the Exam was reset to 14/07. Students willing to attend the Exam should send me a message stating this.

26/06 - The grades of Test 2 have been published, together with a table of the final grades, as they stand before the final exam, of course. I'll be available for questions about the Test, and others, next Monday, 01/07, from 10.00 to 12.00, in my office in Tecnico, and by e-mail or zoom session, from 14.00 to 16.00. Students with a final grade above 17 are asked to either show up in my office or write me.

23/06 - A solution of Test 2 has been published. Due to a mild health problem, the grades will be published only in a couple of days. My apologies.

11/06 - The Homework grades were published. All Homeworks were graded from 0 to 4. A weighted global grade for the homeworks, which will never be below the arithmetic mean of the partial grades, will be included later.

04/06 - Notes X were updated to include the proofs in the last section.

03/06 - A first version of Notes X has been published. I hope to update it, namely the last section, in the next few days.

25/05 - The slides from the last lectures are available. The corresponding Notes will be published soon.

12/05 - Notes VIII has been published.

10/05 - - Homework assignement: to be delivered until Friday, 15/05, 16.00, consists of: Exercises 54 and 57 from Notes VII.

07/05 - I noticed that part of the final computations in the example of the second part of today's lectures contained mistakes and were unnecessary complicated. I'll include a corrected version as an exercise in a pdated version of the Notes.

05/05 - Notes VII have been updated with some examples.

29/04 - Notes VI were updated. Appart from a new result and some added clarifications, the main modifications are in the order of the sections.

27/04 - Tomorrow, I will not be online at the usual time. I will be available in the afternoon and may also answer questions on Wenesday, if necessary.

27/04 - A file with solutions for the problems in the Test is available, next to the Notes. This file will be updated with solutions to other problems.

27/04 - Notes VII have been published.

24/04 - Homework assignement: to be delivered until Friday, 01/05, 16.00, consists of: proof of Proposition 56 and problems 59, 66, 67, all from Notes VI.

24/04 - The grades of Test 1 are published. I will publish soon the grades of the homework done so far.

21/04 - A new version of > Notes VI has been published.

20/04 - Notes VI are now available. I will, as usual, be available for attending hours, in the usual schedule, either by message, or by zoom, if needed.

02/04 - Exercise 12 of Notes V must be solved for binary codes. The possible generalization of the result to other fields may eventually be discussed later. My apologies.

27/03 - Homework assignement to be delivered until Friday, 03/04, 16.00, consists of the following problems: Notes IV, Problem 41 and Notes V, Exercise 12.

26/03 - A first version of Notes V is available.

25/03 - Remote Classes (update): First, due to a mild health problem (not related with covid) I have to cancel tomorrow's lecture. It will be replaced later, with date and hour to be discussed. However, I'll be available to answer messages or, if necessary, to connect throuhg zoom.

We will have our usual class on Friday, 27/03, at 11.00. This class will be dedicated to the subject of Weight enumerators.

The lectures of next week will be entirely dedicated to revisions and discussion of problems and exercises from the Notes. Some details may be added, but we will not start a new chapter from the course. The exact date for the first Test and scheduling of attending hours during the Easter break will be discussed on Friday.

24/03 - Notes IV was updated. More information will be published tomorrow.

17/03 - A preliminary version of Notes IV is available. It will surely be updated, mainly its second section.

17/03 - If anyone is having difficulties either in accessing the zoom sessions or of any other kind related to the present public health situation, please let me know. A new set of notes will be published this afternoon or tomorrow morning, and discussed in the remote classes of this week. I'll try to make them as useful as possible and appreciate and welcome any helping feedback.

15/03 - Remote Classes (update) Scheduled remote attending hours will be on Mondays and Tuesdays, from 10.00 to 12.00. During these periods, I'll be online in a zoom session. The URL for the session will be sent by e-mail to all students, as happened in the rehearsal from last Thursday. Other attending hours may be scheduled on demand; the URL for the zoom session will also be sent to everyone.

13/03 - Remote classes will star next Thursday, 19/03. The schedule of classes will be Thursday, from 9.00 to 10.30 and Friday, from 11.00 to 12.30. Notes for the lectures will be published in advance, at least in a preliminary form. I'll be online for remote attending hours on Mondays, Tuesdays and Wednesdays, from 10.00 to 12.00. Other hours may be eventually scheduled, on demand. As this is a situation new to all of us, any feedback on the classes and course materials is most welcome and appreciated.

13/03 - Homework assignement to be delivered until Friday, 20/03, 16.00, consists of the following problems: Notes II - problems 37, 41 and 44; Notes III - proof of Proposition 2, Problems 30, 34 and 36. The homework may be delivered by e-mail or left in my locker in the department's locker room.

13/03 - A new version of the file Notes III is now available. It contains two more problems and a more clear presentation of residual codes.

11/03 - Following the decision to start remote classes, tomorrow's lecture will be a first trial of this. The class will take place at 9.30, using the Colibri platform, which uses the software zoom. Information on the use of this is available on Tecnico's webpage. An invitation for the zoom meeting will be sent this afternoon to the students e-mails. In case someone does not receive it, please send me a message. This will be just a first trial and more information will be published soon in this webpage. I will try to compensate for the natural disadvantages of this situation. In particular I'll be avilable to answer any questions by e-mail and to schedule remote zoom meeetings on demand.

10/03 - A first version of the file Notes III is now available.

05/03 - Problem 28 in Notes I has now a hint, as promised. My apologies for the delay.

03/03 - Attending Hours: Starting next week, during the attending hours on Tuesday, I'll be in room P2, in the ground floor.

03/03 - The file Notes II is now available.

27/02 - Attending Hours I'll be available in my office every Tuesday from 10 to 12. Other attending hours may be defined, if needed.

27/02 - The file Notes I is now available. The Homework assignement to be delivered until 06/03, in class, consists of the following problems: Problem 28, Problem 29 b) and c), Problem 32 b) and d), Problem 33. All students are encouraged to try to solve other problems and exercises.

12/02 - Information and materials for the course will be made available in this page. The following announcement was already published in the Fenix webpage:

Classes for the course on Coding Theory and Combinatorics will start next week.

All students planning to attend the course, or that may be interested in doing so, are invited to visit me at my office for a short conversation; these are intended to give me some information about each student mathematical background and previous knowledge of the subject and, of course, to answer any questions that the students may want to ask. I'll be available 12/02, 13/02, 14/02, 17/02 and 18/02, from 10.00 to 12.00, but I would appreciate a message announcing your visit.



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

Notes I

Notes II

Notes III

Notes IV

Notes V

Notes VI

Notes VII

Notes VIII

Slides: Subfield and Trace Codes     Slides: Concatenation of Codes

Notes IX

Notes X

Solutions     Test 2: Solutions



Evaluation
The main evaluation consists of two tests (16/04 and 17/06) and an optional exam (03/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.8 max(Tests, Exam)+0.2 Homework).



Grades

Grades - Homework

Grades - Test 1

Grades - Test 2

Final Grades