Loading
Nota de Estudos
Study Reminders
Support
Text Version

Problemas Simplificados & Soluções

Set your study reminders

We will email you at these times to remind you to study.
  • Monday

    -

    7am

    +

    Tuesday

    -

    7am

    +

    Wednesday

    -

    7am

    +

    Thursday

    -

    7am

    +

    Friday

    -

    7am

    +

    Saturday

    -

    7am

    +

    Sunday

    -

    7am

    +

Olá lá, bem-vindo à segunda sessão da sua primeira semana. O que faremos nesta sessão épara revisitar o problema simplificado, rever a solução novamente e principalmente oferecer argumentos sobre a correção. É isso que vamos ver principalmente nesta sessão. Veremos também uma implementaçãoparticularmente com base em planilhas. Examinaremos as generalizações do problema e discutiremosas estruturas de dados e o processamento envolvido.
(Consulte O Tempo De Deslizamento: 00:51)

O professor Sane discutiu a versão simplificada desse problema em que dois e trêscolegas de quarto foram considerados. Agora, generalizaremos a um número arbitrário de colegas de quarto. Nósusaremos a seguinte notação:• Vamos denotar o número de roommates por NRoomMate.• KEvents irá denotar o evento.• Cada evento será denotado por um EventId.• Algum colega de quarto será denotado por um RoomMateId.
(Consulte O Tempo De Deslizamento: 01:30)
No final do mês, representaremos um evento por linhas e cada roommate por uma coluna.Portanto, no final do mês, teremos um conjunto de linhas denotando os diversos eventos que tiveramcompartilhados pelos colegas de quarto. E ao longo de cada coluna será a despesa ou o dinheiro que temfoi contribuído por um colega de quarto para um determinado evento. Esta matriz de 2 dimensões, ou matriz, pode serrepresentada como despesas para um EventID por um colega de quarto, J, qualquer que seja a despesa.
(Consulte O Tempo De Deslizamento: 02:21)
Para cada linha desejamos compartilhar a despesa entre todos os colegas de quarto, que são colunas. Isso podeser feito subtraindo o compartilhamento por cabeça para cada roommate de cada espaçador ’ s estado atualde assuntos. Os colegas de quarto com números negativos serão aqueles que terão que pagar enquantocompanheiros de quarto com números positivos contra seus nomes serão aqueles que receberão dinheiro.No final do mês, simplesmente adicionamos as colunas. Novamente, os negativos terão que pagare os positivos estarão recebendo dinheiro.(Consulte o Slide Time: 03:09)
Deixe-nos olhar para a correção desta abordagem. A seguir, algumas perguntas cujas respostas seriammuito importantes para nós, afinal, estamos fazendo uma máquina fazer essas coisas, não mais um humanosendo:• O que realmente queremos dizer com correção?• O que é que queremos? Por que a subtração de per despesas de cabeça para cada feira de atividadepara todos os colegas de quarto? Por que o fim do mês coluna sábados também é justo?• Como essa noção de equidade vai mudar à medida que adicionamos complexidade ao problema?Afinal, estamos considerando a versão simplificada do problema. Mas é uma boa ideia tereste pensamento em nossa mente à medida que nossa complexidade é adicionada, no que outras maneiras podem pensar em
correção ser útil para nós. Poderia haver outras perguntas também, mas para os nossos propósitos essas são principais perguntas dopara nós. Vamos levá-los um por um.(Consulte o Slide Time: 04:20)
O que exigimos fora da ideia de correção ou da abordagem de equidade? Bem, todo mundo quecontribui mais do que a sua parte deve ser devolvido exatamente esse excesso de contribuição. Da mesma forma,qualquer um que não tenha contribuído deve, eventualmente, pagar exatamente essa mesma quantia, o que quer que elesdevam. Na verdade, mais fortemente, não mais, nem menos. Ninguém recebe mais do que o que quer que seja a parcela queele ou ela tem direito. E ninguém paga mais do que o que quer que ele ou ela seja obrigado a. Essa noçãode equidade – você só paga o máximo que deve e só recebe o máximo que você contribuiu.
(Consulte O Tempo De Deslizamento: 05:24)
Vamos ver de perto como essa ideia de equidade realmente funciona, dada a nossa abordagem de solução.Suponha, por exemplo, começarmos com o primeiro evento, para que não haja gastos ou pagamento para serliquidado ou reconciliado. Suponha que um colega de quarto pague por um evento, alguma quantia X. Então, dado quehá NRoomMates no total, a contribuição por cabeça é X dividida pelo número decolegas de quarto. Chamemos a isto por contribuição de cabeça como P.� = ������������������������
Nossa abordagem diz que subtramos a � a partir de cada contribuição de roommate ’, que atualmente é 0,porque é o primeiro evento. Como o � foi contribuído por aquele colega de quarto, e o pessoal é dele ou dela.Portanto, o valor de saldo para este companheiro de quarto que contribuiu seria o � − �. E desdeé subtração de � de 0 para os outros colegas de quarto que não contribuíram, veremos − �para cada colega de quarto que didn ’ t contribuiu.
Isso é bastante consistente com a nossa ideia de que colegas de quarto com números negativos contra eles iriamter que pagar, e colega de quarto com números positivos contra eles teria que ser pago. É uma álgebra simplespara ver que a soma de � − � do roommate de contribuição, e o − � do restodos colegas de quarto é 0.
(Consulte O Tempo De Deslizamento: 07:21)
Deixe-nos olhar para o fim do total de meses. Por que o fim do mês totaliza também justo? A quantidade sábia de colunarepresenta uma única contribuição de roommate ’ ou por ações de cabeça devida aoutras sobre todos os eventos naquele mês. Adicionar todos os montantes para uma coluna dá a quantia líquida queo companheiro de quarto deve pagar ou receber. Se considerarmos o final do mês totaliza para cadaroommate, e dado que o valor a ser pago são negativos, e os montantes a receber são positivos,então você pode usar leis como associatividade ou commutatividade de números para a operação de adição,para mostrar que as somas sábias da coluna total devem sempre ser 0.
(Consulte O Tempo De Deslizamento: 08:15)
Vamos para o próximo passo. Como essa equidade vai mudar com a complexidade? Lembre-se de que temos 2direções distintas em que podemos adicionar complexidade neste problema:1. Um deles são os problemas em si podem ser tornados ainda mais gerais. Por que devemos esperar no finaldo mês para os totais? Por que devemos ter sempre totais para todos? Talvez eu comocolega de quarto possa apenas querer meu total por esse ponto de tempo. Poderia haver muito maiscolegas de quarto do que o que acabamos de considerar, e de tantas outras maneiras – já temosvisto tudo isso.
2. A segunda via seria a generalização da solução baseada em computadores. Gostaríamos depensar se a nossa abordagem de solução permanecerá justa à medida que adicionamos qualquer tipo de complexidade.
(Consulte O Tempo De Deslizamento: 09:23)
Na verdade, ele vai. O argumento de que a soma dos excessos positivos e das dívidas negativas deve ser0 sempre será verdadeira. Esse é o comportamento imutável ou invariável desse problema. De fato, este invariantegarante que a solução é sempre justa e, portanto, correta independentemente da complexidade adicional.(Consulte o Tempo de Slide: 09:51)
Por fim, vejamos de que outras maneiras isso pode pensar sobre a correção nos ajuda. Suponhamos que nóstenhamos milhões de colegas de quarto, embora seja bastante improvável, este invariável ainda garantirá a correçãoda nossa solução. Na verdade, ele também pode nos ajudar a identificar alguns erros de implementação.Por exemplo, nossas máquinas são máquinas de precisão tipicamente finitas. Por isso, podem ocorrer estouros e sob os fluxos de. Se pensarmos um pouco nisso, então qualquer erro de estouro ou subfluxo seráimediatamente refletirmos em nosso invariante se tornar nonzero, o que deve dn ’ t ser o caso se quisermosser completamente justo. O momento em que vemos que nosso invariante é nonzero, sabemos que algo passouerrado!Este é um bom momento para fazer uma pausa. E pense nas questões que acabamos de discutir.(Consulte o Slide Time: 11:04)
Vamos demonstrar a solução usando uma planilha. Sobre a figura dada acima, você verá slideque mostram uma planilha do Libre Office 6,0. Temos um EventID de coluna. Issosignifica basicamente que cada linha representa um evento.
(Consulte O Tempo De Deslizamento: 11:31)
Temos uma coluna que capta as despesas para aquele evento.(Consulte o Slide Time: 11:36)
Temos um monte de colunas para RoommateIDs.
(Consulte O Tempo De Deslizamento: 11:44)
Nós mostramos aqui 5 colegas de quarto, que que são F1, F2, F3, F4 e F5. Na prática,estes poderiam ser alguns nomes reais como Ramesh, Sudha, Nikhil ... etc.
(Consulte O Tempo De Deslizamento: 12:04)
Nós também ilustramos que o roommate F1 pagou alguma quantia para o evento com EventID1.
(Consulte O Tempo De Deslizamento: 12:12)
A região cercada na figura dada acima denota os dados de entrada, ou seja, para um evento, comomuito foi pago por quem.(Consulte o Slide Time: 12:25)
A região cercada na figura dada acima denota os cálculos e os resultados de saída. Esteé onde calculamos a parcela justa de cada colega de quarto para cada evento, e vamos em acumulandoa parcela justa para todos os eventos.
(Consulte O Tempo De Deslizamento: 12:44)
Observe a última coluna que é a invariante. É a soma de cada linha da parte calculada, queé a contribuição menos o compartilhamento de cabeça por cabeça. Esta coluna deve ser sempre zero em cada linha. Nósjá vimos que este é um argumento para a correção. Por isso, na planilha, temos apenassomados as linhas e escrevemos que nesta coluna em particular. Se isso é 0 então sabemos que nossos cálculosestavam corretos.
(Consulte O Tempo De Deslizamento: 13:19)
Aqui também é uma fórmula de planilha para pessoas que podem não saber sobre planilhas. Esta fórmulacalcula a soma de conteúdos de células a partir da coluna J e linha 13 (denotada por
�: 13) à coluna N e linha 13 (denotada por �: 13). Neste exemplo específico, temos 55 −45 + 55 − 70 + 5 = 0. Portanto, nossa solução de planilhas está correta. Ele exatamente equilibraa quantidade que deve ser dada e a quantia que deve ser recebida.(Consulte o Tempo de Slide: 14:15)
Deixe-nos ter uma olhada em solução real de trabalho.(Consulte o Slide Time: 14:21)
Aqui está uma planilha do Excel da mesma solução que vimos. Acrescentemos um VII evento. Deixenós dizer que é rupees 200. Isso significa que entre 5 amigos, a contribuição por cabeça é rupees40. Vamos supor que o amigo número 1 paga 20 rúpias, paga toda a quantia 200 enquanto outros não
pague em tudo. Observe que para o amigo 1, o excesso de quantidade é rupees 160. Sua parcela de rupees 40foi subtraída a partir de 200 e, portanto, 160 é o excesso de quantidade.Muito obviamente, o outro tem que pagar rúpias 40 cada, há 4 deles. Portanto, 160 rúpiastotalmente têm que ser pagas pelos outros 4 e nosso amigo que contribuiu deve receber 160 rúpias.O invariante é, portanto, 0.
(Consulte O Tempo De Deslizamento: 15:45)
Este é novamente um bom ponto para pausar e revisar o que foi feito.(Consulte o Slide Time: 15:52)
Vamos agora olhar para algumas estruturas de dados desse problema. A estrutura de dados chave é claro, uma tabela. Em nossa discussão, denominamos isso como a tabela de despesas, ou pode ser também chamada deuma matriz. Seria bom se pudéssemos indexar esta tabela usando o RoommateID. Isso pode serfeito, por exemplo, usando dicionários em Python. Deixamos essa discussão aqui como o programapode ser implementado em qualquer idioma.Para o nosso curso que utilizamos, estaremos usando Java. Como exatamente temos que realizar a indexação baseada em RoommateIDé algo que deixamos em você! As outras peças de informação são realmentetipos de dados individuais. Por exemplo, o RoommateID é uma string. O EventID é um número inteiro positivo. O gasto ou por parte de cabeça, ou tais objetos, são números reais ou números de ponto flutuante.(Consulte o Tempo de Deslizamento: 17:24)
Também precisaremos da declaração do método que calcula o compartilhamento justo. Esse é um importante processamento de funçãoa ser feito nesta solução. Aqui está um esboço de declaração do método,Boolean computePerHeadShare (Real Despesas []);. Esta declaração éilustrativa e usa uma sintaxe de estilo C, C++ e Java. O método retorna um Boolean: que nos dizemse o trabalho é feito ou não. Talvez à medida que nós progredirmos e adicionamos complexidade, talvez tenhamos que mudaro tipo de retorno para um mais adequado. O método aceita um parâmetro, uma matriz de números reaisdenominada Despesas, que representa a tabela de despesas até o momento.
Quick Check 1: Na palestra utilizamos o Boolean como tipo de retorno paracomputePerHeadShare, mas na verdade esta doesn ’ t serve bem o propósito. O que poderia ser um tipo de retorno melhorpara esta função, e por que?(Consulte o Tempo de Slide: 18:15)
Nós repetimos que este é apenas um esboço das estruturas de dados essenciais. Dependendo do idioma quevocê usa, você pode ter que usar as maneiras corretas de definir essas estruturas de dados. Mais adiante, você podequerer enriquecer essas estruturas de dados. Estes são apenas esboços de ossos descalços. Por exemplo, em vez de apenas númerosna tabela de despesas, você pode querer também adicionar informações de data ou de localização ou descrição.
Em nossas ilustrações na planilha, tínhamos mostrado uma data de coluna, essa informação também foicapturada lá. Você também pode precisar de métodos adicionais. Por exemplo, é possível que vocêqueira computar a parcela justa de um determinado colega de quarto em vez de todos eles. Então, você pode quererdevolver uma matriz de números reais indicando a parcela de um determinado colega de quarto dado por RoommateIDR, e a matriz de Despesas [].
Quick Check 2: Na palestra utilizamos o Real [] como o tipo de retorno para getFairShareOf, masrealmente precisamos de uma matriz de número real? O que poderia ser um tipo de retorno melhor para esta função,e por quê?
Este é um ponto em que nós vamos querer chamar sua atenção. Em algumas designações, podemos mandatoos métodos a serem definidos e usados, podemos afirmar explicitamente que quais são os métodos que vocêprecisa definir e utilizar. Sempre que tal mandato é dado, então sua solução deve ser construídausando os métodos declarados e outros métodos adicionais que você pode considerar necessários. Mas os métodosdeclarados devem ser necessários. Podemos utilizar testes automatizados e, portanto, se eles não existirem em sua solução, não seremos capazes de avaliá-lo e, portanto, você não ganhará créditos por esse esforço.(Consulte o Tempo de Slide: 20:39)
À medida que chegamos ao final desta sessão, deixe-me esboçar nosso caminho para o app web. Em breve olharemosna versão de linha de comando do programa terá seguindo propriedades principais:• A versão da linha de comandos vai ser o app de usuário único.• Ele vai rodar em uma única CPU que é compartilhada entre os colegas de quarto individuais.• Haverá uma única base de informações localizada. Não há rede.Essencialmente, esta é uma arquitetura muito monolítica. Nós generalizaríamos ao incorporar vários usuários, mas ainda com uma CPU compartilhada. Essa CPU compartilhada é o que chamaríamos como um ponto de acesso de serviço. Isso envolveria inclusive uma peça extra de funcionalidade, como autenticação do usuário. E nóspoderíamos ter que pensar em separação de informações versus compartilhamento. Vamos analisar estes como o cursoprogride.
Em seguida, introduziremos a rede. Mas a ideia principal da rede é que um separador de entradae saída e o processamento. Vamos olhar para a web como uma técnica de entrada ampla de rede e saída. Ele abre as possibilidades de arquiteturas de pontos de acesso múltiplo. Portanto, nossa arquiteturanão será mais monolítica e será distribuída. Nossas próximas generalizações seriam ao longo detornando nosso app multi usuário com múltiplos pontos de acesso com vários grupos de colegas de quarto e assimem. Isso você pode usar essa pré-visualização para começar a pensar em como generalizar o seu app em várias maneiras.Rumo ao final deste curso, você terá um projeto de 2 semanas em que você poderá generalizar em comomuitas maneiras diferentes como você pode pensar. É claro que você será obrigado a cometer sua generalizaçãoprimeiro, você tem que afirmar o que é a generalização que você vai fazer e apenasenviar essa parte.Este é um bom ponto novamente para pausar.Com isso chegamos ao final da segunda sessão da semana 1. Obrigado. Veja você na próxima sessão.