Semana 04 Pensamento Computacional

Prévia do material em texto

Semana 04 Pensamento Computacional
4 Raciocínio lógico, análise e resolução de problemas: estratégias de ordenação
Esta semana vamos tratar de tarefas importantes do nosso dia a dia ― tarefas de busca ― discutindo-as com base em conceitos do Pensamento Computacional. Também vamos utilizar um conceito novo para descrição dos algoritmos: diagramas de fluxo. Antes das estratégias adotadas em tarefas de busca, vamos lembrar como um programa acessa as posições de memória de nosso computador: uma de cada vez. Estudaremos tarefas de busca a partir da estratégia mais simples que podemos utilizar quando temos poucos itens a pesquisar: busca sequencial. A seguir, vamos discutir a estratégia que adotamos quando, dado um conjunto de itens, procuramos pelo maior ou o menor valor entre eles. E, por fim, vamos discutir como podemos reutilizar a estratégia que utilizamos quando procuramos palavras em um dicionário: a busca binária, e discutiremos o quanto essa estratégia é poderosa quando o número de itens é grande. Observamos que, para utilizar essa estratégia, os dados precisam estar ordenados. Utilizaremos programas interativos Scratch e programas escritos na linguagem Python, e discutiremos uma notação que sumariza o quão difícil é resolver os problemas associados.
Ao final desta semana você deverá ser capaz de:
Rotular e categorizar problemas de busca de acordo com as estratégias apresentadas;
Rotular e descrever os algoritmos de busca sequencial, busca pelo maior/menor, e busca binária, bem como suas ordens de complexidade;
Computar o número de comparações realizadas pelos algoritmos apresentados;
Descrever e construir o resultado de um conjunto de operações dos algoritmos estudados;
Contrastar a execução dos algoritmos para diferentes conjuntos de dados;
Nomear os elementos utilizados na apresentação de algoritmos via diagramas de blocos;
Descrever a tarefa de comparação em algoritmos de busca e em uma UCP (unidade central de processamento).
Desafio
Buscas, Buscas, Buscas
O nosso desafio desta semana é composto de duas tarefas. Uma tarefa é identificar atividades do nosso dia a dia nas quais utilizamos, ou poderíamos utilizar, as estratégias de busca sequencial busca pelo maior ou menor, e busca binária. A outra tarefa é ajudar alguém a observar quando está utilizando uma dessas estratégias e, se for o caso, quando deveria utilizar uma outra.
Revisitando Conhecimentos
Antes de iniciar os estudos desta semana, revisite os conhecimentos propostos nos materiais a seguir:
Material de apoio: Logaritmo binário | Wikipedia
Explicação sobre logaritmos na base 2.
Logaritmo binário
Na matemática, logaritmo binário (log2 n) é o logaritmo de base 2. Consequentemente, é o inverso da potência de dois (2n). O logaritmo binário de n é definido pela seguinte equivalência:[1]
O logaritmo binário está intimamente ligado ao sistema de numeração binário. Historicamente, seu primeiro uso foi na teoria musical pelo matemático e pioneiro no estudo dos logaritmos Leonhard Euler. Sua aplicação é muito vasta, sendo utilizado em teoria da informação (bit como unidade fundamental de informação), complexidade computacional e fotografia.
História
Leonhard Euler foi o primeiro a aplicar logaritmos binários à teoria musical, em 1739.
Potências de dois são conhecidas desde a antiguidade. Elas aparecem, por exemplo, em Os Elementos de Euclides, nas proposições IX.32 (sobre a fatorização das potências de dois) e IX.36 (metade do Teorema de Euclides-Euler, sobre a estrutura de números perfeitos pares). O logaritmo binário de uma potência de dois é apenas sua posição na sequência ordenada das potências de dois. Baseado nisto, Michael Stifel é reconhecido por ter publicado a primeira tabela de logaritmos binários em 1544. Seu livro Arithmetica Integra contém diversas tabelas que mostram os inteiros com suas respectivas potências de dois. Inverter as colunas dessas tabelas permite que elas sejam interpretadas como tabelas de logaritmos binários.[2][3]
Antes de Stifel, o matemático jainista Virasena é reconhecido como o precursor do logaritmo binário. Seu conceito de ardhacheda foi definido como o número de vezes que um certo número pode ser divido sem resto por dois. Essa definição cria uma função que coincide com o logaritmo binário em potências de dois,[4] porém é diferente para os outros inteiros, gerando a valorização 2-ádica ao invés do logaritmo.[5]
A forma moderna do logaritmo binário, aplicável a qualquer número (não apenas potências de dois) foi considerada explicitamente por Leonhard Euler em 1739. Euler estabeleceu a aplicação de logaritmos binários à teoria musical, antes de aplicações mais significativas em teoria da informação e ciência da computação serem conhecidas. Como parte de seu trabalho na área, Euler publicou uma tabela dos logaritmos binários de 1 a 8, com sete dígitos de precisão.[6][7]
Definição e Propriedades
A função logartimo binário pode ser definida como a função inversa à função potência de dois, que é estritamente crescente nos números reais positivos, assim possuindo uma inversa única.[8] Alternativamente, pode ser definida como ln n/ln 2, sendo ln o logaritmo natural definido de forma usual. Usar o logaritmo complexo nessa definição permite estender o logaritmo binário aos números complexos.[9]
Assim como os demais logaritmos, o logaritmo binário obedece às seguintes equações, que podem ser utilizadas para simplificar fórmulas que combinam logaritmos binários com multiplicação ou exponenciação:[10]
{\displaystyle \log _{2}xy=\log _{2}x+\log _{2}y}
{\displaystyle \log _{2}x^{y}=y\log _{2}x.}Outras identidades podem ser encontradas em Identidades logarítmicas.
Notação
Na matemática, o logaritmo binário de um número é frequentemente escrito como log2 n.[11] No entanto, outras notações para essa função já foram propostas e utilizadas, especialmente em áreas aplicadas.
Alguns autores adotam a notação lg n para o logaritmo,[12] utilizada, por exemplo, no The Chicago Manual of Style. Donald Knuth atribui essa notação a uma sugestão de Edward Reingold, porém seu uso em teoria da informação e ciência da computação antecede o período de atividade de Reingold. Outra notação utilizada para a mesma função é ld n, principalmente na literatura científica alemã, cuja origem é o termo em latim logarithmus dualis.
Aplicações
Teoria da informação
O número de dígitos (bits) na representação binária de um inteiro positivo n é a parte inteira de 1 + log2  n, ou seja,[12]
{\displaystyle \lfloor \log _{2}n\rfloor +1.}
Material de apoio: Função polinomial | Wikipedia
Funções polinomiais de grau um, de grau dois e de outros graus.
Material de apoio: Fluxograma | Wikipedia
Explicação ilustrada sobre fluxogramas
Fluxograma: é um tipo de diagrama, e pode ser entendido como uma representação esquemática de um processo ou algoritmo, muitas vezes feito através de gráficos que ilustram de forma descomplicada a transição de informações entre os elementos que o compõem, ou seja, é a sequência operacional do desenvolvimento de um processo, o qual caracteriza: o trabalho que está sendo realizado, o tempo necessário para sua realização, a distância percorrida pelos documentos, quem está realizando o trabalho e como ele flui entre os participantes deste processo.
Os fluxogramas são muito utilizados em projetos de software para representar a lógica interna dos programas, mas podem também ser usados para desenhar processos de negócio e o workflow que envolve diversos atores corporativos no exercício de suas atribuições.[1]
O diagrama de fluxo de dados (DFD) utiliza do fluxograma para modelagem e documentação de sistemas computacionais.
O termo fluxograma designa uma representação gráfica de um determinado processo ou fluxo de trabalho, efetuado geralmente com recurso a figuras geométricas normalizadas e as setas unindo essas figuras geométricas. Através desta representação gráfica é possível compreender de forma rápida e fácil a transição de informações ou documentos entre os elementos que participam no processo emcausa.
O fluxograma pode ser definido também como o gráfico em que se representa o percurso ou caminho percorrido por certo elemento (por exemplo, um determinado documento), através dos vários departamentos da organização, bem como o tratamento que cada um vai lhe dando.
A existência de fluxogramas para cada um dos processos é fundamental para a simplificação e racionalização do trabalho, permitindo a compreensão e posterior otimização dos processos desenvolvidos em cada departamento ou área da organização.
O que é um fluxograma?
O primeiro método estruturado para o fluxo de um processo, o fluxograma, foi introduzido por Frank Gilberth aos membros da American Society of Mechanical Engineers (ASME) em 1921 durante a apresentação intitulada “Process Charts – First Steps in Finding the One Best Way”. Após sua apresentação, a ferramenta passou a fazer parte do currículo do curso de engenharia industrial. No início dos anos 30, um engenheiro industrial chamado Allan H. Mogensen começou a capacitar alguns homens de negócio a utilizarem esta ferramenta.
Em 1944, um aluno de Mogenses, Art Spinager levou esta ferramenta para a Procter Gamble, difundindo seu uso em um dos seus programas de melhoria. Outro aluno, Bem S. Graham, diretor de Formcraft Engenharia, adaptou o fluxograma para que ele também informasse o fluxo de informação, desenvolvendo um fluxograma multi-fluxo, mostrando os vários documentos utilizados ao longo do processo e suas interações. Em 1947, a ASME adotou um conjunto de símbolos derivados do trabalho do Gilberth.
Já no universo dos programas de computadores, onde ficaram tão famosos, os fluxogramas chegaram em 1947. Goldstein e von Neumann utilizaram vários fluxogramas de programação em seu trabalho “Planning and coding of problems for an electronic computing instrument, Part II, Volume 1”. Foi no campo dos algoritmos de computadores que os fluxogramas atingiram seu apogeu.[2]
Como os fluxogramas vieram para melhoria de processos?
Para melhorarmos bastante os processos em nossas empresas, precisamos entender como ele funciona e se comporta atualmente. Precisamos também, compreender o fluxo do processo e como as etapas se relacionam entre si. Um método importante para realizar esta tarefa é o mapeamento de processo.
Porém, na década de 70 os fluxogramas começaram a perder sua popularidade, quando os terminais de computação interativos e as linguagens de programação de terceira geração começaram a substituir os fluxogramas. Por meio do código fonte nestas linguagens era possível expressar os algoritmos de maneira muito mais clara e concisa do que utilizando-se os fluxogramas. Expressar o algoritmo no próprio código-fonte permitia a equipe trabalhar separadamente, pois não havia mais erros de “tradução” do fluxograma para a linguagem de programação.
Apesar de terem sua popularidade diminuída no campo da computação, o fluxograma é ainda uma das melhores ferramentas para se mapear e medir um processo. O fluxograma é uma das ferramentas básicas de melhoria que fornece uma imagem visual de um processo que está sendo estudado. Esta imagem é feita por meio de uma representação gráfica de uma série de atividades que definem o processo e a sequência entre elas. Com a popularização das técnicas de melhoria de processos, como TQM, Lean e Six Sigma, e com a difusão das normas ISO de padronização de processos, o fluxograma continua mais atual que nunca.
O mapeamento de processo por meio do fluxograma é uma importante estratégia de diagnóstico para projetos de melhoria. Um bom fluxograma é fundamental para que a equipe consiga compreender como o processo funciona atualmente.[2]
Tipos de fluxogramação
De acordo com Chiavenato (2010), existem pelo menos, 3 tipos de fluxogramação[3]: Fluxograma Vertical (ou Fluxograma padrão ASME), Fluxograma Horizontal (ou Fluxograma Padrão ANSI), e Fluxograma de blocos
Fluxograma padrão ASME
Um exemplo de Fluxograma padrão ASME.
O fluxograma padrão ASME (American Society of Mechanical Engineers), mais conhecido como Fluxograma Vertical ou ainda como diagrama de processo, foi o primeiro método estruturado para documentar o fluxo do processo. Em 1947, a ASME adotou um conjunto de símbolos derivado do trabalho original de Gilbreth como o "Padrão ASME: Gráficos de Processo de Operação e Fluxo". Eles podem ser encontrados em um relatório não publicado, intitulado "Planejamento e codificação de problemas para um instrumento de computação eletrônica, Parte II, Volume 1" (1947), que é reproduzido nas obras completas de John von Neumann.
Esse fluxograma é composto por colunas verticais onde estão disponíveis simbologias referentes aos tipos de processo, descrição e outras informações.
Fluxograma padrão ANSI
O Fluxograma funcional, também chamados de Fluxograma Padrão ANSI (American National Standards Insitute), é o mais conhecido deles. Ele teve seus padrões e símbolos establecidos na década de 1960.[4] A Organização Internacional para Padronização (ISO) adotou os símbolos ANSI em 1970.[5] O padrão atual, ISO 5807, foi revisado em 1985.[6] Geralmente, fluxogramas fluem de cima para baixo e da esquerda para a direita.[7]
Fluxograma de blocos
O Fluxograma de blocos possui um design não tabulado. Ele é usado com o objetivo de representar a sequência de atividades por meio de blocos encadeados entre si. É normalmente utilizado para estudos analíticos dos processos.[3]
Material de apoio: Logaritmo | Robson Luiz (Brasil Escola)
Definições e operações de logaritmos
Logaritmo é a operação inversa da exponencial utilizada para o cálculo de equações exponenciais que não possuem soluções imediatas.
"Logaritmo é uma ferramenta muito importante não somente para a área da matemática, pois possui aplicação em diversos campos da ciência, como na geografia, química e computação.
Historicamente o logaritmo surge a fim de facilitar contas que apareciam com frequência em diversas áreas cientificas. John Napier foi pioneiro nos estudos sobre logaritmos, e conseguiu desenvolver a operação capaz de transformar produtos em soma, divisões em subtrações e potências em multiplicações.
Definindo essa operação, com o tempo, outros matemáticos formalizaram definições e propriedades, além disso, foi desenvolvida também a conhecida tábua de logaritmos."
"Definição do logaritmo
Esboço do gráfico da função logaritmo (à direita) e sua inversa exponencial (à esquerda).
Considere dois números reais positivos a e b, com a ≠ 0. O logaritmo de b na base a é o número x se, e somente se, a elevado a x for igual ao número b."
Ciência da Computação, 4ª edição
Nell Dale; John Lewis
Estudo Dirigido de Algoritmos
Perguntas
PERGUNTA 1
1. Assim como a CPU só acessa uma posição de memória de cada vez, o algoritmo de busca sequencial também acessa um a um os elementos disponíveis e, a cada acesso, compara o valor do elemento acessado com o elemento a ser buscado (este último também chamado de chave de busca). O diagrama de fluxo do algoritmo de busca sequencial está ilustrado na figura.
Escolha a alternativa que completa, correta e respectivamente de cima para baixo, as lacunas.
	
	
	primeiro; último; próximo elemento
