Escrita de algoritmos

1. Escreva um algoritmo para somar dois números decimais inteiros usando somente a tabuada.

   a) Identifique entrada e saída desse problema.

   b) Defina um conjunto de instruções elementares que são necessárias para resolver esse problema.

   c) Escreva um algoritmo para o problema em português. Que tipos de estruturas de controle e estruturas de dados você utilizou?

2. Ana dá uma volta no percurso de corrida do Lago a cada 15 min. Suponha que um amigo comece a correr X minutos mais tarde em um ritmo de Y min por volta. Dados X e Y, Ana e seu amigo irão se encontrar no início da volta antes de uma hora? Quando?

   a) Identifique entrada e saída desse problema.

   b) Defina um conjunto de intruções elementares que são necessárias para resolver esse problema.

   b) Construa um algoritmo para o problema na forma de um diagrama de fluxo.

3. Em um hospital, é preciso escalar um médico para plantão em cada dia da semana. Queremos construir um novo vetor plantao com 7 posições, em que plantao[j] contém a matrícula do médico escalado para o dia $j$. Suponha que medico é um vetor de dimensão $N$, onde $N \le 7$ é o número de médicos e medico[i] é a matrícula do $i$-ésimo médico. O objetivo é obter uma escala mais justa possível.

   a) O problema acima não está bem definido porque a noção de “escala justa” pode ser interpretada de diversas maneiras distintas; como você descreveria uma escala justa? A partir de sua interpretação, descreva a entrada e a saída desse problema usando uma linguagem mais formal do que na descrição acima.

   b) Um funcionário do hospital escreveu o algoritmo abaixo.

   1. plantao[1] ← medico[1];
   2. dia ← 2;
   3. enquanto dia ≤ 7 faça:
   4.   - plantao[dia] ← plantao[dia - 1];
   5.   - dia ← dia + 1;
   

   Liste todas as variáveis e vetores desse algoritmo. Depois, faça um desenho da configuração da memória nos seguintes momentos:

   • antes de executar o algoritmo;
   • logo após a linha 2 ser executada;
   • logo após a linha 5 ser executada (em cada uma das iterações do laço)

   c) Argumente (informalmente ou formalmente) que o algoritmo acima não está correto de acordo com a especificação de saída que você descreveu.

Linguagens de programação

Observe os seguintes trechos de código realizam o produto escalar de vetores em diferentes linguagens de programação. Você não precisa entender o que eles fazem.

C:

#include <stdio.h>

static double dot_product(double *a, double *b, int n) {
    double sum = 0;
    int i;
    for (i = 0; i < n; i++) {
        sum = sum + a[i] * b[i];
    }
    return sum;
}

int main() {
    double a[] = {1, 3, -5};
    double b[] = {4, -2, -1};

    printf("%lf", dot_product(a, b, 3));
}

Java:

public class DotProduct {

	public static double dotProduct(double[] a, double[] b){
		double sum = 0;
		for (int i = 0; i < a.length; i++){
			sum += a[i] * b[i];
		}
		return sum;
	}

	public static void main(String[] args) {
		double[] a = {1, 3, -5};
		double[] b = {4, -2, -1};
		System.out.println(dotProduct(a,b));
	}
}

Matlab:

a = [1 3 -5]
b = [4 -2 -1]
c = dot(a, b)

Pascal:

program Product;

type ArrayDoubles = array[1..3] of Double;

function DotProduct(const a, b : ArrayDoubles): Double;
var
  i: integer;
begin
  DotProduct := 0;
  for i := 1 to Length(a) do
    DotProduct := DotProduct + (a[i] * b[i]);
end;

var
  a, b: ArrayDoubles;
begin
  a[1] := 1;
  a[2] := 3;
  a[3] := -5;
  b[1] := 4;
  b[2] := -2;
  b[3] := -1;
  WriteLn(DotProduct(a, b));
end.

Python:

def dot_product(a, b):
    return sum(aterm * bterm for aterm, bterm in zip(a, b))

a, b = [1, 3, -5], [4, -2, -1]
print(dot_product(a,b))

1. Para cada uma das linguagens, tente identificar palavras-chaves, estruturas de controle e nomes de variáveis, vetores, tipos de dados ou sub-rotinas.

2. As sintaxes dessas linguagens são muito diferentes. Por exemplo, em todos os programas inicializamos dois vetores tridimensionais $a =(1, 3, -5)$ e $b = (4, -2, -1)$, mas a maneira que inicializamos esses vetores muda em cada uma delas. Descubra como inicializar um vetor de tamanho 4 em cada uma dessas dessas linguagens. Tente descrever regras genéricas e precisas para inicializar vetores nessas linguagens com um tamanho arbitrário. Depois, escreva um trecho de código em cada uma delas inicializando um vetor $z = (1, 2, 3, 4)$.

