Algoritmos e Estrutura de Dados 2 - UFPR - Algoritmos 2 - Problemas Computacionais e Algoritmos (3/4)

anteriormente nós estávamos comentando sobre as definições das problemas computacionais, então defini bem entrada, defini bem a saída, defini de forma forma, entra de saída e de maneira matemática. Bom, isso pode ser até um desafio aí e há alguns problemas que eles nem são bem definidos, então quero apresentar alguns desses problemas só para a gente ter uma ideia de que eu estou falando de problemas mal definidos. Então alguns problemas podem ser inicialmente, às vezes é só no início, inicialmente mal definidos. Então, um problema que a gente trabalha lá em Alguewon é só para mostrar essa questão de problemas que não são bem definidos, é assim, quero ler vários pares de números e imprimir a soma de cada par, só que o que são vários pares?

Então, lá em Alguewon, a gente pega essa coisa que não está bem definida aqui, vários pares, a gente trabalha com duas hipóteses lá, né, vários pares, às vezes significa ler n números ou os vários pares, às vezes significa ler diversos números de par, de ler números, quando você vê, lá, zero zero, né, que são dois, o par, por exemplo, dois números, tem os zero zero. Então, se poderia começar a dar interpretações mais precisas para quando os problemas são mal definidos, então a solução é definir precisamente o teu problema. Então, como eu comentei aqui, uma primeira interpretação seria ler pares de números, tem que encontrar dois zeros e uma segunda interpretação é ler 100 pares de números ou n números, os usuários de gitan, certo, número n e você vai ler que eles n pares de números bem entrada, tá? Então, dá para você pegar uma coisa que está mal definida e definir de maneira bem precisa.

Outro problema que a gente trabalha lá em Alguewon, também ele é mal definido, é o problema de detectar bordas da imagem. Então, essa aplicação era uma aplicação que eu gostava bastante lá em Alguewon, detectar bordas de imagem. A questão é o que é uma borda? A gente vai ler a posição do que seria uma borda, mas se eu pegar a falasse em tradusa e traduz essa intuição do que significa ser borda, tradusa para uma linguagem mais matemática, uma linguagem mais precisa ou tradusa para um algoritmo.

E a gente faz isso de uma maneira bem precisa lá em Alguewon, só que existem diversas formas de você fazer. Então, lá em Alguewon, a gente trabalha com o método do gradiente, mas existem outros métodos aqui, por exemplo, métodissobre, métodis preuit, métodicanny, o que são esses métodos aqui? São formas de você pegar essa definição que precisa de borda e falar assim, pronto, borda é isso, o borda é aquilo. Então, no momento em que você fala que você está trabalhando com o método do gradiente, você está falando assim, bordas são gradientes, que é um conceito lá que a gente acaba vendo lá no cálculo 2.

O método de sobeu, aí você tem uma outra definição, precisa do que que é uma borda. Um outro problema mal definido, problema de detectar com muridades em redes sociais, são problemas eu costumo dar, e vezes, enquanto em disciplina de redes sociais, e é uma disciplinutativa aí para os cursos de ciência, da computação e formática biomédica. A questão assim, a gente gostaria de pegar essas que a gente chama de grafo aqui da conexão, que representa conexões em redes sociais, por exemplo, os pontos aqui seriam pessoas e a conexão, e os pontos seriam, essas pessoas têm amizades. A gente gostaria de pegar esse grafo aqui, de conexões, e fazer esses clustering, esses agrupamentos de pessoas aqui, igual a essas coisas.

O problema é definir o que é uma comunidade, o que é uma comunidade. Então, da mesma forma, a gente tem que pegar essa definição informal e transformar numa definição precisa, para aí você resolveu o problema. Então, você tem vários métodos lá, método do corte mínimo, método de agrupamento de hierarquico, algoritmo de girvanilman, maximização de modularidade, baseado em cliques, e diversos outros. Não vou comentar sobre isso daqui.

Cada um deles tem, assim, vão dizer vantagens e desvantagens. Agora, quem define, quem escolhe qual é a definição precisa e qual é a melhor definição precisa? Isso é também uma outra questão. Talvez saem um pouco do que a gente está...

Na verdade, isso sai do que a gente vai discutir em algo 2, mas só para vocês saberem, porque é uma questão que vocês eventualmente vão ter que trabalhar, vão ter que discutir isso aí, né? Lá, nessa área de redes sociais mesmo, não vou ser trabalha com... É uma área que você trabalha ali com redes sociais. Então, sociais, sociologia, tá?

Então, você vê o que pessoas sociólogos entendem por comunidade, tá? Para daí você criar uma definição matemática do que significa ser uma comunidade, tá? Ou até mesmo questões da psicologia, às vezes, entre aí nas redes sociais. Então, você tem aí essa interação, né?

Você não fica só na área de ciências exatas, você trabalha com essa área de ciências humanas, e por isso que elas são áreas bastante importantes também, tá? Então, sociologia, psicologia e outras aí, tá? Então, tem esse estúdio aí, mas a gente não trabalha nesse nível, a gente trabalha assim com um definições já dadas, né? Pelo menos da maioria dos casos, às vezes a gente tem que fazer esse trabalho aí também.

