Logică și structuri discrete - Tema 4

Tema se trimite prin Campus Virtual UPT până miercuri ora 22, împreună cu exercițiile date ca temă după laborator.

Exercițiul 1: Demonstrați că mulțimea tuturor șirurilor finite formate cu un alfabet numărabil e numărabilă.
Un alfabet numărabil e o mulțime numărabilă de simboluri (caractere) { c1, c2, ... }.
Indicație: Găsiți o modalitate de a da un număr fiecărui șir, astfel încât să existe doar un număr finit de șiruri are au un număr dat. Descrieți apoi ordinea în care enumerați șirurile.
Alternativă: arătați (prin inducție după n) că mulțimea șirurilor de lungime n e numărabilă. Apoi arătați (folosind un tabel bidimensional ca la numerele raționale) că reuniunea unei mulțimi numărabile de mulțimi numărabile e numărabilă.

Exercițiul 2 Scrieți o funcție care returnează mulțimea tuturor divizorilor unui număr pozitiv n dat ca argument.
Folosiți o funcție auxiliară care acumulează într-un parametru mulțimea divizorilor găsiți și mai are ca parametru divizorul încercat la pasul curent.
Evitați teste de divizibilitate inutile (cu numere > radical din n)
Scrieți apoi funcția de cel mai mare divizor comun în două feluri: cu algoritmul lui Euclid, și obținând maximul dintre divizorii comuni. Verificați pe câteva exemple că dă același rezultat.


Marius Minea
Last modified: Tue Oct 20 22:45:00 EEST 2015