PRG1-2012-2-Engenharia

PRG1 - PROGRAMAÇÃO I

CARGA HORÁRIA

TOTAL: 72 HORAS (4 HORAS/SEMANA)

TEÓRICA: 36 HORAS

LABORATÓRIO: 36 HORAS

DIAS COM AULA: 36 (18 semanas)

EMENTA

Introdução a lógica de programação e algoritmos. Constantes, variáveis e tipos de dados. Operadores aritméticos, relacionais e lógicos. Concepção de fluxograma e pseudocódigo. Estruturas de decisão e estruturas de repetição. Introdução a linguagem de programação c. Vetores de caracteres e multidimensionais. Ponteiros e aritmética de ponteiros. Funções: chamada por valor e por referência. Chamada recursiva de funções. Tipos de dados compostos. Operação com arquivos textos e binários.

Bibliografia Básica

• SCHILDT, Herbert. C Completo e Total - 3.ed. [S.l.]: Makron, 1997. 830p. ISBN 978-8534605953

Referências Complementares

• Apostila adotada: Curso de Linguagem C - Engenharia Elétrica - UFMG

• Apostila sobre Lógica de Programação

AULAS

AULA 1 DIA 5/10/2012

Como fazer um churrasco

Vamos observar atentamente este vídeo para iniciarmos o nosso curso de programação:

EmbedVideo received the bad id "U0xSYIXE9vo#!" for the service "youtube".

O que tem o churrasco com a nossa aula??
Trata-se de uma sequência de passos para execução  
de um objetivo.

EXERCÍCIO: Na forma textual, descrever as etapas
para fazer um bom churrasco.

O que é um algoritmo

Um algoritmo pode ser visto como uma sequência de instruções ou operações que resolvem um dado problema.

A receita de um bom churrasco corresponde 
a um algoritmo.

Como representar um algoritmo ?

Uma forma é representar na forma textual ordenada:

1.Comprar a carne
2.Colocar carvão na churrasqueira
3.Acender o carvão
4.Cortar a carne (picanha)
5.Espetar a carne
6.Salgar a carne
7.Colocar a carne na churrasqueira
8.Aguardar a carne ficar no ponto desejado
9.Bater a carne
10.Servir a carne

Outras formas são mais apropriadas para o uso no meio computacional:

• pseudo-código
• fluxogramas

A PENSAR: É possível mudar a ordem das instruções?
É possível paralelizar algumas instruções?

O problema da raposa, do milho e da galinha

EmbedVideo received the bad id "yifW9XueSaI#!" for the service "youtube".

EXERCÍCIO 1: Descrever na forma de etapas um 
solução para o problema da raposa, do milho e da galinha.

Note que somente é possível escrever o algoritmo se tivermos uma solução para o problema.

EXERCÍCIO 2: Descrever na forma de etapas uma 
solução para o problema dos canibais/padres.

Torres de Hanoi

Veja este jogo:

EmbedVideo received the bad id "hLnuMXO95f8#!" for the service "youtube".

EXERCÍCIO 3: Escrever na forma de etapas numeradas a solução para o problema 
das torres de Hanói usando 3 discos.

EXERCÍCIO 4: Escrever na forma de etapas numeradas a solução para o problema 
das torres de Hanói usando 4 discos.

E para quem são os algoritmos?

Uma receita de bolo é apropriada para ser executada 
por um ser humano. 
Um procedimento de como trocar um pneu também. 
Mas muitas vezes  queremos que o algoritmo seja executado 
por uma máquina! O computador é perfeito para isto!

Neste curso vamos nos concentrar no desenvolvimento de
algoritmos simples,  desde a sua concepção até  a sua  
implementação através de uma LINGUAGEM DE
PROGRAMAÇÃO, em um computador.

Um PROGRAMA implementa um algoritmo. É o algoritmo 
materializado na forma de uma sequência de instruções.

Neste sentido, vamos entender minimamente o funcionamento de um computador.

Como funciona um computador? Como ele executa programas ("receitas")?

• Partes de um computador:
  • UCP (CPU) (Unidade Central de Processamento)
  • Barramentos
  • Memórias: Primária (semicondutora -> RAM e ROM) e Secundárias (disco, pendrive)
  • Dispositivos de Entrada e Saída de Dados (Teclado, Monitor etc)

• O computador é digital:
  • Dados e Instruções são sequências de bits
  • Representação de dados em sistemas computacionais: uso de códigos (ex:código ASCII);

 A -> 01000001
 B -> 01000010

