Professores responsáveis: André Guedes e Vinícius Fulber-Garcia
Colaboradores/Monitores: Fernando Monteiro Kiotheka (fmkiotheka@inf.ufpr.br), Vinicius Tikara Date (vtvd19@inf.ufpr.br), Roberto Sprengel Minozzo Tomchak (rsmt23@inf.ufpr.br), Pedro Vinicius Sousa da Silva (pvssilva@inf.ufpr.br), Antônio da Ressurreição Filho (arf24@inf.ufpr.br), Nathan Endo (ne24@inf.ufpr.br).
Horário: Quarta-feira, 13:30 até 15:30
Sala de aula: PC-04
Juĝisto: https://maratona.c3sl.ufpr.br/jughisto/
Lista de e-mails: https://listas.inf.ufpr.br/cgi-bin/mailman/listinfo/desafios
- Ao inscrever-se você receberá mensagem pedindo confirmação. Só após a confirmação você estará efetivamente inscrito.
- A lista só aceita mensagens enviadas a partir do endereço com o qual você se inscreveu.
- Você pode inscrever mais de um endereço.
Introdução a algoritmos utilizados em programação competitiva.
Apresentar problemas de programação competitiva e técnicas para soluções.
A cada semana uma nota será atribuída para o desempenho na resolução dos problemas da competição. A nota atribuída é de forma individual e absoluta, não é relativa entre alunos. A média (S) destas semanas será definida pela soma de todas as notas de todos os exercícios dividas por 12 (15 competições, 3 bônus). Pontos extras (proporcionais a 12) serão atribuídos para problemas resolvidos fora dos prazos de cada competição, valendo metade da nota que seria atribuída caso fossem resolvidos dentro do prazo.
Também termos uma prova (em formato de competição) no fim do semestre que terá nota (P) proporcional à quantidade de exercícios resolvidos na prova. A última submissão de exercícios incorretos poderá ser avaliada para atribuição de nota parcial.
A média final (F) será a média simples doas notas. Ou seja, F = (S + P)/2.
O curso mescla: (1) aulas teóricas expositivas ministradas na forma síncrona, incluindo soluções de problemas; (2) leituras feitas pelos alunos de material disponibilizado pelo professor; (3) a realização de competições de programação semanais com problemas ligados ao tema de semana que serão usadas para avaliação
A disciplina será desenvolvida através de aulas de 2h de duração um vez por semana. Nestas aulas serão apresentadas as técnicas descritas para resoluções de problemas, e que serão testadas naquela semana.
Os materiais de leitura e a abertura das competições serão disponibilizadas aos alunos logo após a aula síncrona sobre aquele assunto. Espera-se que o aluno gaste 2 horas no decorrer da semana para resolver os exercícios da prova.
A interação efetiva com os alunos irá ocorrer nas aulas em laboratório e no atendimento remoto via consulta por e-mail. O material das atividades assíncronas será formado de recomendações de leitura, a gravação da aula síncrona e a competição.
Haverá um total de 15 competições semanais, cada uma composta de aproximadamente 5 problemas. A competição terá duração de uma semana a partir da aula semanal. É permitida a discussão geral dos problemas, e a solução contribui para a nota.
[1] Antti Laaksonen. Guide to Competitive Programming: Learning and Improving Algorithms Through Contests. Springer International Publishing AG, 2017. DOI : 10.1007/978-3-319-72547-5 .
[2] Steven Halim e Felix Halim. Competitive Programming 3: The New Lower Bound of Programming Contests. 3ª ed. 2013.
[3] Steven S. Skiena. The Algorithm Design Manual. 3ª ed. Texts in Computer Science. Springer International Publishing, 2020. DOI : 10.1007/978-3-030-54256-6.
[4] Thomas H. Cormen et al. Introduction to Algorithms. 3ª ed. The MIT Press, 2009.
[5] C. H. Papadimitriou e K. Steiglitz. Combinatorial Optimization: Algorithms and Complexity. Dover Pub., 1998.
[6] Donald L. Kreher e Douglas R. Stinson. Combinatorial algorithms: generation, enumeration, and search. Discrete Mathematics and Its Applications. Boca Raton, Florida: CRC Press, 1999. ISBN : 9780849339882.
[7] Antti Laaksonen. Competitive Programmer’s Handbook. 2018. URL: https://cses.fi/book/book.pdf.
[8] Krzysztof Diks et al. Looking for a Challenge 2: Problems from the Polish Collegiate Programming Contest 2011–2014. 2ª ed. University of Warsaw, 2019. URL : https://www.mimuw.edu.pl/~idziaszek/algonotes/looking-for-a-challenge-2-en.pdf.
[9] Jon Kleinberg e Éva Tardos. Algorithm Design. Pearson Education, 2006. URL: https://www.cs.sjtu.edu.cn/~jiangli/teaching/CS222/files/materials/Algorithm%20Design.pdf.
[10] Steven S. Skiena e Miguel A. Revilla. Programming Challenges: The Programming Contest Training Manual. Springler-Verlag New York, 2003. URL: http://acm.cs.buap.mx/downloads/Programming_Challenges.pdf.
[11] Ivanov Maxim et al. CP Algorithms. URL: http://e-maxx.ru/algo/ e https://cp-algorithms.com/ e https://samuraiwesleyjack.github.io/cp-algoritmos/.
[12] Arthur Pratti Dadalto. Ementa Modalidade Programação (OBI). URL: https://olimpiada.ic.unicamp.br/info/ementa/geral/.
[13] Victor de Oliveira Colombo. Material didático sobre algoritmos gulosos. 2018. URL: https://linux.ime.usp.br/~colombo/mac0499/monografia.pdf .
[14] Yan Soares Couto. Algoritmos em sequências. 2016. URL: https://bcc.ime.usp.br/tccs/2016/yancouto/tcc.pdf.
[15] Adrian Vladu e Cosmin Negruşeri. Suffix arrays – a programming contest approach. 2005. URL : http://web.stanford.edu/class/cs97si/suffix-array.pdf.
[16] Maxim Akhmedov. Dynamic programming optimizations. 2017. URL: http://maratona.ic.unicamp.br/MaratonaVerao2017/documents/dp.pdf.
[17] Victor Lecomte. Handbook of geometry for competitive programmers. 2018. URL : https://vlecomte.github.io/cp-geo.pdf.
[18] Pranav A. Sriram. 2014. Olympiad Combinatorics. URL: https://drive.google.com/file/d/1sQtirXxkEfWYuGSKDZ-d7VGYkR_idebY/view.
[19] Cody Johnson. 2015. Algorithms. URL: https://people.bath.ac.uk/masgcs/algorithms.pdf.
[20] C++ Reference. 2021. URL: https://en.cppreference.com.