Pergunta 2
	
	
	
	Nesta aula discutimos o algoritmo de busca pelo maior elemento de uma lista. O diagrama de fluxo do algoritmo está ilustrado na figura.
	
	
	
	
	
	
	
	
	
Escolha a alternativa que completa, correta e respectivamente de cima para baixo, as lacunas.
Resposta primeiro, primeiro, último, próximo, maior
PERGUNTA 3
1. Nesta aula discutimos o algoritmo de busca binária. O diagrama de fluxo do algoritmo está ilustrado na figura.
Escolha a alternativa que completa, correta e respectivamente, de acordo com a numeração, as lacunas.
	
	
	esq; dir; esq; dir
PERGUNTA 4
Os autores Mueller e Massaron (2018) discutem, na seção “Avaliando Algoritmos” (páginas 38-44),a necessidade de se avaliar algoritmos de forma abstrata e independente da capacidade de hardware e software de dispositivos. Nessa oportunidade, eles também explicam como fazemos para utilizar funções matemáticas para abstrair o tempo de execução de um algoritmo com base no tamanho de itens da entrada que devem ser processados. Um exemplo seria quantos elementos precisamos analisar para identificar qual o item de maior valor em um conjunto de itens fornecido para o algoritmo.
Analise as afirmações abaixo para escolher a alternativa que completa, correta e respectivamente, as lacunas:
I. Análise de Algoritmos é o ramo da ciência da computação dedicado a entender como os algoritmos funcionam de modo formal.
II. Quanto mais operações um algoritmo necessita, mais complexo ele é.
III. Considerar o tamanho da entrada de dados faz sentido considerando que a vida das pessoas está abarrotada com uma grande quantidade de dados.
IV. A análise de algoritmos é realmente um conceito maravilhoso, pois reduz uma complexa série de passos a uma fórmula matemática.
V. Normalmente uma análise de algoritmos não está interessada em definir exatamente a função correspondente ao algoritmo.
VI. Normalmente o objetivo da análise de um algoritmo é comparar a função do algoritmo analisado com outra função geral já conhecida.
VII. O conjunto de funções gerais é chamado notação Big O.
VIII. As cinco primeiras funções gerais, em ordem crescente de complexidade, são: O(1), O(log n), O(n), O(nlogn) e O(n2).
		