Então, alguns casos de problemas mal definidos são ainda mais problemáticos, né? Como assim? É... Porque até então, esses problemas que eu acabei de falar para vocês aí, eu consigo pegar e criar definições precisas, tá?

E alguns outros problemas você quer criar um algoritmo que faz uma determinada coisa, mas você não consegue definir o que são aquelas coisas, tá? Então, um problema assim é pacificar uma imagem como o Cão O Gato, esse problema lá da área de aprendizado de máquina, tá? Você quer, eu te dou duas imagens aqui, um gato e um cachorro, tá? Os difícils você for olhar aqui, não, essas duas imagens aqui, você vai pensar por mais esse gato aqui, talvez parece um gato, mas pode ser um outro bicho aí, tá?

Esse cachorro aqui tá até com uma cara do Murcinho, né? Como você faz para definir isso? Forma um mente e fazer o teu programa identificar o que é gato e o que é cachorro, e os algoritmos fazem isso hoje, tá? Os algoritmos lá da aprendizado de máquina.

Então assim, a solução aqui, uma solução entre aspas, tá? É fazer definições precisas entre aspas, elas não são tão precisas, e aí você acaba trabalhando com assim, o que é um... o que é um Cão e Gato? Ah, é o que é definido por uma rede neural, né?

Uma definição baseada numa outra definição, né? Uma rede neural, tá? O que é Cão e Gato? Ah, o que é Cão e o que é Gato?

É o que classificadores lineares me dizem o que é Cão e Gato. Então, de certa forma você tá meio que desviando do problema, né? Você... Você atribui a definição de Cão e Gato para o classificadores lineares.

A grande questão aqui, por isso que ela é mais problemática, ainda, é que ainda ninguém sabe exatamente por que que uma rede neural funciona, por que que um classificador linear funciona? É uma área de pesquisa, tá? Então você... Você sabe que funciona, tem o funcionado bem, mas você não sabe exatamente por quê?

Então você... A tribuia definição de Cão e essas soluções que são precisas, tá? Só que você não sabe o que acontece lá dentro direito, tá? Pessoal, tem estudados, daí é uma área bem...

bem ativa aí da computação hoje em dia, tá? Então assim, só para... Estudo aqui é só para mostrar que tem problemas que são mal definidos, mas não nós... Na nossa forma de ver aqui em algoritmos 2, a gente vai defin...

A gente sempre vai ver que precisa, tá? Problemas bem definidos, ó? Então, ó, um exemplo de problema que nós vamos tratar aqui, a gente até já viu antes, tá? Então, tá aqui a entrada e a saída instância resposta, então aqui é a instância.

VAB, são três coisas, tá? É uma tripla que a gente chama, né? VAB, onde V é um vetor indexado por A e B, e UAB tem que ser menor e igual do que B, tá? Isso vai receber três coisas como entrada, você pode pensar lá já na entrada das funções, né?

Vai receber um vetor, você vai receber um INCAB e um INCB, e a gente já tá supondo que o INCAB é menor e igual do que o INCB, tá? Isso é nossa entrada, e a nossa saída, o INCM, entre A e B, tal que o valor na posição de E, é menor e igual que todas as outras... O valor de todas as outras posições, tá? Então, a gente chamou esse problema, agora, um problema bem definido e de problema de mínimo de vetor.

É um problema que a gente já trabalhou na A1 também, ó? Mas a gente não tinha assim, chamado tanta atenção para essa questão da entrada e da saída, a instância da resposta. Então, só para exemplificar aqui, tá? Aí, agora, o problema do mínimo do vetor, né?

Se o vetor que eu passo como entrada é dado por esse vetor aqui, vai então aqui tem os índices de 1 até 7, e o valor de cada posição, 16, 23, 4, 42, 15, 84, sobre 1 ponto de vírgula aqui. Então, primeira coisa, V1 7 é uma instância do problema mínimo do vetor, é uma entrada do problema do mínimo do vetor. Então, o que é a entrada? É o vetor?

Qual o vetor? Esse vetor aqui, 1 e 7, por que? Essa é a tripla, a gente vai receber três coisas, como eu falei, o vetor, o índice inicial e o índice final, tá? V1 7 é a entrada do nosso problema.

Que mais? 3 é uma resposta para a entrada V1 7, né? Porque 3, que na posição 3, lembra que a gente retorna as posições, os índices M, então, por que que 3 é a resposta? Porque na posição 3 contém o número 4, e o número 4 é menor, igual a todas as outras posições do vetor.

Terceiro ponto aqui, 7 é outra resposta para a instância V1 7, então, nesse problema aqui, eu posso ter aquele duas respostas possíveis, pode ser 3 ou pode ser 7, porque na posição 7 o número 4 é menor, igual a todos os 18 números do vetor. 4 ponto V4 6 é outra instância ou outra entrada do problema, tá? É outra entrada, 1 é V1 7, e quando eu mudo aqui os parâmetros da entrada, tem outra entrada, né? O V4 6 seria, eu posso até passar esse vetor inteiro aqui, mas o 4 6 eu estou me restringindo a essa parte aqui.