• • As instruções também são palavras binárias interpretadas pela CPU;

De forma simplificada podemos dizer que as instruções ficam em uma 
memória de programa enquanto os dados a serem processados pelo programa
ficam em uma memória de DADOS;

O programa que está na memória de programa está escrito
em LINGUAGEM DE MÁQUINA

• Funcionamento Simplificado de um Computador

Suponha que um programa a ser executado se encontra em uma memória de programa.
Ao ligar o sistema, a CPU busca na memória de programa uma instrução a ser executada
(ciclo de busca) e, então, executa a instrução (ciclo de execução). Na SEQUÊNCIA,
a CPU busca a PRÓXIMA instrução na memória de programa, e assim sucessivamente...

O fluxo de execução do programa é, a princípio SEQUENCIAL no sentido 
que a execução de uma instrução é realizada somente após a execução da instrução 
antecedente.

(apresentação do Prof.Semprebom sobre computadores)

Possíveis linguagens de programação

Na prática, é inviável desenvolver programas complexos em
LINGUAGEM DE MÁQUINA.
Em geral, utilizamos linguagens de ALTO NÍVEL que podem, de
alguma forma, serem traduzidas (compiladas) para a linguagem
de baixo nível ou interpretadas em tempo de execução.

Exemplo:

• Linguagem C
• Fortran
• Basic
• C++
• Pascal
• Java
• Python

 Neste curso utilizaremos a linguagem C. Por que? 
 É uma linguagem muito usada na implementação de produtos 
 eletrônicos, incluindo àqueles voltados as Telecomunicações.

Um exemplo completo

PROBLEMA: Computar a média de dois números reais fornecidos pelo teclado. Mostrar o resultado no monitor.

SOLUÇÃO:

ALGORITMO
DADOS DE ENTRADA: NUM1 e NUM2
DADOS DE SAÍDA: MEDIA
INÍCIO
 1.Ler NUM1
 2.Ler NUM2
 3.MEDIA <- (NUM1+NUM2)/2
 4.Mostrar MEDIA
FIM

/* Calculador de media de dois números reais */
#include <stdio.h>

main()
{
  float num1,num2;

  scanf(&num1);
  scanf(&num2);
  media = (num1+num2)/2;
  printf ("media =\n", media);
}

EXERCÌCIO 5: Implementar o algoritmo com o Scratch.

Plano de Ensino

Agora que temos uma ideia do que será tratado neste curso, vamos apresentar o plano de ensino.

AULA 2 DIA 9/10/2012

Objetivos

O aluno deverá ser capaz de:

• Entender o significado de variáveis e sua relação com a memória de um computador;
• Utilizar fluxogramas para descrever algoritmos simples, usando caixa de ínicio/fim, caixa de processos (instruções) e caixas decisão;
• Identificar os pontos fortes e fracos no uso de fluxogramas;
• Identificar tipo de variáveis
• Construir expressões usando variáveis e constantes usando os 4 operadores matemáticos e exponenciação;
• Construir expressões usando operadores lógicos;
• Construir instruções de atribuição a uma variável;

Recordando o significado de algoritmo

Um algoritmo é um "um conjunto de instruções para resolver um determinado problema".

O nome advém de al-Khwārizmī

Segundo Knuth um algoritmo deve:

• Sempre terminar após um determinado número de passos. Caso contrário, é chamado (por Knuth) de método computacional;
• Cada passo do algoritmo deve ser precisamente definido (sem ambiguidades);
• Um certo número (ou nenhum) de dados de entrada deve ser fornecido no início ou dinamicamente na execução do algoritmo;
• Ter dados de saída, resultantes do processamento dos dados de entrada;
• Ser efetivo, no sentido que suas operações sejam simples e se executem em tempo finito de tempo;

Não existe algoritmo para fazer um algoritmo

É sempre bom lembrar que não existe um algoritmo para fazer um algoritmo. Podemos considerar que fazer um algoritmo é uma forma de arte.

No entanto, existem algumas diretrizes que podem ser consideradas. Vamos ver estas:

• Comprender bem o problema é fundamental para a solução;

“If I had an hour to solve a problem I'd spend 55 minutes thinking about the problem and 5 
minutes thinking about solutions.”
― Albert Einstein

• Tentar enumerar estratégias possíves;
• Tentar dividir o problema e resolver os subproblemas.

A Descrição de Algoritmos usando Fluxogramas

Um fluxograma é uma linguagem semi-gráfica que pode ser utilizada 
para descrição de algoritmos.

