Guest User

Untitled

a guest
Jan 19th, 2018
82
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 12.01 KB | None | 0 0
  1. ## Conteúdos
  2.  
  3. * [Algoritmo](#algoritmo)
  4. * [Programa](#programa)
  5. * [Processo Computacional](#processo-computacional)
  6. * [Erros Sintáticos e Erros Semânticos](#erros-sint%C3%A1ticos-e-erros-sem%C3%A2nticos)
  7. * [Fases do Desenvolvimento de um Programa](#fases-do-desenvolvimento-de-um-programa)
  8. * [Estruturas de Dados](#estruturas-de-dados)
  9. * [FIFO](#fifo)
  10. * [LIFO](#lifo)
  11. * [Abstração](#abstra%C3%A7%C3%A3o)
  12. * [Abstração Procedimental](#abstra%C3%A7%C3%A3o-procedimental)
  13. * [Abstração de Dados](#abstra%C3%A7%C3%A3o-de-dados)
  14. * [Metodologia dos Tipos Abstratos de Informação (TADs)](#metodologia-dos-tipos-abstratos-de-informa%C3%A7%C3%A3o-tads)
  15. * [Passagem de Parâmetros](#passagem-de-par%C3%A2metros)
  16. * [Função de ordem superior](#fun%C3%A7%C3%A3o-de-ordem-superior)
  17. * [Recursão e Iteração](#recurs%C3%A3o-e-itera%C3%A7%C3%A3o)
  18. * [Processo Recursivo](#processo-recursivo)
  19. * [Processo Iterativo](#processo-iterativo)
  20. * [Paradigmas de Programação](#paradigmas-de-programa%C3%A7%C3%A3o)
  21. * [Programação Imperativa](#programa%C3%A7%C3%A3o-imperativa)
  22. * [Programação Funcional](#programa%C3%A7%C3%A3o-funcional)
  23. * [Programação por Objetos](#programa%C3%A7%C3%A3o-por-objetos)
  24. * [Funcionais Sobre Listas](#funcionais-sobre-listas)
  25. * [Acumula](#acumula)
  26. * [Filtra](#filtra)
  27. * [Transforma](#transforma)
  28. * [Linguagem BNF](#linguagem-bnf)
  29.  
  30. ## Algoritmo
  31.  
  32. Um algoritmo é uma sequência finita de instruções bem definidas e não ambíguas, cada uma das quais pode
  33. ser executada mecanicamente num período de tempo finito com uma quantidade de esforço finita, de maneira
  34. a atingir um determinado objetivo.
  35.  
  36. 1. **Rigoroso**. Cada instrução do algoritmo deve especificar exata e rigorosamente o que deve ser feito,
  37. não havendo lugar para ambiguidade.
  38. 2. **Eficaz**. Cada instrução do algoritmo deve ser suficientemente básica e bem compreendida de modo a
  39. poder ser executada num intervalo de tempo finito, com uma quantidade de esforço finita.
  40. 3. **Deve terminar**. O algoritmo deve levar a uma situação em que o objetivo tenha sido atingido e não
  41. existam mais instruções para ser executadas.
  42.  
  43. ## Programa
  44.  
  45. Um programa é uma sequência de instruções a ser efetuada pelo computador, determinando o seu comportamento.
  46. São algoritmos escritos numa linguagem de programação.
  47.  
  48. ## Processo Computacional
  49.  
  50. Um ente imaterial que existe dentro de um computador durante a execução de um programa, e cuja evolução ao longo
  51. do tempo é ditada pelo programa.
  52.  
  53. ## Erros Sintáticos e Erros Semânticos
  54.  
  55. Os **erros sintáticos** correspondem ao facto de um programa não estar de acordo com as regras definidas
  56. pela sintaxe da linguagem de programação em uso. Por exemplo, o uso da expressão `+ x y` para somar dois valores.
  57.  
  58. Os **erros semânticos** correspondem ao facto de uma dada parte do programa, embora sintaticamente correta,
  59. não corresponder ao significado que o programador pretendia. Por exemplo, escrever `x + y` quando, na realidade,
  60. se pretendia multiplicar e não somar.
  61.  
  62.  
  63. ## Fases do Desenvolvimento de um Programa
  64.  
  65. - **Análise do problema.** O programador, juntamente com o cliente, estuda o problema a
  66. resolver com o objectivo de determinar exatamente o que o programa deve fazer.
  67. - **Desenvolvimento de uma solução.** Determinação de como vai ser resolvido o problema.
  68. Desenvolvimento de um algoritmo e definição abstrata dos tipos de informação usados.
  69. Deve usar-se a metodologia do topo para a base.
  70. - **Codificação da solução.** Tradução do algoritmo para uma linguagem de programação, e
  71. implementação dos tipos de informação. Depuração, i.e., correção de erros sintáticos
  72. e semânticos.
  73. - **Testes.** Definição de uma bateria de testes com o objetivo de "garantir" que o programa
  74. funciona correctamente em todas as situações possíveis.
  75. - **Manutenção.** Fase que decorre depois do programa estar em funcionamento. A manutenção
  76. é necessária por dois tipos de razões: a descoberta de erros ou a necessidade de introduzir
  77. modificações e atualizações nas especificações do programa.
  78.  
  79. ## Estruturas de Dados
  80.  
  81. ### FIFO
  82.  
  83. "First In First Out" designa o tipo de comportamento em que o primeiro elemento a entrar
  84. numa estrutura de informação será também o primeiro a sair. As estruturas de informação que
  85. seguem este tipo de comportamento são as filas.
  86.  
  87. ### LIFO
  88.  
  89. "Last In First Out" designa o tipo de comportamento em que o último elemento a entrar numa
  90. estrutura de informação será o primeiro elemento a sair. As estruturas de informação que seguem
  91. este tipo de comportamento são as pilhas.
  92.  
  93. ## Abstração
  94.  
  95. Consiste em ignorar certos aspectos de uma entidade, considerando apenas os aspectos relevantes.
  96.  
  97. ## Abstração Procedimental
  98.  
  99. A abstração procedimental corresponde a abstrair o modo como uma função realiza o seu trabalho,
  100. considerando apenas o que ela faz.
  101.  
  102. É utilizada como **mecanismo de controlo da complexidade de programas**, pois quando se
  103. desenvolve um programa são identificados os principais problemas que este tem que resolver,
  104. especificando-se as funções que realizam esse trabalho e sem entrar nos detalhes do modo como
  105. elas realizam o seu trabalho. Depois de escrita uma primeira versão do programa recorrendo à
  106. abstração procedimental, aborda-se o desenvolvimento de cada uma das funções especificadas
  107. utilizando o mesmo método.
  108.  
  109. Em **Python**, a abstração procedimental é realizada através da definição de funções que recebem os
  110. argumentos apropriados.
  111.  
  112. ## Abstração de Dados
  113.  
  114. Consiste em considerar as propriedades de um tipo de dados, ignorando o modo como este é representado.
  115.  
  116. É definido um conjunto de operações básicas que conhecem e podem manipular a representação interna dos objetos
  117. de um tipo abstrato de informação. O resto do programa deve usar estas operações para manipular esses objetos, se não
  118. o fizerem e manipularem diretamente a sua representação interna, estão a **violar as barreiras de abstração** definidas
  119. pelo conjunto de operações básicas do tipo.
  120.  
  121. Para isso definem-se camadas conceptuais lidando com cada um destes aspetos, estando estas camadas separadas por
  122. **barreiras de abstração** que definem o modo como os programas acima da barreira podem comunicar com os programas
  123. que se encontram abaixo da barreira. Idealmente, os programas que se encontram a um dado nível de abstração
  124. contêm toda a informação necessária para lidar com um certo tipo de dados, a informação está "encapsulada" dentro desta
  125. camada concetual, e escondem das restantes partes do programa o modo como a informação está representada, o que é
  126. conhecido por "anonimato da representação".
  127.  
  128. ### Metodologia dos Tipos Abstratos de Informação (TADs)
  129.  
  130. - Identificar as operações básicas:
  131. - **Construtores** (e.g., `cria_racional: int x int --> racional`)
  132. - **Seletores** (e.g., `numerador: racional --> int`)
  133. - **Reconhecedores** (e.g., `e_racional: universal --> logico`)
  134. - **Testes** (e.g., `racionais_iguais: racional x racional --> logico`)
  135. - **Transformadores** (e.g, `escreve_racional: racional ->`)
  136. - Axiomatização: identificar relações que as operações básicas devem verificar entre si.
  137. - Escolher a representação interna.
  138. - Implementar.
  139.  
  140. Esta metodologia garante a abstração de dados no sentido em que as operações básicas, que
  141. definem o comportamento do tipo de informação, são definidas antes da escolha da representação
  142. para o tipo.
  143.  
  144. ## Passagem de Parâmetros
  145.  
  146. - **Parâmetros formais** são os argumentos especificados na definição de uma função.
  147. - **Parâmetros concretos** são os valores que são usados na invocação de uma função.
  148.  
  149. - Na **passagem por valor**, o parâmetro concreto é avaliado e o seu valor é associado
  150. com o respectivo parâmetro formal. A passagem por valor é um mecanismo unidireccional,
  151. do ponto de chamada para a função.
  152. - Na **passagem por referência** a localização de memória da entidade correspondente ao
  153. parâmetro concreto é fornecida ao parâmetro formal. Na passagem por referência o
  154. parâmetro concreto e o parâmetro formal partilham a mesma entidade na memória
  155. do computador.
  156.  
  157. Quando uma função é chamada, é criado um ambiente local, o qual corresponde a uma associação
  158. entre os parâmetros formais e os parâmetros concretos. Este ambiente local desaparece no
  159. momento em que termina a avaliação da função que deu origem à sua criação.
  160.  
  161. ## Função de ordem superior
  162.  
  163. Função com estado interno.
  164.  
  165. ## Recursão e Iteração
  166.  
  167. ### Processo Recursivo
  168.  
  169. Caracteriza-se por possuir uma fase de expansão, correspondente à construção de uma cadeia de operações adiadas,
  170. seguida por uma fase de contração correspondente à execução dessas operações.
  171.  
  172. Exemplo de um processo recursivo linear:
  173.  
  174. ```
  175. misterio(2, 3)
  176. | 6 + misterio(2, 2)
  177. | | 4 + misterio(2, 1)
  178. | | | 2 + misterio(2, 0)
  179. | | | | 0
  180. | | | 2
  181. | | 6
  182. | 12
  183. 12
  184. ```
  185.  
  186. ### Processo Iterativo
  187.  
  188. Caracteriza-se por um certo número de variáveis, chamadas variáveis de estado, juntamente com uma regra que
  189. especifica como atualizá-las. Estas variáveis fornecem uma descrição completa do estado da computação em cada
  190. momento.
  191.  
  192. ## Paradigmas de Programação
  193.  
  194. ### Programação Imperativa
  195.  
  196. Em programação imperativa, um programa é constituído por uma série
  197. de ordens dada ao computador. A programação imperativa depende da instrução de atribuição e da
  198. utilização de ciclos.
  199.  
  200. ### Programação Funcional
  201.  
  202. A programação funcional baseia-se na utilização de funções que devolvem valores que são
  203. utilizados por outras funções. Em programação funcional as operações de atribuição e os ciclos
  204. podem não existir.
  205.  
  206. ### Programação por Objetos
  207.  
  208. A programação por objetos baseia-se na utilização de objetos,
  209. entidades com estado interno associados a um conjunto de métodos que manipulam esse estado.
  210.  
  211. Um **objeto** é uma entidade computacional com estado interno e com um conjunto de operações,
  212. os métodos, que manipulam esse estado interno.
  213.  
  214. Os objetos estão organizados numa hierarquia de classes, subclasses e instâncias, à qual se aplica
  215. o conceito de herança.
  216.  
  217. A **herança** consiste em transmitir o estado interno e os métodos a uma classe a todas as suas
  218. subclasses, exceto se esse estado interno ou esses métodos forem explicitamente alterados numa
  219. subclasse.
  220.  
  221. ## Funcionais Sobre Listas
  222.  
  223. ### Acumula
  224.  
  225. Um acumulador é um funcional que recebe como argumentos uma lista e uma operação aplicável aos
  226. elementos da lista, e aplica sucessivamente essa operação aos elementos da lista original,
  227. devolvendo o resultado da aplicação da operação todos os elementos da lista.
  228.  
  229. Iterativo:
  230.  
  231. ```python
  232. def acumula(f, lst):
  233. res = lst[0]
  234. for x in lst[1:]:
  235. res = f(res, x)
  236. return res
  237. ```
  238.  
  239. Recursivo:
  240.  
  241. ```python
  242. def acumula(fn , lst):
  243. if len(lst) == 1:
  244. return lst[0]
  245. else:
  246. return fn(lst[0], acumula(fn, lst[1:]))
  247. ```
  248.  
  249. ### Filtra
  250.  
  251. Um filtro é um funcional que recebe como argumentos uma lista e um predicado aplicável aos elementos da
  252. lista, e devolve a lista constituída apenas pelos elementos da lista original que satisfazem o predicado.
  253.  
  254. Iterativo:
  255.  
  256. ```python
  257. def filtra(p, lst):
  258. res = []
  259. for x in lst:
  260. if p(x):
  261. res = res + [x]
  262. return res
  263. ```
  264.  
  265. Recursivo:
  266.  
  267. ```python
  268. def filtra(fn, lst):
  269. if lst == []:
  270. return lst
  271. elif fn(lst[0]):
  272. return [lst[0]] + filtra(fn, lst[1:])
  273. else:
  274. return filtra(fn, lst[1:])
  275. ```
  276.  
  277. ### Transforma
  278.  
  279. Um transformador é um funcional que recebe como argumentos uma lista e uma operação aplicável aos elementos
  280. da lista, e devolve uma lista em que cada elemento resulta da aplicação da operação ao elemento correspondente
  281. da lista original.
  282.  
  283. Iterativo:
  284.  
  285. ```python
  286. def transforma (tr, lista):
  287. res = list()
  288. for e in lista:
  289. res = res + [tr(e)]
  290. return res
  291. ```
  292.  
  293. Recursivo:
  294.  
  295. ```python
  296. def transforma(fn, lst):
  297. if lst == []:
  298. return lst
  299. else:
  300. return [fn(lst[0])] + transforma(fn, lst[1:])
  301. ```
  302.  
  303. ## Linguagem BNF
  304.  
  305. - `<..>` - Símbolos não terminais
  306. - `...` - Símbolos terminais
  307. - `::=` - É definido como
  308. - `|` - Ou
  309. - `*` - Zero ou mais
  310. - `+` - Um ou mais
  311.  
  312. Exemplo:
  313.  
  314. ```
  315. <S> :: = <A>a
  316. <A> :: = a<B>
  317. <B> :: = <A>a|b
  318. ```
  319.  
  320. Símbolos terminais: `a, b`
  321. Símbolos não terminais: `<S>, <A>, <B>`
Add Comment
Please, Sign In to add comment