O que a gente quer fazer isso? Porque a gente quer deixar genera e com as índices do vetor, não necessariamente a gente sempre precisa começar em 1, terminar no número máximo, a gente pode pegar subvetores, a gente torna até o problema, a entrada mais genérica. E aí, nesse caso, o 6 é a única resposta para a instância V4 6, como eu falei, V4 6 é esse vetor, mas restrito aqui a posição 4 5 6. E aí se restringindo a esse subvetor, a única resposta é 6, porque o valor da posição 6 é 8, e 8 é menor igual que todos esses números aqui, da posição 4 até a posição 6.

Isso daqui só para a gente entender que estão de entrada e saída, instância e resposta. Beleza, onde é que entre nos algoritmos aí nessa discussão toda? Então, a gente falou de problemas computacionais agora, então, quando o computacional é definido por entrada e saída, a solução de um problema computacional é chamado de algoritmo. Então, o algoritmo é, primeiro, a descrição, dei uma computação, né, ou de um passo a passo.

Dá para a gente definir essas coisas aqui de maneira mais formal. E para cada instância do problema, para cada entrada possível do problema, resulta em uma resposta correta com aquele problema. Então, do jeito que a gente está trabalhando aqui, está qualquer tipo de entrada que o passo é o problema, se eu tenho um algoritmo, ou seja, se eu tenho uma solução para esse problema, ele tem que me devolver a resposta correta, para qualquer entrada. Só assim que eu posso considerar que é uma solução, se ele responde uma vez errado, ele já não é uma solução para o problema.

Bom, e como descrever uma computação, como é que a gente costuma descrever um passo a passo, a gente já fez isso no algoritmo Zoom, né, a gente descreve o passo a passo, por exemplo, usando o linguagem Pascal, linguagem de programação Pascal, e a gente descreveu o passo a passo, ou poderia ser outro linguagem de programação. Como é que a gente vai descrever os algoritmos aqui em algoritmos 2, a gente vai usar a descrição chamada de pseudo código, a gente não vai descrever as soluções nem Pascal, nem C, nem nenhuma outra linguagem, a gente vai descrever usando pseudo código. Talvez mais, bom, tem a próxima aula, eu vou apresentar alguns trechinhos de linguagem C, pode ser que mais para frente também a gente representa outros trechos de linguagem, de outras linguagens, aí o mesmo linguagem C, mas a ideia geral aqui é apresentar os algoritmos usando pseudo código. O que é um pseudo código?

Seu do código é assim, parece código, mas não é, por isso a palavra pseudo parece, mas não é. Por que é legal a gente descrever os algoritmos usando pseudo código? Porque é mais simples, como assim mais simples? Por exemplo, ele omite alguns detalhes específicos que são feitos só para o computador entender.

Por exemplo, você lá no pseudo código você não declara variáveis, mas você precisa declarar isso para o computador entender que você está reservando um espaço de memória, então a gente não precisa entrar nesse tipo de questão. Outros detalhes específicos que é só feito para o computador entender, por exemplo, usar ponti vírgula. O ponti vírgula é assim, terminou aqui uma certa sentença, certo comando, e aí o computador que está lendo aqui sabe que terminou. Então são os delimitadores.

A gente também evita isso no pseudo código, então a coisa fica um pouco mais limpa e mais simples. Outro tipo de delimitador, você lhe lá o beguinho, o Índido do Pascal. Também não precisamos desse tipo de coisa aqui. Isso é feito só para o computador entender.

Então é mais simples usar o pseudo código. Um outro fator aqui é que a maioria dos livros delgurítimos usa pseudo código para fazer a descrição dos algoritmos. Grande maioria dos livros usa pseudo código. Porque é uma forma mais genérica, não?

Você não está atrelando a uma tecnologia específica. Quando eu digo tecnologia é uma certa linguagem específica, ou pastel, ou Java, ou C ou Python. Não, pseudo código todo mundo vai leito, todo mundo vai entender. E aí você não vai ter que se preocupar com alguns detalhes, daria da linguagem, sendo que às vezes você nem conhece a linguagem.

Então não te confundi muito. Então a grande maioria dos livros usa pseudo código. Porém, porém, a última coisa aqui é que quando vocês forem implementar, vocês vão usar a linguagem C. A linguagem C, aí, posso dizer que é quase como se fosse a linguagem oficial aí dos cursos de C está computação e informática biomédica.

A gente aprende lá no primeiro semércio Pascal justamente para a gente abandonar ela e saber que existem outras linguagens que são muito parecidas. Mas aí a gente acaba ficando aí muitas vezes na linguagem C. Não é objetivo dessa disciplina, aqui explica a linguagem C como falei. A gente vai descrever as coisas em pseudo código.

A linguagem C vocês vão aprender lá na disciplina de programação 1. Mas quando vocês forem implementar, implementar as soluções que vocês envolveriam aqui, vocês vão ter que usar a linguagem C ou implementar os trabalhos práticos que a gente for foram dados aí nessa disciplina delgurite nos dois. Então, por aí você tem que... aí você não pode desapiseu do código.

Tem que usar uma linguagem real de que você vai usar a linguagem C.