Exemplo: O algoritmo de cálculo da média de dois números da aula anterior:

Pontos fortes:

• permite fácil entendimento do algoritmo, mesmo para pessoas leigas;

Ponto fraco:

• a descrição das estrutura dos dados inexiste. O usuário deve descrevê-los a parte;

Observe no exemplo anterior que nada é dito sobre as variáveis NUM1, NUM2 e MEDIA.

Símbolos de um Fluxograma

Teste de Mesa

Constantes, Variáveis

Algoritmos operam sobre dados. O que podem ser estes dados?

Variáveis e Constantes

No exemplo anterior podemos identificar três variáveis NUM1, NUM2 e MEDIA Também podemos identificar uma CONSTANTE. O número 2.

• Tipo de Variáveis:
  • Numéricas: reais e inteiras

Ex: NUM1 = 5.5 /* NUM1 é uma variável real */

• • Booleanas: true ou false

Ex: RES = TRUE /* RES é uma variável booleana */ 

• • caracter:

Ex: LETRA = 'A'

• • alfanumérica

Ex: FRASE = "ALO MUNDO"

E como estas variáveis armazenam os dados?? Depende da linguagem usada. Vamos passar
uma primeira noção do C

Expressões

Expressões sentenças que relacionam variáveis e constantes através de operadores matemáticos
e que RESULTAM em um valor. A instrução do algoritmo:

MEDIA = (NUM1 + NUM2) / 2 

será considerada como uma expressão, que usa os operadores '+', '/' e '='

O operador '=' é um OPERADOR DE ATRIBUIÇÃO e indica que a expressão do lado direito
do '=' será atribuída a variável do lado esquerdo.

Neste curso, para mantermos coerência com a Linguagem C, consideraremos que a expressão
como um todo resulta no valor que é atribuído a variável.

Operadores Aritméticos

Os operadores aritméticos que usaremos neste curso serão os disponíveis no C:

Operador	Significado
+	adição
-	subtração
*	multiplicação
/	divisão
%	resto

O único operador desconhecido aqui é o resto, cujo significado é o resto entre dois números
inteiros. Exemplo, se B possui o valor 9, então o resultado da atribuição na expressão:
A = B%2 
será 1.

Operadores relacionais

Os operadores relacionais permitem realizar comparações entre dois operandos. Os operadores são os seguintes:

Operador	Significado
>	maior que
>=	maior ou igual que
<	menor que
<=	menor ou igual que
==	igual a (se o operando a esquerda é maior que o da direita)
!=	diferente de (se o operando a esquerda é diferente do da direita)

LINK PARA O EDITOR YED

Se você quiser um editor de fluxogramas pode utilizar a ferramenta abaixo:

Se baixar o zip com o java, descompactar, entrar no diretório e executar com:

java -jar yed.jar

• Editor Yed

Sheldon e o fluxograma da amizade

Vamos observar o fluxograma da amizade do Sheldom da série de TV "Big Bang Theory"

EmbedVideo received the bad id "VAX4jLlNo-Q#!" for the service "youtube".

Observer que a caixa no formato de LOSANGO permite testar uma condição: é uma caixa de decisão.

Controle do Fluxo de Execução: Caixas de Decisão

Em algumas situações é necessário realizar algum teste sobre uma expressão. Seja o problema:

Problema do Controle de Acesso

PROBLEMA: Controlar o acesso a uma porta usando uma senha pré-configurada no sistema. DADO DE ENTRADA: SENHA (variável alfanumérica) DADO DE SAÌDA: porta aberta (simulado com msg "PORTA ABERTA") ou mensagem de "SENHA NAO CONFERE"

EXERCÍCIO: Elaborar um fluxograma para o o problema de controle de acesso
prevendo um procedimento para modificar a senha de acesso. Para tanto,
assuma a existência de uma senha de administrador fixa (por exemplo,
"xY12"). Se a senha do administrador for fornecida, mostrar um menu de
modificação de senha. A nova senha deve ser repetida.

Exercícios

OBS: sempre anote antes do fluxograma os tipos  e significado das variáveis usadas,
caracterizando os dados de entrada e os de saída.