3. Todas essas linguagens são chamadas linguagens de alto nível porque escondem ou abstraem instruções de máquina. Mas, para manipular vetores de números, os trechos de algumas linguagens são mais simples do que os de outras. Desse modo, podemos dizer que uma linguagem é de mais baixo nível ou de mais alto nível do que outra (quando queremos realizar determinada tarefa). Para a tarefa de calcular o produto interno, procure classificar essas linguagens, começando pela de mais baixo nível para a de mais alto nível.

4. Se você conhece um pouco de inglês, talvez consiga adivinhar o que algumas das instruções significa. Por exemplo sum = sum + a[i] * b[i]; é uma atribuição a uma variável que soma ao valor anterior o produto a[i] * b[i]. Para descobrir se nosso chute está correto, é preciso estudar a semântica de cada uma das linguagens, i.e., qual é o significado de cada símbolo, de cada palavra-chave e de cada estrutura de controle. Responda:

   a) Qual é o símbolo que representa atribuição em cada uma das linguagens?

   b) É verdade que sempre que o asterisco * aparece nesses trechos, ele representa a operação de multiplicação de dois valores?

   c) Qual o significado do símbolo += na versão em C?

5. Das linguagens acima, normalmente são compiladas C e Pascal e normalmente são interpretadas Matlab e Python. Os motivos para usar interpretação ou compilação variam. Por exemplo, Matlab é normalmente utilizado para explorar e prototipar algoritmos que realizam uso extensivo de operações de álgebra linear. Qual a desvantagem de utilizar compilação nesse caso? Explique dizendo a diferença entre intrepretação e compilação.

Exercícios criativos

1. Quando compilamos o programa em C com um compilador para processadores Intel x86, um trecho do código em linguagem de montagem que obtemos é o seguinte:

   ; [...]
   dot_product:
   .LFB0:
       .cfi_startproc
       endbr64
       pushq	%rbp
       .cfi_def_cfa_offset 16
       .cfi_offset 6, -16
       movq	%rsp, %rbp
       .cfi_def_cfa_register 6
       movq	%rdi, -24(%rbp)
       movq	%rsi, -32(%rbp)
       movl	%edx, -36(%rbp)
       pxor	%xmm0, %xmm0
       movsd	%xmm0, -8(%rbp)
       movl	$0, -12(%rbp)
       jmp	.L2
   .L3:
       movl	-12(%rbp), %eax
       cltq
       leaq	0(,%rax,8), %rdx
       movq	-24(%rbp), %rax
       addq	%rdx, %rax
       movsd	(%rax), %xmm1
       movl	-12(%rbp), %eax
       cltq
       leaq	0(,%rax,8), %rdx
       movq	-32(%rbp), %rax
       addq	%rdx, %rax
       movsd	(%rax), %xmm0
       mulsd	%xmm1, %xmm0
       movsd	-8(%rbp), %xmm1
       addsd	%xmm1, %xmm0
       movsd	%xmm0, -8(%rbp)
       addl	$1, -12(%rbp)
   .L2:
       movl	-12(%rbp), %eax
       cmpl	-36(%rbp), %eax
       jl	.L3
       movsd	-8(%rbp), %xmm0
       popq	%rbp
       .cfi_def_cfa 7, 8
       ret
   ; [...]
   

   Já a linguagem Java é particular. Normalmente, ela é compilada, mas não para a linguagem de máquina real, mas sim para o que chamamos de bytecode, que é uma linguagem de uma máquina virtual chamada Java Virtual Machine (JVM). A JVM é um programa nativo que “interpreta” o bytecode e executa no computador real.

   Quando compilamos o trecho em Java para JVM, um trecho do bytecode que obtemos é o seguinte:

   [...]
   public static double dotProduct(double[], double[]);
   Code:
      0: dconst_0
      1: dstore_2
      2: iconst_0
      3: istore        4
      5: iload         4
      7: aload_0
      8: arraylength
      9: if_icmpge     30
     12: dload_2
     13: aload_0
     14: iload         4
     16: daload
     17: aload_1
     18: iload         4
     20: daload
     21: dmul
     22: dadd
     23: dstore_2
     24: iinc          4, 1
     27: goto          5
     30: dload_2
     31: dreturn
   [...]
   

   a) Não podemos utilizar o código em assembly compilado do programa em C em outros processadores que não tenham a mesma arquitetura Intel x86. Por quê? O que precisamos fazer para executar esse trecho em C em um computador com processador baseado em ARM?

   b) Já o mesmo trecho em bytecode pode ser utilizado para qualquer arquitetura real em que uma JVM execute. No entanto, o programa que simula a máquina virtual deve ser específico para cada processador. Explique.

← Anterior Voltar Próximo →