a. formal, mais complexo, faz, reduz, não está, já, gerais, crescente.
PERGUNTA 5
1. Diagramas de blocos utilizam uma notação aceita internacionalmente e documentada por agências de padronização internacionais. Os editores de slides que utilizamos em nosso dia a dia oferecem os blocos prontos para nosso uso, como ilustrado na figura.
Considerando os elementos da figura que estão indicados pelas letras de A a F, escolha a alternativa que completa, correta e respectivamente, as lacunas das afirmações a seguir:
I. Blocos como o apontado pela letra A indicam entrada de dados para o algoritmo.
II. Blocos como o apontado pela letra B execução de instruções indicam pelo algoritmo.
III. Blocos como o apontado pela letra C indicam a execução de uma entre duas sequências de comandos pelo algoritmo.
IV. Blocos como o apontado pela letra D indicam os resultados produzidos pelo algoritmo.
V. Blocos como o apontado pela letra E indicam o término do algoritmo.
VI. Desvios como o apontado pela letra F indicam a repetição de uma sequência de comandos pelo algoritmo.
	
	
	entrada de dados; execução de instruções; a execução de uma entre duas sequências; os resultados produzidos; o término; a repetição de uma sequência de comandos
PERGUNTA 6
1. A figura a seguir ilustra a execução de três iterações do algoritmo de busca binária para buscar a chave de valor 70 em uma lista contendo 13 elementos. Aplique seu conhecimento sobre o algoritmo de busca binária construir a próxima iteração.
	
	
	meio: 3 contém: 60
PERGUNTA 7
1. O termo “CPU” que utilizamos no dia a dia corresponde ao termo em inglês Central Processing Unit (CPU), que, em português, equivale a Unidade Central de Processamento (UCP). Entre os principais componentes da CPU estão a Unidade de Controle, a Unidade Lógica e Aritmética (ULA), e o Caminho de Dados (em inglês, Datapath). É pelo Caminho de Dados que são transferidos, da memória para a CPU, as instruções dos programas e os dados manipulados pelo programa.
Toda tarefa de busca implica a comparação de valores: o valor da chave buscada é comparado com os valores armazenados em posições de memória nas quais a chave pode estar.
A partir da sua análise, aplique os conceitos estudados para avaliar as afirmações relativamente a tarefas que demandam a comparação de valores utilizadas por algoritmos de busca.
I. Internamente, uma CPU compara dois valores de cada vez.
II. Internamente, uma CPU acessa um valor de memória de cada vez.
III. Para comparar dois valores que estão na memória, a CPU tem que transferir os dois valores da memória para a ULA.
IV. Para transferir dois valores que estão na memória para a ULA, a CPU transfere um valor de cada vez.
V. A transferência de valores entre memória e ULA utiliza o Caminho de Dados da CPU.
	
	
	Todas são verdadeiras.