1. Apresentar um fluxograma para ler 3 números e fazer a média;
2. Fazer um teste de mesa usando como valores de entrada 2.0, 5.0 e 3.0;
3. Construir um fluxograma para ler 3 números e calcular a média dos dois maiores números lidos;
4. Refazer o exercício anterior, para calcular a média do maior e do menor número entre os 3 lidos.
5. Considere um algoritmo para calcular o comprimento de uma circunferência. Quem são os dados de entrada e os dados de saída. Fazer um fluxograma para resolver o problema;
6. Modifique o algoritmo acima para calcular, além do comprimento, a área da circunferência;
7. Considere que a função de uma reta é dada por: $y=5x+2$. Elabore um fluxograma para calcular o valor de y dado o valor de x.
8. Um estudo sobre sensibilidade de pessoas a temperaturas da água identificou que a maioria das pessoas considera fria a água com temperaturas abaixo de 25 graus, morna entre 25 e 30 graus, e quente acima de 30 graus. Escreva um algoritmo na forma de fluxograma que mostre as palavras "fria", "morna" ou "quente" dependendo da temperatura da água que for informada;

AULA 3 DIA 11/10/2012

Objetivos

O aluno deverá ser capaz de:

• construir fluxogramas usando estruturas de repetição;
• compreender o aninhamento de estruturas de controle de fluxo
• dividir problemas em subproblemas e utilizar subrotinas para organizar a solução.

Quebrando um problema em subproblemas: SUBPROGRAMAS

PROBLEMA: Aprimorar o exemplo do controle de acesso para que, no caso de 3 tentativas de acesso seguidas, com senha errada, o sistema seja bloqueado.

• DADOS DE ENTRADA: SENHA /* variável que armazena a senha entrada pelo usuário ou administrador */
• DADOS DE SAÍDA: mensagem de abertura da porta / usuário bloqueado*/
• VARIÁVEIS INTERMEDIÁRIAS: CONT_ACESSO /* valor inicial zero - incrementada a cada senha inválida */

Note que a variável CONT_ACESSO é iniciada com zero e
incrementada a cada erro no fornecimento da senha. A 
atribuição CONT_ACESSO = CONT_+ACESSO + 1 deve ser 
interpretada da forma: acesse o valor de CONT_ACESSO e some 1
a este valor. Coloque o resultado novamente em CONT_ACESSO
(o conteúdo anterior é sobrescrito!)

Neste procedimento pode ser observado que:

• começa a aparecer uma certa complexidade no fluxograma;
• Além disto, não ficou uma abordagem muito interessante, pois se for o administrador que erra a senha, ele pode bloquear o usuário;
• não existe forma de desbloquear a senha (zerar o contador), a não ser mudando a senha.

Em síntese, existem subproblemas adicionais a serem resolvidos. Como podemos resolvê-los sem deixar um fluxograma complexo?

Usaremos a caixa de processos pré-definidos que usaremos para invocar funções que resolvem determinado subproblema.

Inicialmente, vamos construir três subprogramas:

• Iniciar_Sistema(): inicia variáveis do sistema, colocando o sistema em um estado inicial conhecido;
• Tratar_Admin(): é o código que trata a funcionalidade associada ao administrador;
• Tratar_User(): é a funcionalidade que trata o usuário (procedimento de abrir porta, bloquear etc).

OBS: Note que foi usada uma variável auxiliar AUX que permite ajustar o valor
de número de acessos a ser mostrado no display. Note também que na caixa DISPLAY foi usado
uma string a ser impressa e a variável AUX cujo conteúdo deve ser impresso. Ambos separados
por vírgula.

• ANINHAMENTO DE DECISÔES

A função Tratar_User() se utiliza de aninhamento de decisões. Em um primeiro momento é testado se a senha confere com a senha do usuário. SE ela conferir ENTÂO é testado se o contador de bloqueios está dentro do aceitável.

Estruturas de repetição

No exemplo de controle de acesso da aula passada já construímos uma estrutura de repetição (um loop infinito). Vamos elaborar um pouco mais estas estruturas de repetição.

Uma das grandes vantagens de um sistema computacional é a capacidade de repetir um conjunto de instruções
possivelmente sobre dados diferentes, a uma velocidade muito grande.

PROBLEMA: Calcular a somatório de N valores a serem fornecidos pelo teclado.

$S=\sum _{i=0}^{N-1}a_{i}=a_{0}+a_{1}+..+a_{N-1}$

DADOS DE ENTRADA:

• N /* número de valores */,
• a_i /* valor de um dos N números a serem inseridos */

DADOS DE SAÌDA = S /* somatório */

NOTA: Observe que a estrutura de repetição utilizada é caracterizada por um teste (decisão) de uma expressão que deverá resultar em verdadeiro enquanto houver número a ser lido (dentro da quantidade N de números), um contador de itens lidos "i" e um bloco de repeticão terminado em um arco que conduz o fluxo de execução ao início da decisão.

