Zadania z egzaminu, 2 termin 2010/2011

Treść:



Zadania
  1. Niech będzie relacją pomiędzy punktami płaszczyzny określoną następująco: dla i
    wtedy i tylko wtedy, gdy
    Sprawdzić czy relacja jest relacją: a) zwrotną b) symetryczną c) przechodnią d) słabo antysymetryczną e) silnie antysymetryczną f) słabo spójną g) silnie spójną. (Podać interpretację geometryczną tej relacji.) (16pkt)
  2. Narysować diagram Hassego relacji porządku o macierzy . Czy ta relacja ma (wskazać je) elementy: najmniejsze, największe, minimalne, maksymalne? Czy jest relacją równoważności? Czy diagram Hassego traktowany jako graf jest: a) drzewem, b) eulerowski, c) hamiltonowski, d) spójny? (12pkt)
  3. Znaleźć rozwiązanie ogólne i rozwiązanie spełniające warunki początkowe równania rekurencyjnego (12pkt)
  4. Znaleźć klucz prywatny RSA dla klucza publicznego (10pkt)
  5. Znaleźć odległość od lewego dolnego wierzchołka grafu z podanego rysunku do pozostałych wierzchołków grafu oraz zaznaczyć kolorem drogi minimalne. (12pkt)
  6. Ile liczb naturalnych mniejszych od 5000 jest podzielnych przez 11 albo 13 (ale nie przez obie te liczby)? (8pkt)

Pytania teoretyczne

  1. Zdefiniować macierz relacji dwuargumentowej. (5pkt)
  2. Sformułować małe twierdzenie Fermata. (5pkt)
  3. Sformułować twierdzenie Kuratowskiego. (5pkt)

Punktacja

70pkt za część zadaniową + 15pkt za część teoretyczną =85pkt

zaliczenie można było otrzymać od 43 pkt za całość (przy minimum 32 pkt za część zadaniową)

Rozwiązania: