Relato da reunião de 20/JAN/2014 Início: 12h Término: 13h05m Próxima reunião será 03/FEV no CCSL das 12h às 13h. Presentes: Lucas (2o. BCC), Vinícius (3o. BCC), Victor (3o. BCC), Schaeffer(4o. BCC), Samuel (ex-BCC), Wilson (ex-BCC), Igor (ex-BCC), Hirata (prof), Walter (prof), Carlinhos (prof) Coelho (prof) -------------------------------------------------------- Prato do dia: Walter vai falar sobre "Há lugar para uma disciplina de computação científica em um curso de computação?" No CS2013 o mais próximo disto é CN - Computational Science As habilidades relacionadas estão no questionário http:/bcc.ime.usp.br/fundamentais/2 Só por diversão, veja também http://introcs.cs.princeton.edu/java/91float/ -------------------------------------------------------- Informes: * Relembrar a carta de intenções da nova grade "Carta de intenções para Reformulação da Grade Curricular do BCC". que foi entregue ao Conselho de DCC. Essa carta pode ser vista na página do Apoio ao BCC na paca. http://paca.ime.usp.br/course/view.php?id=511 * (Pedro) Prévia da pesquisa como o egresso bcc.ime.usp.br -> ex-alunos -> Relatório parcial da pesquisa * (Igor) Disciplina O BM pretende criar uma disciplina "How to prove it" que parece que tem o mesmo objetivo da disciplina "Fundamentos de Matemática para Computação". A ementa da disciplina MATXXXX - Introdução ao Pensamento Matemático pode ser vista no final do relatório. * Pessoal de Algoritmos está trabalhando nas ementas de Princípios (MAC0122), ED (MAC0323) e AA (MAC0338) http://www.ime.usp.br/~pf/ementas-novas/ O final desta mensagem tem uma lista das habilidades em Algoritmos que aparecem no CS2013. * Pedro não poderá participar das reuniões da comissão do Conselho do DCC sobre a grade curricular Precisamos de alguém para substituí-lo nas reuniões dos profs sobre a grade curricular. O Igor tem participado das reuniões junto com o Pedro. As próximas reuniões estão agendadas para 13/FEV 27/MAR 22/MAI 14/AGO 18/SET 9/OUT 13/NOV ------------------------------------------------------------ Não consegui anotar direito os comentários (coelho) Walter: Cálculo numérico é mais importante que o raciocínio matemático. A dúvida ou angústia é Como manter o aluno interessado em uma disciplina como esta? Uma demonstração é o mesmo que um algoritmo, mas não são muitos os alunos que enxergam dessa. Samuel: Queremos que os alunos aprendam a fazer demonstrações? Walter: Muitos alunos sabem o quicksort sem entender o significado do consumo de tempo médio desse algoritmo ser O(n lg n). O mercado tem espaço para pessoas quem sabem algoritmos, matemática, métodos numéricos, estatística, .... mas também precisa de pessoas que saibam juntar os "pedaços". Juntar os pedaços não é algo fácil e também requer uma certa habilidade. [Nota do coelho: aqui parecia que estava se discutindo programming in small X programming in large] Ninguém vai morrer se sair do BCC sem morrer se não souber numérico ou uma coisa assim. Queremos pessoas que façam "programação em small" (= "fazer os pedaços). Wilson: O BCC não um curso de Tecnologia da Informação, senão devemos mudar o nome do curso. Em Ciência da Computação o aluno deve também desenvolver a habilidade de "fazer os pedaços". Nada contra o alunos ser mais habilidoso em "juntar os pedaços" ou outras coisas. Walter: Programar componentes ou sistemas são habilidades importantes. Devemos formar os dois tipos de alunos. O aluno deve escolher os seus caminhos. Carlinhos: Acreditamos que o currículo do BCC deve ser amplo o suficiente para dar a oportunidade dos alunos escolher entre diversos caminhos. O que é fundamental e importante para todas as ênfases/módulos/... deve obrigatório. Eu acho importante o contato do aluno com programação numérica. Walter: Para dar está experiência numérica o o aluno deve experimentar. O legal seria bolar um curso focado em problemas concretos em que o aluno deva desenvolver programas numéricos. O ideal seria fazer um curso em que os alunos resolvessem coisas interessantes. Hirata: Que tal um "Laboratório de Cálculo, Álgebra Linear..." em que os alunos programassem os que vêm em Cálculo, Álgebra,... Carlinhos: Que tal uma disciplina de laboratório? Gostaria que o aluno soubesse modelagem, inclusive modelagem de programação linear. Seria legal uma disciplina que apresentasse aplicações numéricas interessante. Hirata: Seria legal um disciplina que todos achassem que o conteúdo é importante. Carlinhos: Tem coisas muito legais, zero de funções, integração numérica é muito legal. Gostei da ideia de uma disciplina que seja um "Laboratório numérico". Schaffer: O CS2013 fala algo sobre Cálculo Numérico. Coelho O CS2013 não entra nessas coisas. [Em tempo, o CS2013 tem uma Knowledge Area chamada Computational Science onde trata de modelagem, simulação... "Computational Science is a field of application of computer science to solve problems acros a range of disciplines..." As habilidades a serem desenvolvidas estão em no questionário http://bcc.ime.usp.br/fundamentais/2] Walter: Poderíamos tentar fazer uma disciplina que fosse "orientada a problemas numéricos: e suas aplicações" e os alunos programassem bastante. Fazer um disciplina de "Laboratória de Programação Científica". Carlinhos: Para uma ementa eu pensaria nos tópicos e colocaria "aplicações" na parte dos trabalhos. Wilson: Como deixar claro que na disciplina terá vários EPs. Carlinhos: Dá para colocar na ementa, créditos trabalho. Final. O Walter ficou de pensar em uma disciplina e apresentar em uma próxima reunião "Laboratório de Computação Científica" onde o aluno aplicasse ideia básicas cálculo numérico(?) modelagem (?), simulação(?). =============================================================== MATXXXX - Introdução ao Pensamento Matemático Créditos Aula: 2 Créditos Trabalho: 2 Carga Horária Total: 90h Tipo: Semestral Ativação: ? Objetivos: Familiarizar o aluno com a linguagem matemática e com a estrutura das demonstrações matemáticas, bem como com alguns fatos e noções elementares sobre números, conjuntos, funções e relações. A apresentação dos tópicos do programa deve ser entrelaçada com discussões sobre notação, conectivos lógicos e suas tabelas-verdade, quantificadores, hipótese e tese, tipos de demonstrações (decomposições em casos, demonstrações por absurdo, contrapositivas), exemplos de argumentos válidos e inválidos, etc. Programa Resumido Noções básicas sobre números inteiros, indução finita, conjuntos, funções e relações. Programa 1. Números inteiros e fatos elementares sobre divisibilidade. Infinitude do conjunto dos números primos. Inexistência de um número racional cujo quadrado é igual a 2. Indução finita e Princípio da Boa Ordem. Somatórios e produtórios finitos. Fórmulas de soma de progressão aritmética e geométrica, fórmula do binômio, fórmula para a soma dos n primeiros quadrados. 3. Conjuntos: subconjuntos, operações (união, interseção, diferença), uniões e interseções de famílias, leis de De Morgan e propriedades das operações. Conjunto das partes, produto cartesiano. 4. Funções: injetoras, sobrejetoras, bijetoras, inversas. Imagens diretas e inversas de conjuntos por funções. Identidades envolvendo imagens diretas e inversas e operações com conjuntos. 5. Relações binárias: reflexiva, simétrica/anti-simétrica, transitiva. Relações de equivalência e de ordem (parcial ou total). Classes de equivalência e conjunto quociente. Exemplos de conjunto quociente: classes de congruência módulo n, construção dos racionais a partir dos inteiros. Funções definidas em conjuntos quocientes por escolhas de representantes. Avaliação Listas de exercícios e provas escritas. Método Aulas teóricas e de exercícios. Critério Média ponderada de provas e exercícios. Norma de Recuperação Cada docente (ou equipe) deverá decidir qual o peso p, onde 1<=p<=4. A média final será média ponderada da nota do semestre com a da recuperação com o peso acima. Bibliografia 1. D. J. Velleman, How to prove it - a structured approach, Cambridge University Press, Cambridge, 2nd.ed., 2006, 384pp. 2. U. Daepp and P. Gorkin, Reading, writing, and proving - a closer look at mathematics, Springer, New York, 2003, 395pp. 3. E. D. Bloch, Proofs and fundamentals - a first course in abstract mathematics, Springer, New York, 2nd.ed., 2011, 359pp. 4. J. P. D'Angelo and D. B. West, Mathematical thinking - problem-solving and proofs, Prentice-Hall, Upper Saddle River, 2nd.ed., 2000, 412pp. 5. H. Schlichl, R. Steinbauer; Einführung in das mathematische Arbeiten, 2a. ed., 2012, Springer-Lehrbuch XIV, 520pp. ============================================================= O CS2013 é "Orientado a Habilidades (Outcomes)". No CS2013 há um "Knowledge Area" chamada "Algorithms and Complexity" que é divida nos seguintes tópicos: - Basic Analysis - Algorithmic Strategies - Fundamental Data Structures and Algorithms - Basic Automata Computability and Complexity - Advanced Computational Complexity - Advanced Automata Theory and Computability - Advanced Data Structures Algorithms and Analysis Esses tópicos aparecem no questionário http://bcc.ime.usp.br/fundamentais/1 que alguns de vocês preencheram. Nesse exercício as habilidades encontradas nesses tópicos foram distribuídas entre MAC0122, MAC0323, MAC0338 e MACsobrou . AVISO Esse exercício _não_ é uma ementa. Esse exercício _não_ tem cara de ementa. Esse exercício _não_ pretende ser uma emente. "Este exercício" is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . = MAC0122 Princípios de Desenvolvimento de Algoritmos Objetivos. --------- Idealmente... após concluir esta disciplina espera-se que os alunos sejam capazes de: - realizar análise assintóticas informais e empíricas de um algoritmo; - argumentar sobre a correção de um algoritmo; - demonstrar familiaridade com algoritmos de busca, ordenação e estruturas de dados básicas; - reconhecer estratégias algorítmicas básicas; e - implementar algoritmos e estruturas de dados básicas Habilidades trabalhadas. ----------------------- Idealmente... os estudantes que completaram essa disciplina demonstraram a habilidade de: - Explicar a diferença entre "melhor caso", "caso médio" e "pior caso" de um algoritmo - No contexto de um algoritmo específico, identificar as características dos dados e outras condições ou suposições que levam a comportamentos diferentes. - Determinar informalmente o consumo de tempo e espaço de um algoritmo simples. - Argumentar informalmente sobre a correção de algoritmos através de invariantes. - Entender a definição formal de O-grande. - Realizar estudos empíricos para validar hipóteses sobre o consumo de tempo de um algoritmo simples proveniente de uma análise matemática. Executar algoritmos sobre entradas de vários tamanhos e comparar o seu desempenho. - Usar backtracking recursivo para resolver um problema como percorrer um labirinto. - Implementar algoritmos simples de busca e explicar as diferenças entre os seu consumos de tempo - Implementar algoritmos de ordenação quadráticos e O(n lg n). - Implementar algoritmos de força bruta. - Discutir o consumo de tempo e espaço dos principais algoritmos de busca e ordenação. - Entender a diferença entre busca em largura e em profundidade. - Entender a propriedade de um heap e usar heaps para implementar filas de prioridade. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . = MAC0323 Algoritmos e Estruturas de Dados Objetivos. --------- Idealmente... após concluir esta disciplina espera-se que os alunos sejam capazes de: - demonstrar familiaridade com as principais estruturas de dados utilizadas em projetos de algoritmos; - realizar uma análise assintótica de tempo e espaço dessas estruturas e reconhecer situações algorítmicas em que podem ser empregadas. - escolher entre várias estruturas de dados apropriadas para um problema e justificar a sua escolha; - explicar os principais algoritmos em grafos e suas análises. - explicar os principais algoritmos de busca de padrões e suas análises. Habilidades trabalhadas. ----------------------- Idealmente... os estudantes que completaram essa disciplina demonstraram a habilidade de: - Transformar com facilidade pseudocódigo em uma implementação, implementar exemplos de estratégias de algoritmos e aplicá-las em problemas específicos. - Entender a implementação de tabelas de hash, incluindo como evitar colisões - Discutir o consumo de tempo e espaço dos principais algoritmos de busca e hashing. - Implementar estruturas de dados para dicionários, filas, filas com prioridades e ser capaz de discutir os seus consumos de tempo e espaço. - Implementar as estruturas de dados mais elementares para conjuntos dinâmicos e analisar as operações realizadas com essas estruturas. Relatar sobre algoritmos que utilizam essas estruturas de dados como um componente chave. Relatar sobre algoritmos que utilizam essas estruturas e como o seu consumo de tempo depende delas. - Resolver problemas usando algoritmos fundamentais em grafos, incluindo busca em largura e em profundidade. - Avaliar estruturas dados, selecionar entre as possíveis opções, justificar a sua escolha e implementar a estrutura em um contexto particular. - Resolver problemas usando algoritmos em grafos, incluindo caminhos mínimo a partir de uma fonte ou entre todos os pares e pelo menos um algoritmo para encontrar uma árvore espalhada mínima. - Utilizar grafos para modelar problemas em engenharia, quando apropriado. Sintetizar algoritmos que utilizam operações sobre grafos como um de seus componentes chaves e analisá-los. - Discutir o conceito de uma máquina de estados finitos. - Gerar uma expressão regular para representar uma linguagem específica. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . = MAC0338 Projeto e Análise de Algoritmos Objetivos. --------- Idealmente... após concluir esta disciplina espera-se que os alunos sejam capazes de: - realizar uma análise assintótica do desempenho de um algoritmo; - escrever uma demonstração rigorosa de correção de um algoritmo; - demonstrar familiaridade com os principais algoritmos e estruturas de dados; - aplicar estratégias algorítmicas e métodos de análise importante; e - sintetizar algoritmos eficiente de situações comuns. Habilidades trabalhadas. ----------------------- Idealmente... os estudantes que completaram essa disciplina demonstraram a habilidade de: - Transformar com facilidade pseudocódigo em uma implementação, implementar exemplos de estratégias de algoritmos e aplicá-las em problemas específicos. - Usar formalmente a notação O-grande para descrever o consumo de tempo e espaço de algoritmos - Explicar o uso de Omega, Teta e o-pequeno para descrever o consumo de tempo e espaço de algoritmos - Uso de relações de recorrência para determinar a complexidade de tempo de algoritmos recursivos. - Resolver equações de recorrência fundamentais, por exemplo, usando alguma forma do Teorema Mestre. - Para cada uma das estratégias (força bruta, gulosa, divisão e conquista, backtracking, programação dinâmica) identificar um exemplo em que ela se aplica. - Dar exemplos que ilustram situações de "custo benefício" (trade-offs) entre tempo e espaço de algoritmos - Usar algoritmos de divisão e conquista para resolver um problema apropriado. - Usar algoritmos gulosos para resolver um problema apropriado e determinar se a regra gulosa leva a uma solução ótima. - Usar programação dinâmica para resolver um problema apropriado. - Descrever vários métodos de heurísticas para resolver problemas. - Usar uma heurística apropriada para resolver um problema apropriado. - Demonstrar a habilidade de avaliar algoritmos, selecionar entre as possíveis opções, justificar a sua escolha e implementar o algoritmo em um contexto particular. - Implementar um algoritmo de busca de padrões. - Usar técnicas avançadas (por exemplo, aleatorização, aproximação) para resolver problemas reais. - Aplicar técnicas avançadas de análise de algoritmos (por exemplo, amortizada, probabilística). - Listar e contrastar classes de complexidade padrão. - Definir a classe P e NP. - Explicar o "significância/implicação/sentido/" (significance) de NP-completude . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . DEPÓSITO DE HABILIDADES QUE SOBRARAM - Projetar uma máquina de estados finitos para aceitar uma linguagem específica. - Explicar porque o problema da parada não tem solução algorítmica - Projetar uma gramática livre de contexto para representar uma linguagem específica - Definir EXP - Apresentar exemplos clássicos de problemas NP-completos. - Demonstrar que um problema é NP-completo através da redução de um problema NP-completo clássico. - Determinar o lugar de uma linguagem na hierarquia de Chowsky (regular, livre de contexto, recursivamente enumerável) - Demonstrar que uma linguagem especifica está em uma classe e não está em uma classe inferior. - Converter entre notações de poder equivalente, incluindo entre DFAs, NFAs e expressões regulares e entre PDAs e CFGs. - Explicar a tese de Church-Turing e a seu "significância/implicação/sentido/" (significance) - Explicar o Teorema de Rice e o seu "significância/implicação/sentido/" (significance) - Apresentar exemplos de funções não computáveis. - Demonstrar que um problema não é computável através da redução a um problema clássico não computável. - Entender a modelagem entre problema do mundo real e soluções algorítmicas (por exemplo, problemas e grafos, programação linear, etc.) - Analisar o consumo de tempo médio de algoritmos "probabilísticos/aleatórios/aleatorizados" (randomized algorithms). Utilizar variáveis aleatórias indicadoras e linearidade da esperança para realizar a análise. "Relatar/narrar" (recite) análises de algoritmos que utilizam esse método. - Explicar as propriedades básicas de algoritmos "probabilísticos/aleatórios/aleatorizados" (randomized algorithms) Relatar (recite) sobre algoritmos que utilizam aleatorização. Explicar a diferença entre algoritmos probabilísticos e algoritmos com entradas probabilísticas (? análise probabilística de algoritmos determinísticos ?). - Analisar algoritmos através de análise amortizada, quando apropriado. "Relatar/narrar" (recite) sobre algoritmos simples que são analisados através desse método. Descrever estratégias diferentes de análise amortizada. - Descrever a estratégia de divisão-e-conquista e explicar quando uma situação pede por ela. Relatar sobre algoritmo que utilizam essa estratégia. Relatar sobre algoritmos que usam essa estratégia. - Descrever a estratégia de programação dinâmica e explicar quando uma situação pede por ela. Relatar sobre algoritmo que utilizam essa estratégia. Relatar sobre algoritmos que usam essa estratégia. - Descrever a estratégia gulosa e explicar quando uma situação pede por ela. Relatar sobre algoritmo que utilizam essa estratégia. Relatar sobre algoritmos que usam essa estratégia. - Explicar os principais algoritmos de ordenação. Relatar as suas análises e as estratégias algorítmicas que utilizam. Relatar sobre algoritmos que utilizam ordenação como uma subrotina. Derivar limites inferiores para o consumo de tempo de algoritmos baseados em comparação e explicar como esses limites podem ser superados. - Demonstrar familiaridade com cenários algorítmicos (geometria computacional, pesquisa operacional, segurança e criptografia, computação paralela e distribuída, sistemas operacionais, e arquitetura de computadores) através do relato de algoritmos relevantes em cada cenário.