01.Introdução MC102.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    },
    "toc": true
   },
   "source": [
    "<h1>Table of Contents<span class=\"tocSkip\"></span></h1>\n",
    "<div class=\"toc\" style=\"margin-top: 1em;\"><ul class=\"toc-item\"><li><span><a href=\"#MC102---Algoritmos-e-Programação-de-Computadores\" data-toc-modified-id=\"MC102---Algoritmos-e-Programação-de-Computadores-1\"><span class=\"toc-item-num\">1&nbsp;&nbsp;</span>MC102 - Algoritmos e Programação de Computadores</a></span><ul class=\"toc-item\"><li><span><a href=\"#Computação\" data-toc-modified-id=\"Computação-1.1\"><span class=\"toc-item-num\">1.1&nbsp;&nbsp;</span>Computação</a></span></li><li><span><a href=\"#Duas-idéias-fundamentais-de-ciência-da-computação\" data-toc-modified-id=\"Duas-idéias-fundamentais-de-ciência-da-computação-1.2\"><span class=\"toc-item-num\">1.2&nbsp;&nbsp;</span>Duas idéias fundamentais de ciência da computação</a></span><ul class=\"toc-item\"><li><span><a href=\"#Algoritmos\" data-toc-modified-id=\"Algoritmos-1.2.1\"><span class=\"toc-item-num\">1.2.1&nbsp;&nbsp;</span>Algoritmos</a></span></li><li><span><a href=\"#Processamento-de-Informações\" data-toc-modified-id=\"Processamento-de-Informações-1.2.2\"><span class=\"toc-item-num\">1.2.2&nbsp;&nbsp;</span>Processamento de Informações</a></span></li><li><span><a href=\"#Exercício\" data-toc-modified-id=\"Exercício-1.2.3\"><span class=\"toc-item-num\">1.2.3&nbsp;&nbsp;</span>Exercício</a></span></li><li><span><a href=\"#Resumo\" data-toc-modified-id=\"Resumo-1.2.4\"><span class=\"toc-item-num\">1.2.4&nbsp;&nbsp;</span>Resumo</a></span></li></ul></li><li><span><a href=\"#Linguagens-de-Programação\" data-toc-modified-id=\"Linguagens-de-Programação-1.3\"><span class=\"toc-item-num\">1.3&nbsp;&nbsp;</span>Linguagens de Programação</a></span><ul class=\"toc-item\"><li><span><a href=\"#Expressando-algoritmos-em-linguagens-de-programação\" data-toc-modified-id=\"Expressando-algoritmos-em-linguagens-de-programação-1.3.1\"><span class=\"toc-item-num\">1.3.1&nbsp;&nbsp;</span>Expressando algoritmos em linguagens de programação</a></span></li><li><span><a href=\"#Exemplo-do-algoritmo-&quot;Raiz-Quadrada&quot;-em-Python\" data-toc-modified-id=\"Exemplo-do-algoritmo-&quot;Raiz-Quadrada&quot;-em-Python-1.3.2\"><span class=\"toc-item-num\">1.3.2&nbsp;&nbsp;</span>Exemplo do algoritmo \"Raiz Quadrada\" em Python</a></span></li></ul></li><li><span><a href=\"#Programa-de-Estudos\" data-toc-modified-id=\"Programa-de-Estudos-1.4\"><span class=\"toc-item-num\">1.4&nbsp;&nbsp;</span>Programa de Estudos</a></span><ul class=\"toc-item\"><li><span><a href=\"#Este-curso-irá-abranger-três-aspectos-principais-da-computação:\" data-toc-modified-id=\"Este-curso-irá-abranger-três-aspectos-principais-da-computação:-1.4.1\"><span class=\"toc-item-num\">1.4.1&nbsp;&nbsp;</span>Este curso irá abranger três aspectos principais da computação:</a></span></li><li><span><a href=\"#Porque-aprender-a-programar-(alguns-exemplos)\" data-toc-modified-id=\"Porque-aprender-a-programar-(alguns-exemplos)-1.4.2\"><span class=\"toc-item-num\">1.4.2&nbsp;&nbsp;</span>Porque aprender a programar (alguns exemplos)</a></span></li></ul></li><li><span><a href=\"#O-que-será-necessário\" data-toc-modified-id=\"O-que-será-necessário-1.5\"><span class=\"toc-item-num\">1.5&nbsp;&nbsp;</span>O que será necessário</a></span><ul class=\"toc-item\"><li><span><a href=\"#Jupyter-Notebook\" data-toc-modified-id=\"Jupyter-Notebook-1.5.1\"><span class=\"toc-item-num\">1.5.1&nbsp;&nbsp;</span>Jupyter Notebook</a></span></li></ul></li><li><span><a href=\"#Extras\" data-toc-modified-id=\"Extras-1.6\"><span class=\"toc-item-num\">1.6&nbsp;&nbsp;</span>Extras</a></span></li><li><span><a href=\"#Créditos\" data-toc-modified-id=\"Créditos-1.7\"><span class=\"toc-item-num\">1.7&nbsp;&nbsp;</span>Créditos</a></span></li></ul></li></ul></div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# MC102 - Algoritmos e Programação de Computadores\n",
    "\n",
    "É difícil imaginar o nosso mundo sem computadores, embora não pensemos muito\n",
    "nos computadores reais. Também é difícil imaginar o que a raça humana fez sem\n",
    "tecnologia de computadores nestes milhares de anos e que o mundo, como o\n",
    "conhecemos hoje, esteja tão envolvido com a tecnologia da informação nos últimos\n",
    "25 anos.  Neste curso vocês aprenderão sobre **ciência da computação**, que é o\n",
    "estudo da **computação** que tornou possível essa nova tecnologia e este novo\n",
    "mundo. Vocês também aprenderão a usar os computadores de forma eficaz e adequada\n",
    "para melhorar sua própria vida e a vida dos outros."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Computação\n",
    "\n",
    "Uma **computação** é uma seqüência de operações bem definidas que levam de um ponto de partida inicial para um resultado final desejado.\n",
    "- note que esta definição não inclui a palavra \"computador\"\n",
    "- uma computação é um processo que pode ser realizado por uma pessoa ou máquina\n",
    "- a mesma computação pode ser realizada usando qualquer uma de várias tecnologias diferentes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Duas idéias fundamentais de ciência da computação\n",
    "\n",
    "Como a maioria das áreas de estudo, a ciência da computação se concentra em um\n",
    "amplo conjunto de idéias inter-relacionadas. Duas das mais básicas são:\n",
    "**algoritmos** e **processamento de informações**. Essas idéias serão introduzidas de\n",
    "forma informal, mas posteriormente vamos examiná-los com mais detalhes."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Algoritmos\n",
    "\n",
    "- A seqüência de etapas realizada durante uma computação é definida por um **algoritmo**\n",
    " - um algoritmo pode ser pensado como uma \"receita\"\n",
    " - \"Siga estas etapas e você irá resolver o problema\"\n",
    "- Um algoritmo inclui uma descrição completa do\n",
    " - conjunto de insumos ou condições iniciais\n",
    "   - uma especificação completa do problema a ser resolvido\n",
    " - conjunto de saídas\n",
    "   - descrições de soluções válidas para o problema\n",
    " - seqüência de operações que acabará por produzir o resultado\n",
    "   - as etapas devem ser simples e precisas"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Pessoas já efetuavam cálculos muito antes da invenção de dispositivos de computação\n",
    "modernos, e muitos continuam a usar dispositivos de computação que consideramos\n",
    "primitivos. Por exemplo, considere a forma como os comerciantes efetuavam\n",
    "troco para clientes em mercados antes da existência de cartões de crédito,\n",
    "calculadoras de bolso ou caixas registradoras. Efetuar troco pode ser uma\n",
    "atividade complexa. Provavelmente levou algum tempo para aprender a fazê-lo, e\n",
    "é preciso algum esforço mental para fazê-lo correto sempre. Vamos considerar o que\n",
    "está envolvido neste processo."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "O primeiro passo é calcular a diferença entre o preço de compra e a quantia de\n",
    "dinheiro que o cliente entrega ao comerciante. O resultado desse cálculo é o\n",
    "valor total que o comerciante deve retornar ao comprador. Por exemplo, se você\n",
    "comprar uma dúzia de ovos no mercado dos agricultores por $R\\$2,39$ e você entrega\n",
    "ao agricultor uma nota de $R\\$10$, ele deve retornar $R\\$7,61$ para você. Para\n",
    "produzir esse valor, o comerciante seleciona, por exemplo, uma nota de $R\\$5,00$,\n",
    "uma nota de $R\\$2,00$ e as moedas de $50$ centavos, $10$ centavos e $1$ centavo."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Poucas pessoas conseguem subtrair números de três dígitos sem recorrer a alguma\n",
    "ajuda manual, como lápis e papel. Como vocês aprenderam na escola primária, a\n",
    "subtração pode ser realizada com lápis e papel seguindo uma seqüência de etapas\n",
    "bem definidas. Vocês provavelmente já fizeram isso inúmeras vezes, mas nunca\n",
    "fizeram uma lista das etapas específicas envolvidas. Fazer essas listas para\n",
    "resolver problemas é algo que os cientistas da computação fazem o tempo todo.\n",
    "Por exemplo, a seguinte lista de etapas descreve o processo de subtrair dois\n",
    "números usando um lápis e papel:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**Passo 1**: Anote os dois números, com o número maior acima do número menor e seus\n",
    "dígitos alinhados nas colunas da direita para a esquerda.\n",
    "\n",
    "**Passo 2**: Selecione a coluna mais à direita para iniciar o processo de subtração.\n",
    "\n",
    "**Passo 3**: Anote abaixo a diferença entre os dois dígitos na coluna de dígitos atual,\n",
    "emprestando um $1$ da próxima coluna do número superior à esquerda, se necessário.\n",
    "\n",
    "**Passo 4**: Se não houver uma próxima coluna à esquerda, pare. Caso contrário, vá\n",
    "para a próxima coluna à esquerda e vá para o Passo 3."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Se o agente de computação (neste caso um ser humano) seguir cada uma dessas\n",
    "etapas simples corretamente, todo o processo resultará em uma solução correta\n",
    "para o problema dado. Assumimos no **Passo 3** que o agente já sabe como calcular a\n",
    "diferença entre os dois dígitos em qualquer coluna, emprestando da coluna à esquerda,\n",
    "se necessário."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Para realizar o troco, a maioria das pessoas pode selecionar a combinação de\n",
    "notas e moedas que representam a quantidade de troco correta, sem qualquer\n",
    "ajuda manual, além das moedas e notas. Mas os cálculos mentais envolvidos\n",
    "ainda podem ser descritos de forma semelhante aos passos anteriores, e podemos\n",
    "recorrer a escrevê-los no papel se houver uma disputa sobre a correção do\n",
    "troco.  A sequência de etapas que descreve cada um desses processos\n",
    "computacionais é chamada de algoritmo. Informalmente, um algoritmo é como uma\n",
    "receita. Ele fornece um conjunto de instruções que nos diz como fazer algo,\n",
    "como fazer trocos, assar pão ou construir um automóvel. Mais precisamente, um\n",
    "algoritmo descreve um processo que termina com uma solução para um problema. O\n",
    "algoritmo também é uma das idéias fundamentais da ciência da computação."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Um algoritmo tem as seguintes caracteristicas:\n",
    "\n",
    "1: Um algoritmo consiste em um número finito de instruções.\n",
    "\n",
    "2: Cada instrução individual em um algoritmo está bem definida. Isso significa\n",
    "que a ação descrita pela instrução pode ser realizada efetivamente ou ser\n",
    "executada por um agente de computação. Por exemplo, qualquer agente de\n",
    "computação capaz de cálculos aritméticos pode calcular a diferença entre dois\n",
    "dígitos.  Portanto, um passo algorítmico que diz \"calcular a diferença entre\n",
    "dois dígitos\" seria bem definido. Por outro lado, um passo que diz \"dividir um\n",
    "número por 0\" não está bem definido, porque nenhum agente de computação poderia\n",
    "realizá-lo."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "3: Um algoritmo descreve um processo que eventualmente pára depois de chegar a\n",
    "uma solução para um problema. Por exemplo, o processo de subtração pára depois\n",
    "que o agente de computação reduz a diferença entre os dois dígitos na coluna de\n",
    "dígitos mais à esquerda.\n",
    "\n",
    "4: Um algoritmo resolve uma classe geral de problemas. Por exemplo, um\n",
    "algoritmo que descreve como fazer o troco deve funcionar para qualquer duas\n",
    "quantias de dinheiro cuja diferença seja maior ou igual a $0$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "A capacidade de dividir uma tarefa em suas partes componentes é um dos\n",
    "principais trabalhos de um programador de computador. Uma vez que podemos\n",
    "desenvolver um algoritmo para resolver um problema, podemos automatizar a\n",
    "tarefa de resolver o problema. Os computadores podem ser projetados para\n",
    "executar um pequeno conjunto de algoritmos para realizar tarefas\n",
    "especializadas, como o funcionamento de um forno de microondas. Mas também\n",
    "podemos criar computadores, como o notebook de vocês, capazes de executar uma\n",
    "tarefa descrita por qualquer algoritmo. Esses computadores são verdadeiras\n",
    "máquinas de solução de problemas de propósito geral. Eles são diferentes de\n",
    "qualquer máquina que já construímos antes, e eles formaram a base do mundo\n",
    "completamente novo em que vivemos.  Mais adiante nós iremos ver uma notação\n",
    "para expressar algoritmos para serem executados pelos computadores bem como\n",
    "algumas sugestões para projetar algoritmos. Vocês verão que os algoritmos e o\n",
    "pensamento algorítmico são fundamentos críticos de qualquer sistema de\n",
    "informação."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Processamento de Informações\n",
    "\n",
    "Desde que os seres humanos aprenderam a escrever, vários milhares de anos atrás,\n",
    "eles processaram a informação. A própria informação tomou muitas formas em sua\n",
    "história, das marcas impressas na argila na Mesopotâmia antiga, aos primeiros\n",
    "textos escritos na Grécia antiga, às palavras impressas nos livros, jornais e\n",
    "revistas produzidas em massa desde a Renascença, aos símbolos abstratos da\n",
    "matemática e da ciência modernas utilizados nos últimos 350 anos. Recentemente,\n",
    "no entanto, os seres humanos desenvolveram a capacidade de automatizar o\n",
    "processamento de informações construindo computadores. No mundo moderno dos\n",
    "computadores, a informação também é comumente referida como dados."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    " **Mas o que é informação?**\n",
    " \n",
    "Como os cálculos matemáticos, o processamento da informação pode\n",
    "ser descrito com algoritmos. Em nosso exemplo anterior de efetuar o troco, as\n",
    "etapas de subtração envolveram a manipulação de símbolos usados para\n",
    "representar números e dinheiro. Ao levar a cabo as instruções de qualquer\n",
    "algoritmo, um agente manipula a informação. O agente de computação começa com\n",
    "algumas informações (conhecidas como entrada), transforma essas informações de\n",
    "acordo com regras bem definidas e produz novas informações, conhecidas como\n",
    "saída."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "É importante reconhecer que os algoritmos que descrevem o processamento\n",
    "da informação também podem ser representados como informações. Os cientistas da\n",
    "computação conseguiram representar algoritmos de uma forma que pode ser\n",
    "executada de forma eficaz e eficiente pelas máquinas. Eles também criaram\n",
    "máquinas reais, chamadas de computadores digitais eletrônicos, que são capazes\n",
    "de executar estes algoritmos.  Os cientistas da computação descobriram mais\n",
    "recentemente como representar muitas outras coisas, como imagens, audio\n",
    "e vídeo, como informação. Muitos dos meios de comunicação e dispositivos de\n",
    "comunicação que agora damos por certo seriam impossíveis sem esse novo tipo de\n",
    "processamento de informações."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Exercício\n",
    "\n",
    "Descreva um algoritmo que seja capaz de calcular a raiz quadrada de um número\n",
    "inteiro positivo usando somente as operações básicas (adição, subtração,\n",
    "multiplicação e divisão)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "**Definição** (declarativa, isto é, \"o que é verdadeiro\"):\n",
    "\n",
    "$\\sqrt{x} = y$, tal que $y >= 0$  e $y^2 = x$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**Solução** (imperativa, isto é, \"como fazer\"):\n",
    "\n",
    "Como exemplo de solução, vamos usar o método de Newton de Aproximações Sucessivas.\n",
    "Este método nos diz que sempre que tivermos um palpite $y$ para o valor da raiz\n",
    "quadrada de um número $x$, podemos realizar uma manipulação simples para obter\n",
    "uma melhor adivinhação (próxima à raiz quadrada real) com a média entre $y$ e\n",
    "$x/y$. Por exemplo, podemos calcular a raiz quadrada de 2 da seguinte maneira.\n",
    "Suponha que nosso palpite inicial seja 1:\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**Dividindo a tarefa em componentes**:\n",
    "\n",
    "**Passo1**: Comece com um palpite para $y$\n",
    "\n",
    "**Passo2**: Se $y*y$ estiver próximo o suficiente de $x$, pare e diga que $y$ é a resposta\n",
    "\n",
    "**Passo3**: Caso contrário, melhore o palpite com base na média entre $y$ e $x/y$, i.e., $\\frac{(y + \\frac{x}{y})}{2}$\n",
    "\n",
    "**Passo4**: Usando este novo palpite, que novamente chamamos de $y$, repita o Passo2.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "|  `Palpite`  |  `Quociente`  |          `Média`        |\n",
    "|    :---:    |    :---:      |           :---:         |\n",
    "|     $1$     | $\\frac{2}{1} = 2$ | $\\frac{(2+1)}{2} = 1.5$ |\n",
    "|             |                   |                         |\n",
    "|    $1.5$    | $\\frac{2}{1.5} = 1.3333$ | $\\frac{(1.3333 + 1.5)}{2} = 1.4167$ |\n",
    "|             |                          |                                     |\n",
    "|   $1.4167$  | $\\frac{2}{1.4167} = 1.4118$ | $\\frac{(1.4167 + 1.4118)}{2} = 1.4142$ |\n",
    "|             |                             |                                        |\n",
    "|   $1.4142$  | ...           | ...       |"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Resumo\n",
    "\n",
    "Para solucionar o problema nós definimos:\n",
    "1. uma sequencia de etapas simples\n",
    "2. fluxo de processo de controle que especifica quando cada etapa é executada\n",
    "3. um meio de determinar quando parar\n",
    "\n",
    "1 + 2 + 3 = um algoritmo!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Linguagens de Programação"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Seria bom se pudéssemos abrir um telefone celular e dizer \"enviar uma mensagem\n",
    "para Alex, Katia e Erica para ver se eles querem vir para estudar cálculo\".\n",
    "Poderíamos então trabalhar com outra coisa enquanto o telefone compõe uma\n",
    "mensagem de texto, envia para os telefones de nossos amigos e negocia com os\n",
    "outros telefones para encontrar um momento em que todos desejam se encontrar.\n",
    "Esse tipo de interação não é possível com computadores atuais, mas\n",
    "pesquisadores em um campo conhecido como inteligência artificial estão tentando\n",
    "entender o que está envolvido nesses tipos de comunicação e desenvolver métodos\n",
    "computacionais para realizá-los. Hoje um assistente pessoal humano pode\n",
    "realizar esta tarefa, então este é um exemplo do tipo de problema que os\n",
    "humanos resolvem, mas os computadores (atualmente) não. É uma questão aberta se\n",
    "este problema está além dos limites da computação. Muito bem, pode ser possível\n",
    "que algum assistente pessoal digital no futuro realize essa tarefa."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "As descrições das etapas de um algoritmo em portugues ou em outra linguagem\n",
    "humana, como no algoritmo para calcular a raiz quadrada de um número inteiro\n",
    "positivo, é suficiente para falar sobre o algoritmo, para descrever o processo\n",
    "para outra pessoa ou para tentar entender se o algoritmo funciona ou não. Mas,\n",
    "para executar o algoritmo em um computador, as etapas devem ser descritas com\n",
    "mais precisão. Nesta descrição, as etapas devem ser simples o suficiente para\n",
    "serem \"entendidas\" por uma máquina. Uma maneira de pensar o que uma máquina é\n",
    "capaz de fazer é pensar em termos de símbolos, como números ou letras. As\n",
    "etapas em um algoritmo são basicamente configurações de símbolos, como\n",
    "operações aritméticas simples ou comparações que determinam quais as palavras\n",
    "que vêm antes de outros no alfabeto."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Cientistas da computação resolveram esse problema criando notações para\n",
    "expressar cálculos de forma exata e inequívoca. Essas notações especiais são\n",
    "chamadas de linguagens de programação. Toda estrutura em uma linguagem de\n",
    "programação tem uma forma precisa (sua sintaxe) e um significado preciso (sua\n",
    "semântica). Uma linguagem de programação é algo como um código para escrever as\n",
    "instruções que um computador seguirá. De fato, os programadores geralmente se\n",
    "referem a seus programas como código de computador, e o processo de escrever um\n",
    "algoritmo em uma linguagem de programação é chamado de codificação.  Python é\n",
    "um exemplo de uma linguagem de programação. É o idioma que usaremos neste\n",
    "curso. Vocês podem ter ouvido falar de outros idiomas, como C++, Java, Perl,\n",
    "Haskell ou PHP. Embora essas linguagens diferem em muitos detalhes, todas elas\n",
    "compartilham a propriedade de ter *sintaxe* e *semântica* bem definidas,\n",
    "inequívocas."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Expressando algoritmos em linguagens de programação\n",
    "\n",
    "- Uma linguagem de programação fornece um conjunto de operações primitivas.\n",
    "\n",
    " - Expressões são combinações legais de primitivas.\n",
    "\n",
    " - Expressões e cálculos têm valores e significados."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Exemplo do algoritmo \"Raiz Quadrada\" em Python"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "code_folding": [],
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def sqrt(x):\n",
    "    \"\"\" Calculate the square root of a positive integer \"\"\"\n",
    "\n",
    "    def average(y, x):\n",
    "        return (y + x) / 2\n",
    "\n",
    "    def improve(y, x):\n",
    "        return average(y, x / y)\n",
    "\n",
    "    def abs(x):\n",
    "        if x >= 0:\n",
    "            return x\n",
    "        else:\n",
    "            return -x\n",
    "\n",
    "    def good_enough(y, x):\n",
    "        return abs((y * y) - x) < 0.000001\n",
    "\n",
    "    def sqrt_iter(y, x):\n",
    "        if good_enough(y, x):\n",
    "            return y\n",
    "        else:\n",
    "            return sqrt_iter(improve(y, x), x)\n",
    "\n",
    "    return sqrt_iter(1.0, x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "sqrt(2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Programa de Estudos\n",
    "\n",
    "### Este curso irá abranger três aspectos principais da computação:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**Noções básicas de programação**: tipos de dados, estruturas de controle,\n",
    "desenvolvimento de algoritmos e design de programas com funções são idéias\n",
    "básicas que vocês precisarão dominar para resolver problemas com computadores.\n",
    "Este curso examinará estes tópicos fundamentais em detalhes e a parte prática\n",
    "permitirá sua compreensão deles para resolver uma ampla gama de problemas."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**Processamento de dados e informações**: os programas mais úteis dependem das\n",
    "estruturas de dados para resolver problemas. Essas estruturas de dados incluem\n",
    "seqüências imutáveis como tuplas e strings (cadeias de caracteres), sequencias mutáveis como listas, conjuntos e dicionários, e tipos abstratos de dados (ADT) como pilhas, filas e árvores. Neste curso vocês irão usar,\n",
    "construir e avaliar o desempenho das estruturas de dados. O conceito geral de\n",
    "um tipo de dados abstrato será introduzido, assim como a diferença entre\n",
    "abstração e implementação. Vocês irão aprender a usar a análise de complexidade\n",
    "para avaliar os custos de espaço/tempo de diferentes implementações de ADTs. \n",
    "Sem o bom entendimento da eficiência, é possível levar até os computadores mais\n",
    "rápidos a uma parada de execução ao trabalhar com grandes conjuntos de dados."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**Programação orientada a objetos (OOP)**: A programação orientada a objetos\n",
    "é o paradigma de programação dominante usado para desenvolver grandes sistemas de\n",
    "software. Se houver tempo suficiente, nós iremos introduzir ao final do curso os princípios fundamentais da OOP."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Porque aprender a programar (alguns exemplos)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "- Como engenheiro vocês deverão ser capazes de automatizar algum processo.\n",
    " - Vocês poderão criar programas para gerenciar e automatizar algum processo que hoje é manual.\n",
    "\n",
    "- Vocês deverão ser capazes de desenvolver novas ferramentas ou protótipos.\n",
    " - Para criar ferramentas/protótipos vocês deverão fazer simulações computacionais para fazer testes preliminares. \n",
    "\n",
    "- Vocês poderão enxergar situações onde uma solução computacional pode trazer benefícios.\n",
    " - Mesmo que vocês não implementem (programem) a solução vocês poderão propô-la e serem capazes de “conversar” com o pessoal de TI para implementar a solução."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "- Como cientistas vocês devem propor uma hipótese e testá-la.\n",
    " - Em vários casos onde os sistemas podem ser “modelados matematicamente”, são criados programas que fazem a simulação do sistema para checagem de uma hipótese.\n",
    "\n",
    "- Vocês deverão resolver sistemas complexos de equações que não necessariamente podem ser resolvidos por softwares padrões (como MatLab).\n",
    " - Vocês deverão implementar seus próprios resolvedores.\n",
    "\n",
    "- Simulações.\n",
    " - Muitos dos modelos propostos para explicar algum fenômeno são simulados computacionalmente. Implementar os modelos é uma tarefa básica."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## O que será necessário"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Vocês deverão ter acesso a um computador. Vocês vão precisar também ter acesso a uma aplicação chamada **\\textit{Terminal}**. Talvez seja a aplicação mais útil, porque vocês poderão usar o mesmo para dizer ao seu computador que faça praticamente tudo o que vocês quiserem. Usuários de Mac e Linux provavelmente estão familiarizados com este aplicativo. No Windows isso é um pouco mais complicado, já que a Microsoft é um tanto rebelde. Vocês podem instalar um emulador de terminal mais amigável do que o \"Prompt de Comando\" ou mesmo o \"PowerShell\"que acompanham o Windows. Eu sugiro instalar o Git Bash, a partir de https://git-scm.com/downloads. Durante a instalação, certifique-se de selecionar a opção \"Use Windows' default console window\". Uma outra opção, recomendado principalmente para quem quer iniciar no mundo Linux, é instalar o Shell Bash do Linux no Windows através do subsistema Windows para o Linux, presente nas versões mais atuais do Windows 10. [Aqui](http://www.techtudo.com.br/dicas-e-tutoriais/noticia/2016/04/como-instalar-e-usar-o-shell-bash-do-linux-no-windows-10.html) vocês encontraram um tutorial de como fazer isto."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Para criar um programa, utilizamos um **editor de texto** para escrever o código do programa (e.g.,\n",
    "[Vim](http://www.vim.org/), [Atom](https://atom.io/)) ou um IDE -- Ambiente de\n",
    "Desenvolvimento Integrado (e.g., [PyCharm](https://www.jetbrains.com/pycharm/),\n",
    "[WingIDE](http://wingware.com/)) e um **compilador/interpretador python**. O compilador é\n",
    "o que transforma o código em um programa executável.  O interpretador é um\n",
    "programa que executa diretamente os comandos da linguagem.  Será preciso\n",
    "instalar o compilador/interpretador python da versão 3.  Vocês poderão baixá-lo do site\n",
    "https://www.python.org/downloads/."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Jupyter Notebook\n",
    "\n",
    "Um dos avanços mais significativos na arena de computação científica está em\n",
    "andamento com a explosão de interesse na tecnologia [Jupyter Notebook](http://jupyter.org/). A publicação científica Nature apresentou recentemente um\n",
    "artigo sobre os benefícios dos notebooks Jupyter para pesquisas científicas.\n",
    "Jupyter Notebook nada mais é do que uma aplicação WEB de código aberto que permite\n",
    "criar e compartilhar documentos que contenham código, equações, visualizações e\n",
    "texto narrativo."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Depois de fazer o clone (recomendado) ou o download do caderno de aulas em uma pasta local, vocês precisarão instalar o Jupyter Notebook e algumas extensões para poder usar o material do curso. Com o Python3 já instalado na sua máquina, execute no terminal:\n",
    "\n",
    "- obs.: Se vc tem somente o python3 instalado em sua máquina, o comando `pip3` pode não existir. Neste caso, digite apenas `pip`."
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "$ pip3 install jupyter\n",
    "$ pip3 install jupyter_contrib_nbextensions\n",
    "$ pip3 install tutormagic\n",
    "$ jupyter contrib nbextension install --user"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Para usar as extensões necessárias, vocês também precisarão  ativá-las. Para fazer isso, vocês podem usar um subcomando Jupyter:"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "$ jupyter nbextension enable codefolding/main\n",
    "$ jupyter nbextension enable latex_envs/latex_envs\n",
    "$ jupyter nbextension enable python-markdown/main\n",
    "$ jupyter nbextension enable toc2/main"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Depois de instalar o Jupyter Notebook e as extensões em seu computador, vocês estão prontos para\n",
    "executar o servidor do notebook. Vocês podem iniciar o servidor do notebook a\n",
    "partir da linha de comando. Usando o aplicativo Terminal no Mac/Linux ou prompt de comando no Windows, vá par a pasta onde você baixou o caderno de aulas e execute:"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "$ jupyter notebook"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Isso imprimirá algumas informações sobre o servidor do notebook em seus\n",
    "terminais, incluindo a URL do aplicativo da Web (por padrão, http://localhost:8888), bem como a forma de encerrar o aplicativo:"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "$ jupyter notebook\n",
    "[I 10:31:03.540 NotebookApp] Serving notebooks from local directory: /Users/marcio/Unicamp/MC102/Python/lectures\n",
    "[I 10:31:03.541 NotebookApp] 0 active kernels\n",
    "[I 10:31:03.541 NotebookApp] The Jupyter Notebook is running at:\n",
    "[I 10:31:03.541 NotebookApp] http://localhost:8888/?token=046cfa3064f0b118f56f6ef8859c4ab68d1d202d79445759\n",
    "[I 10:31:03.541 NotebookApp] Use Control-C to stop this server and shut down all kernels (twice to skip confirmation)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Em seguida, jupyter abrirá seus navegadores da Web padrão para esta URL.\n",
    "Quando o notebook abrir nos seus navegadores, vocês verão o Notebook Dashboard, que\n",
    "mostrará uma lista dos cadernos, arquivos e subdiretórios no diretório onde o\n",
    "servidor do notebook foi iniciado. Na maioria das vezes, vocês desejarão iniciar um\n",
    "servidor de caderno no diretório que contém os cadernos do curso MC102. Muitas\n",
    "vezes, este será o seu diretório inicial."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Extras\n",
    "\n",
    "- Livro \"Practical Vim, second edition - Edit Text at the Speed of Thought\" [The Pragmatic Bookshelf](https://pragprog.com/book/dnvim2/practical-vim-second-edition)\n",
    "- Videos de Derek Wyatt sobre o editor Vim no Vimeo [Derek Wyatt](https://vimeo.com/user1690209)\n",
    "- Livro (online) sobre o editor Atom [Atom Flight Manual](http://flight-manual.atom.io/)\n",
    "- YouTube Video \"Setting up a Python Development Environment in Atom\" [Corey Schafer](https://www.youtube.com/watch?v=DjEuROpsvp4)\n",
    "- [Full Stack Python](http://www.fullstackpython.com) é um livro aberto que explica conceitos em linguagem simples e fornece recursos excelentes sobre esses tópicos."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Créditos\n",
    "\n",
    "Durante a elaboração deste caderno de lições, eu me beneficiei significamente de materiais disponíveis na web e, claro, procuro dar aqui os devidos créditos. Embora tenha tentado ser preciso e correto, se esqueci de alguma citação ou se infringi alguma falha de propriedade intelectual, eles são única e exclusivamente de minha responsabilidade, não tendo a Universidade de Campinas e o Instituto de Computação qualquer responsabilidade sobre o mesmo."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "- *Composing Programs*, John DeNero, UC Berkeley, Creative Commons Attribution-ShareAlike 3.0 Unported License.\n",
    "\n",
    "- *Introduction to Computation and Programming Using Python*, Ana Bell, Eric Grimson e John Guttag. MIT OpenCourseWare, Creative Commons License. \n",
    "\n",
    "- *Explorations in Computing - An Introduction to Computer Science and Python Programming*, John S. Conery, University of Oregon, Creative Commons License. \n",
    "\n",
    "- Livro *Think Python 2nd Edition*, Allen B. Downey, licença Creative Commons Atribuição-NãoComercial CC BY-NC 3.0.\n",
    "\n",
    "- Python 3 Official Documentation. (https://docs.python.org/3/). PFS license, GPL-compatible."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.0"
  },
  "latex_envs": {
   "LaTeX_envs_menu_present": true,
   "autoclose": false,
   "autocomplete": true,
   "bibliofile": "biblio.bib",
   "cite_by": "apalike",
   "current_citInitial": 1,
   "eqLabelWithNumbers": true,
   "eqNumInitial": 1,
   "hotkeys": {
    "equation": "Ctrl-E",
    "itemize": "Ctrl-I"
   },
   "labels_anchors": false,
   "latex_user_defs": false,
   "report_style_numbering": false,
   "user_envs_cfg": false
  },
  "livereveal": {
   "theme": "solarized",
   "transition": "slide"
  },
  "toc": {
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "toc_cell": true,
   "toc_position": {
    "height": "624px",
    "left": "0px",
    "right": "1068px",
    "top": "52px",
    "width": "212px"
   },
   "toc_section_display": "block",
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}