Mapeamento de Estruturas de Controle do Scratch em Estruturas de Fluxograma

Fluxograma	C	Comentário
		O fluxogram do programa principal corresponde a função main() do C. A primeira instrução que se executa é a primeira instrução da função main() e a última instrução é a última do main()
	if (y>5) { x=x+1; z=z+1; }	Observar que quando existe mais de uma instrução simples sob o controle do if, deve-se usar as chaves (conceito de bloco).

EXERCÍCIOS

EXERCÍCIO 1: Modificar o sistema de controle de acesso para incluir a inserção de nome de usuário (USERID) e senha (SENHA). Prever a existência de dois usuários (USERID_1, USERID_2, SENHA_1, SENHA_2). O admin poderá ser identificado pelo nome ADMIN. Prever bloqueio por usuário (duas variáveis contadores). Sugestão: criar funcões separadas para tratamento de cada usuário. Em breve veremos como podemos contornar esta duplicação através da parametrização de funções/subprogramas.

EXERCÍCIO 2: Implementar o sistema do exercício 1 com o Scratch. Simule as funções usando envio de sinais (isto foi feito no projeto integrador do semestre passado).

EXERCÍCIO 3: Escrever um fluxograma que leia como dados de entrada dois números inteiros positivos: "s" e "q". O programa deve computar os dez primeiros números da PG (progressão geométrica), onde "s" é o número inicial e "q" a razão da progressão.

Obs: Para PG tem-se:

$a_{1}=s$

$a_{n}=q\times a_{n-1}$ ou

$a_{n}=a_{1}.q^{n-1}\,\!$

EXERCÍCIO 4: Implementar um fluxograma que permita computar a somatória dos N primeiros termos de uma PG, cujos valores de "s" e "q" são também fornecidos como dados de entrada.

AULA 4

OBJETIVOS

O aluno deverá ser capaz de:

• Fazer mapeamento de estruturas de controle de fluxo do fluxograma para o Scratch;
• Compor expressões utilizando operadores relacionais e lógicos;
• Parametrizar e retornar valores em subprogramas;
• distinguir e usar variáveis locais e globais;

Expressões Lógicas

Nas aulas anteriores utilizamos expressões usando operadores aritméticos e relacionais. É possível construir expressões ainda mais completas usando os operadores lógicos, apresentados abaixo:

Operador	Significado
&&	AND
||	OR
!=	NOT

AULA 35

SOLUÇÔES:

1.Atravessar G
2.Retornar
3.Atravessar M
4.Retornar G
5.Atravessar R
6.Retornar
7.Atravessar G

1.ATR CP
2.RET P
3.ATR CC
4.RET C
5.ATR PP
6.RET PC
8.ATR PP
9.RET C
10.ATR CC
11.RET C
12.ATR CC

PROBLEMA: determinar as raízes da equação do segundo grau (Baskara)
DADOS DE ENTRADA: coeficientes reais A, B e C
DADOS DE SAÍDA: raízes X1-REAL,X1-IMG e X2-REAL, X2-IMAG 
VARÍAVEIS INTERMEDIÁRIAS: DELTA
COMENTÁRIO: DELTA pode ser positivo, 0 ou negativo. O valor de DELTA deve ser testado.

FLUXOGRAMA

1. Construir um fluxograma para ler 3 números e calcular a média dos dois maiores números lidos;
2. Construir um fluxograma para ler 3 números e calcular a média do maior e do menor número entre os 3 lidos.

1. Refazer o exercício para ler 3 números e calcular a média dos dois maiores números lido usando variáveis auxiliares MAIOR e MENOR;
2. Refazer o exercício 4 para calcular a média do maior e do menor número entre os 3 lidos usando variáveis auxiliareas MAIOR e MENOR;
3. Construir um fluxograma para ler 6 números e calcular a média dos dois maiores números lidos. Faça um teste de mesa;

1. Faça um algoritmo para fazer a divisão de dois números reais. Antes de dividí-los deve ser feito um teste de validade. Caso não seja possível dividi-los, deve ser mostrada uma mensagem de erro. Se for possível, deve-se mostrar o resultado da divisão;
2. Fazer um algoritmo para computar a área e perímetro de um retângulo. Entrar com os dois lados;
3. Fazer um programa para computar as áreas de um retângulo e de um círculo. O programa deve mostrar uma mensagem indicando qual figura possui maior área;