PERGUNTA 8
1. A figura a seguir ilustra a execução de três iterações do algoritmo de busca binária para buscar a chave de valor 3 em uma lista contendo 17 elementos. Aplique seu conhecimento sobre o algoritmo de busca binária construir a próxima interação.
	
	
	meio: 0 contém: 3
PERGUNTA 9
1. Considere o algoritmo de busca binária executado em uma lista de tamanho n > 4, n ímpar.
A partir da sua análise, aplique os conceitos estudados para avaliar as afirmações.
I. Se a chave estiver na primeira posição da lista, o algoritmo realiza mais que uma comparação com o valor da chave.
II. Se a chave estiver no meio da lista, o algoritmo realiza 1 comparação com o valor da chave.
III. O maior número de comparações é realizado quando a chave estiver ou na primeira ou na última posição da lista, ou quando a chave não estiver presente na lista.
IV. A cada comparação realizada pelo algoritmo, metade da lista restante é descartada, o que significa que a chave será encontrada, ou identificada como ausente, em log2n comparações.
	
	
	Todas são verdadeiras.
PERGUNTA 10
1. Aplique seu conhecimento sobre os algoritmos de busca sequencial e busca binária para as seguintes asserções e a relação proposta entre elas.
I. O algoritmo de busca binária possui exigências não apresentadas pelo algoritmo de busca sequencial.
PORQUE
1. O algoritmo de busca binária é executado em uma lista previamente ordenada.
	
	
	As asserções I e II são proposições verdadeiras, e a II é uma justificativa da I.
PERGUNTA 11
1. Considere um algoritmo de busca pelo maior ou pelo menor elemento contido em uma lista de tamanho n >= 4.
A partir da sua análise, aplique os conceitos estudados para avaliar as afirmações.
I. Podemos utilizar uma mesma execução do algoritmo para identificar o maior e o menor valor.
II. Para identificar o maior valor, o algoritmo tem que realizar comparações, elemento a elemento, do primeiro até o último.
III. Para identificar o menor valor, o algoritmo tem que realizar comparações, elemento a elemento, do primeiro até o último.
IV. Como o algoritmo realiza comparações com todos os elementos da lista, dizemos que ele é da ordem de O(n).
	
	
	Todas são verdadeiras.
	
	
	
PERGUNTA 12
1. Considere o algoritmo de busca sequencial executado em uma lista de tamanho n >= 4.
A partir da sua análise, aplique os conceitos estudados para avaliar as afirmações:
I. Se a chave estiver na primeira posição da lista, o algoritmo realiza uma comparação com o valor da chave.
II. Se a chave estiver na última posição da lista, o algoritmo realiza n comparações com o valor da chave.
III. Se a chave estiver no meio da lista, ele realiza n/2 comparações com o valor da chave.
IV. Quando um algoritmo realiza n comparações no pior caso, dizemos que ele é da ordem de O(n).
	
	
	Todas são verdadeiras.