Diferenças

Esta página mostra as diferenças entre as duas revisões da página.

--- inf05016:2014-2-trabalhos [2014/10/08 15:52]
marcus
+++ inf05016:2014-2-trabalhos [2014/11/05 13:40] (Actual)
marcus [Trabalho 4 (Segmentação de imagens)]
@@ Linha 376: / Linha 376: @@
 </code>
+==== Trabalho 5 (Teste de primalidade) ====
+Entrega: 26/11/2014
+=== Objetivos ===
+  * Implementar o teste de primalidade de Miller & Rabin
+  * Analisar a complexidade do algoritmo em função do tamanho da entrada (log_2(n)) experimentalmente.
+  * Analisar a probabilidade de responder erradamente "sim" experimentalmente.
+=== Casos de teste ===
+  * Números inteiros positivos aleatórios.
+=== Convenções ===
+  * As implementações do algoritmo devem ler um número decimal com até 1000 dígitos da entrada padrão e imprimir "s" na saída padrão caso o número é considerado primo e "n" caso contrário.
+=== Dicas ===
+  * Usa a biblioteca {{http://gmplib.org|GNU MP}} para representar números grandes. Ela tem interfaces para {{http://en.wikipedia.org/wiki/GNU_Multiple_Precision_Arithmetic_Library#Language_bindings|diversas linguagens}} de programação e é simples de usar. Um exemplo em C++:
+  <code c++>
+#include <iostream>
+using namespace std;
+#include <gmpxx.h>
+int main(int argc, char *argv[]) {
+  mpz_class a;
+  cin >> a;
+  cout << "O quadrado de " << a << " é " << a*a << endl;
+}
+</code>

Marcus Ritt