Matemática Discreta Licenciatura em Informática Frequência Jan 2018 PDF
Document Details
Uploaded by Deleted User
Escola Superior de Gestão e Tecnologia de Santarém
2018
Tags
Summary
This is a past paper for a Mathematics Discrete course for undergraduate students of informatics, from January 2018. The paper includes questions on topics like logic, set theory, graphs, and algorithms, requiring justified answers based on the concepts of the course. The questions are for the students to test their understanding of the concepts and apply them in specific situations.
Full Transcript
Escola Superior de Gestão e Tecnologia de Santarém Matemática Discreta Licenciatura em Informática Frequência...
Escola Superior de Gestão e Tecnologia de Santarém Matemática Discreta Licenciatura em Informática Frequência Duração: 2h 16 janeiro de 2018 Todas as repostas deverão ser devidamente justificadas. 1. Estude a validade do argumento: p⇔~q (1,5val.) p t sr ~(~ s q) ~ (q ~r p) t 2. Classifique em IR e em IN a condição: p(x): x2 < 4 (1,0val.) 3. Considere em IR os seguintes conjuntos: A = {x IR: 3x2 - 5x - 2 = 0} B = {x IR: x ≤ 4} C ={ x IR: 12 – 2x ≥ 2} Defina sob a forma de intervalo ou reunião de intervalos o conjunto: (A ∪ ) \ C (1,5val.) (1,5val.) 4. Sejam os grafos: Kn, Cn e Wn. Indique, justificando, para que valores de “n” os grafos referidos são: 4.1 bipartidos? (1,5val.) 4.2 regulares? 5. Considere a matriz: (1,5val.) (1,5val.) (1,5val.) 5.1 Represente o grafo G correspondente à matriz de adjacência A e em seguida o gafo complementar de G. 5.2 Indique, através do calculo matricial, o numero de 2-caminho existem entre os vértices v2 e v3. (2,0val.) 6. Verifique se o grafo abaixo é de Euler, em caso afirmativo indique o circuito através do algoritmo de Hierholzer. 7. É dado o grafo G: (1,75val.) 7.1 Através do algoritmo de Kruscal construa uma árvore geradora minimal. (1,75val.) 7.2 Calcule o número cromático do grafo dado, aplicando o algoritmo respectivo. Explique por que razão o grafo não pode ter um número cromático inferior a 3. (1,5val.) 8. Verifique se o grafo abaixo é de Hamilton, se for indique esse circuito, se não apresente um argumento que mostre porque esse circuito não existe. E um caminho de Hamilton? Justifique a sua resposta indicando esse caminho ou apresente uma justificação, caso não exista. 9. Calcule o menor custo para a passagem aérea entre Boston e Los Angels, sendo que o grafo abaixo (3,0val.) atribui às arestas as tarifas mais económicas praticadas entre as várias cidades. Justifique aplicando o algoritmo de Dijkstra. Frequência – Matemática Discreta Doc. Resp.: Professora Isabel Duarte Página 2 Frequência – Matemática Discreta Doc. Resp.: Professora Isabel Duarte Página 3
