sexta-feira, 31 de julho de 2015

[S5] Solução do problema das Sextas-Feiras 13


     O problema das Sextas-Feiras 13, publicado em 14/03/2015, aguçou minha curiosidade e resolvi atacá-lo com Perl e MS-Excel.

     Conforme mencionado anteriormente:
#UNIX time: http://en.wikipedia.org/wiki/Unix_time
#início: Quinta-Feira, 1 de Janeiro de 1970
#   fim: Domingo, 7 de Fevereiro de 2106 (para máquinas 32 bits)
     Algumas datas a seguir só fazem sentido no Calendário Gregoriano, calendário que iniciou em 1582.

Fatos e datas interessantes (formato DD/MM/AAAA, D=Dia,M=Mês,A=Ano):
01/01/0000 - [Mundo] Início do calendário - seria um Sábado
22/04/1500 - [Brasil] Descobrimento do Brasil foi um Domingo
14/07/1789 - [França] Tomada da Bastilha foi uma Terça-Feira
07/09/1922 - [Brasil] Independência do Brasil foi uma Quinta-Feira
09/11/1989 - [Alemanha] Queda do Muro de Berlim em uma Quinta-Feira
11/09/2001 - [Estados Unidos da América] Onze de Setembro foi uma Terça-Feira
08/07/2014 - [Brasil] Mineiraço aconteceu em uma Terça-Feira

     De 01/01/1970, uma Quinta-Feira, até 06/02/2106, um Sábado, existem 49.711 dias e de 01/01/0000, um Sábado, até 06/02/2106, um Sábado, existem 769.238 dias.

     As análises a seguir correspondem à totalidade dos dados (769.238 dias). Observe a figura a seguir:


     As Sextas-Feiras 13 são tão comuns quanto Sábados dia 14 (totalizando 3622 dias neste conjunto). Observe também que um dia mais raro (com 3601 ocorrências) seria uma Sexta-Feira dia 12...

     A seguir, para completar as informações descobertas na massa de dados, são mostradas as contagens para os dias 29-30-31:


     Foram utilizados os arquivos de dados disponibilizados aqui e funções de contagem do MS-Excel (CONTA.SE).

     Então, se fosse necessário escolher uma data bastante rara, seríamos obrigados a escolher uma Quarta-Feira 31!!!!.

     Esta é a data que acontece menos vezes em toda a massa de dados. A próxima Quarta-Feira 31 será dia 31/08/2016, daqui um ano e um mês desta postagem.

Arquivos do projeto

     Existe basicamente dois arquivos para este projeto:
  1. datas-unix.txt: contém as datas de 01/01/1970 até 06/02/2106
  2. datas-todas.txt: contém as datas de 01/01/0000 até 06/02/2106
Faça o download do arquivo neste link.

Questões interessantes deste projeto
  1. Sabendo-se que dia 01/01/1970 foi uma Quinta-Feira e que dia 01/01/0000 foi um Sábado, faça um programa que cria as datas até 06/02/2106. Verifique sua resposta a partir dos arquivos disponibilizados
  2. A partir de uma data específica, por exemplo, 11/09, descubra os anos de quando foi uma terça-feira
  3. Salve em um novo arquivo todas as ocorrências de Quarta-Feira 31 na base de dados

sexta-feira, 17 de julho de 2015

[P14] Qualis CAPES

     O Qualis da Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) é uma listagem que mostra o International Standard Serial Number (ISSN) das revistas científicas (journals) conforme as seguintes áreas:
-Administração, Ciências Contábeis e Turismo
-Antropologia, Arqueologia
-Arquitetura e Urbanismo
-Artes/Música
-Astronomia/Física
-Biodiversidade
-Biotecnologia
-Ciência da Computação
-Ciência de Alimentos
-Ciência Política e Relações Intern.
-Ciências Agrárias I
-Ciências Ambientais
-Ciências Biológicas I
-Ciências Biológicas II
-Ciências Biológicas III
-Ciências Sociais Aplicadas I
-Direito
-Economia
-Educação
-Educação Física
-Enfermagem
-Engenharias I
-Engenharias II
-Engenharias III
-Engenharias IV
-Ensino
-Farmácia
-Filosofia/Teologia
-Geociências
-Geografia
-História
-Interdisciplinar
-Letras/Lingüística
-Matemática, Probabilidade e Estatística
-Materiais
-Medicina I
-Medicina II
-Medicina III
-Medicina Veterinária
-Nutrição
-Odontologia
-Planejamento Urbano e Regional, Demografia
-Psicologia
-Química
-Saúde Coletiva
-Serviço Social
-Sociologia
-Zootecnia, Recursos Pesqueiros
     Um dos usos destas divisões é classificar os programas por área e dar uma nota para cada revista científica, conforme os seguintes estratos (do melhor qualificado para o pior): A1, A2, B1, B2, B3, B4, B5 e C.

     O problema é que uma mesma revista científica pode ser qualificada de diferentes formas conforme os estratos do Qualis (eu não tenho a resposta para isso), ao invés de simplesmente utilizar o Fator de Impacto de cada revista. Isso faz com que, por exemplo, um pesquisador olhe cada ISSN e escolha os melhores estratos, por exemplo, a revista Applied Mathematics and Computation (ISSN 0096-3003), possui um fator de impacto considerado razoável (Impact Factor: 1.551), mas possui os seguintes estratos em cada área:
SAÚDE COLETIVA (A2)
CIÊNCIA DA COMPUTAÇÃO (A2)
ENGENHARIAS II (B1)
ENGENHARIAS III (A2)
ENGENHARIAS IV (A2)
INTERDISCIPLINAR (A2)
BIODIVERSIDADE (B1)
CIÊNCIAS AGRÁRIAS I (B1)
CIÊNCIAS AMBIENTAIS (B3)
CIÊNCIAS BIOLÓGICAS II (B3)
MATEMÁTICA / PROBABILIDADE E ESTATÍSTICA (B1)
GEOCIÊNCIAS (B1)
MEDICINA II (B1)
MEDICINA III (B1)
MATERIAIS (B2)
ENSINO (B3)
QUÍMICA (B3)
     Observe que a mesma revista, com o mesmo fator de impacto, varia de A2 (uma excelente classificação conforme o Qualis) até B3 (considerado ruim). O Qualis, desta forma, incentiva os pesquisadores a escolher a "revista perfeita" na hora de submissão, ao invés de escolher conforme o fator de impacto, que seria muito mais razoável.

Arquivos do projeto

     Existe basicamente um arquivo para este projeto:
  1. lista-de-revistas.txt: contém 59517 revistas do Qualis (baixado do sistema da CAPES em 15/Julho/2015), com seus respectivos ISSNs e estratos conforme áreas da CAPES
Faça o download do arquivo neste link.

Questões interessantes deste projeto
  1. Faça um programa que mostra, para cada ISSN, a lista de todos seus estratos da CAPES
  2. Para cada estrato da CAPES, mostre as revistas qualificadas
  3. Descubra as revistas com maiores variações em termos de estratos (por exemplo, de A1 até B3)
  4. Descubra as revistas com maior quantidade de estratos CAPES

sexta-feira, 3 de julho de 2015

[P13] Pesquisadores brasileiros (Dados de Julho de 2015)


     O Brasil investiu muito dinheiro em pesquisa nos últimos anos. Isso refletiu em citações nos artigos de outros pesquisadores do mundo inteiro, de forma positiva, colocando o país em uma posição de destaque na pesquisa internacional.

     O site Webometrics - Ranking Web of Universities disponibiliza um ranking de pesquisadores do mundo inteiro a partir do H-Index e do total de citações em artigos. O link Ranking of scientists in Brazilian Institutions according to their Google Scholar Citations public profiles mostra o ranking do Brasil.

     Mas o que significa o H-Index? Meu perfil no Google Scholar, datado de hoje, 3/Julho/2015 (vamos usar este método, neste post, existem outras maneiras, tais como usar o Scopus, etc), indica que o meu H-Index é 7. Isso significa que eu tenho pelo menos 7 artigos com 7 citações cada (obviamente, eu tenho mais do que 7 artigos, mas estes tem menos de 7 citações, então não entram no cômputo do índice). Este H-Index é considerado baixo, já que o primeiro pesquisador do ranking do Webometrics possui H-Index de 126 (ou seja, ele tem pelo menos 126 artigos com 126 citações cada).

     As dificuldades de se usar o H-Index como métrica para bons pesquisadores são muitas, por exemplo, eu poderia apenas citar meus próprios trabalhos, com o objetivo de aumentar o meu índice. Existem maneiras de coibir isso, retirando da contagem de citações as chamadas auto-citações, entre outras técnicas (avaliações de pares consistentes, que removam estes comportamentos, etc). Hoje em dia, observa-se que os pesquisadores lutam para serem citados, pois reflete diretamente no aumento do seu H-Index. Claro que bons pesquisadores desejam realizar apenas pesquisas relevantes, sendo citados de forma natural por outros pesquisadores, mas muitas vezes, não é isso que se observa.

Dados

     Baixe neste link os arquivos para este projeto - existe apenas um arquivo, ordenado por H-Index, com tamanho de 400Kb, com dados de Julho de 2015, contendo o seguinte cabeçalho:
#RANK;NAME;ORGANIZATION;H-INDEX;CITATIONS
  onde:
#RANK mostra o número do pesquisador no ranking (variando de 1 a 6000, com possibilidade de existir valores repetidos)
#NAME indica o nome do pesquisador
#ORGANIZATION mostra a afiliação do pesquisador (podendo ter mais de uma)
#H-INDEX mostra o índice H do pesquisador
#CITATIONS indica o total de citações (de todos os seus artigos científicos) feita por ele ou por outros pesquisadores
     Por exemplo, os primeiros 5 pesquisadores são:
RANK NOME ORGANIZATION H-INDEX CITATIONS
1Cesar VictoraUniversidade Federal de Pelotas10647202
2Maria Elena PolCentro Brasileiro de Pesquisas Físicas10553007
3S F NovaesUniversidade Estadual Paulista10047511
4Eduardo de Moraes GregoresUniversidade Federal do ABC10044555
5Luiz MundimUniversidade do Estado do Rio de Janeiro9844501

Questões interessantes deste projeto
  1. Aspectos gerais - estatísticas interessantes
    1. Quais instituições, sem repetição estão listadas no arquivo?
    2. Construa um ranking por instituição que mais possui pesquisadores na listagem
    3. Crie um arquivo novo chamado pesquisadores-citacoes.txt que organiza os pesquisadores pelo seu total de citações (e não pelo H-Index)
    4. Quantos pesquisadores empataram no ranking?
  2. Desafio
    1. Tente classificar os pesquisadores por região do Brasil, conforme a localização da Universidade (descubra onde fica cada universidade, esta informação não foi disponibilizada em nenhum arquivo)

sexta-feira, 19 de junho de 2015

[P12] Arquivos de Log de um site na Internet

     Criei um logger, um script para salvar os downloads do meu site pessoal na Internet em 19/06/2010 (foram 1826 dias de log). Cinco anos depois, em 19/06/2015, torno público os resultados obtidos. As capturas guardam a data de cada download, o arquivo que foi baixado e o endereço IP origem do download.
     É possível observar que em algumas datas, alguns endereços IPs foram mais utilizados que outros (provavelmente um ataque?), assim como existem arquivos que são mais baixados que outros.
     A seguir, apresento algumas informações interessantes sobre o endereçamento geográfico e distribuição de endereços IP pelo globo terrestre, para facilitar a implementação de alguns itens dos projetos.

Endereçamento dos Protocolos de Internet

     Existem duas formas de endereçar máquinas na Internet: através dos protocolos IPv4 e IPv6 (onde está o IPv5?). O IPv4 possui uma quantidade limitada de endereços, então está sendo gradualmente substituído (há uns 15 anos já...) pelo protocolo IPv6 que tecnicamente possui tantos endereços IP quanto partículas de areia no universo.
     Existe uma governança da Internet, mas quem controla os endereços é a ICANN - Internet Corporation for Assigned Names and Numbers - Corporação da Internet para Atribuição de Nomes e Números.
     Enquanto que o IPv4 endereça cerca de 4 bilhões (4x109) de endereços IP, o IPv6 consegue endereçar 3,4x1038 endereços. Este fato é particularmente interessante quando se sabe que a rede está expandindo à medida que o tempo passa com a adição de novos dispositivos (tablets, smartphones, etc). A seguir, são apresentados exemplos de endereços de cada protocolo:
IPv4 => 173.194.119.49
IPv6 => 2001:bce4:5641:3412:341:45ae:fe32:65
     O livro "IPv6 Address Planning: Designing an address plan for the future", escrito por Tom Coffeen (Publicação: O'Reilly Media, Data: November 2014, 286 páginas) apresenta uma tabela interessante sobre os endereçamentos dos protocolos (e outras contagens interessantes) - clique na imagem para expandi-la:


Dados

     Um único arquivo de dados contém tudo, com o seguinte cabeçalho:
#IP = 0 | ARQUIVO = 1 | DATA = 2 ; VALOR ; QUANTIDADE
     O primeiro campo é um valor 0,1 ou 2 indicando que se trata de um endereço IP, um arquivo ou uma data, seguido do valor correspondente e uma quantidade.

     IP é um endereço conforme o protocolo IPv4, com quatro sequências de 256 caracteres separadas por ponto ('.'):
XXX.XXX.XXX.XXX => XXX varia entre 0 e 255 (inclusive)
     DATA é uma data entre 19/06/2010 e 19/06/2015, no seguinte formato:
DD/MM/AAAA, onde D=Dia, M=Mês, A=Ano
     Se for um arquivo, mostra o nome do arquivo presente no site. Todos os arquivos que foram baixados pelo menos uma vez encontram-se na listagem.

     Cada país recebe uma faixa de endereços IP, sendo possível saber o país de origem do IP. Os dados foram obtidos do site http://services.ce3c.be/ciprg/ no dia 18/06/2015 (os dados mudam constantemente). O nome do arquivo é IP-RANGES-ALL COUNTRIES.txt, disponível para download.

     Baixe neste link os arquivos para este projeto

Questões interessantes deste projeto
  1. Aspectos gerais - estatísticas interessantes
    1. Quantos IP foram salvos, quantas datas e quantos arquivos existem no arquivo de log?
    2. Qual país possui o maior número de faixas nas atribuições da Internet?
  2. Sobre os endereços IP utilizados
    1. Qual é o endereço IP que mais baixou arquivos?
    2. Conforme o país do download, quais foram os países que mais baixaram arquivos?
    3. Conforme o continente, quantos downloads foram realizados? (considere: América do Sul, América do Norte, América Central, África, Ásia, Oceania e Europa)
  3. Sobre os arquivos baixados
    1. Qual foi o arquivo mais baixado?
    2. Quantos downloads de cada tipo foram feitos? (por exemplo, .pdf, .txt, .z0, etc)
    3. Quantos artigos foram baixados (um artigo possui um nome todo em maiúsculo seguido de um ano, por exemplo ICGSE2006.pdf)
    4. Quais são os N arquivos mais baixados (onde N é passado por parâmetro)?
  4. Sobre as datas de download
    1. Qual foi a data com maior número de acessos?
    2. Qual data possui o menor número de acessos? (mostre todos os empates de acessos)
    3. Quais são as N datas com mais acessos (onde N é passado por parâmetro)?
    4. Quantas datas possuem apenas 1 acesso?

sexta-feira, 5 de junho de 2015

[P11] Dados da Copa 2014 - Portal da Transparência

     Não é segredo para ninguém que a Copa 2014 no Brasil custou muito dinheiro a todos os contribuintes brasileiros. Foram jogadas 64 partidas a um custo estimado de R$ 27.346.140.056,43 (segundo o site - leia a seguir). Foram 27 bilhões de reais, ou seja, cada partida custou R$ 421.875.000. Foram marcados 171 gols durante as partidas sendo 26 gols extra de pênaltis, a um custo de R$ 157.894.736,84 por gol. Foram 157 milhões de reais por gol! No fatídico jogo dos 7x1 para a Alemanha, o Brasil PAGOU R$ 1.105.263.158,00 para levar 7 gols (sim, nós brasileiros pagamos 1 bilhão de reais para levar 7 gols e uma humilhação em casa), e ganhou apenas R$ 157 milhões de volta...
     Claro que muitos falam que muito dinheiro foi gasto por estrangeiros e por empresas que investiram por aqui e que mesmo custando bastante dinheiro foi interessante voltar a sediar uma Copa do Mundo, algo que não acontecia desde 1950 (os brasileiros tiveram que esperar 64 anos para voltar a ver uma copa do mundo). Muito dinheiro em infraestrutura foi investido e muitas obras com certeza nem teriam começado se não fosse pela copa.
     O governo montou um site onde disponibiliza diversos dados sobre os gastos da copa para efeitos de transparência. Muitos dos dados obtidos a seguir referem-se a este site. Um outro site que mostra diversas estatísticas dos jogos da Copa do Mundo 2014 encontra-se na Wikipedia.



     A tabela a seguir mostra uma listagem de todas as equipes que participaram da copa (ordenados alfabeticamente por nome do país em português):
#TimeTeam
1AlemanhaGermany
2ArgéliaAlgeria
3ArgentinaArgentina
4AustráliaAustralia
5BélgicaBelgium
6Bósnia e HerzegovinaBosnia and Herzegovina
7BrasilBrazil
8CamarõesCameroon
9ChileChile
10ColômbiaColombia
11Coreia do SulSouth Korea
12Costa do MarfimCote d'Ivoire
13Costa RicaCosta Rica
14CroáciaCroatia
15EquadorEcuador
16EspanhaSpain
17Estados UnidosUnited States of America
18FrançaFrance
19GanaGhana
20GréciaGreece
21HolandaNetherlands
22HondurasHonduras
23InglaterraUnited Kingdom
24IrãIran
25ItáliaItaly
26JapãoJapan
27MéxicoMexico
28NigériaNigeria
29PortugalPortugal
30RússiaRussia
31SuíçaSwitzerland
32UruguaiUruguay

     Foram feitos 65 gols no primeiro tempo e 106 no segundo tempo. A tabela a seguir mostra o total de gols por partida:
GolsTotal
07
112
28
320
49
54
62
71
81

     A tabela a seguir mostra os gols marcados por cada equipe:
TimeTotal de gols
Alemanha18
Argélia7
Argentina8
Austrália3
Bélgica6
Bósnia4
Brasil11
Camarões1
Chile6
Colômbia12
Coreia do Sul3
Costa do Marfim4
Costa Rica5
Croácia6
Equador3
Espanha4
Estados Unidos5
França10
Gana4
Grécia3
Holanda15
Honduras1
Inglaterra2
Irã1
Itália2
Japão2
México5
Nigéria3
Portugal4
Rússia2
Suíça7
Uruguai4



     Os seguintes estádios foram utilizados (total de 12 sedes):
#NomeLocalizaçãoCapacidade (oficial)PartidasPúblicoGols
01Arena AmazôniaManaus44.0004160.22714
02Arena da BaixadaCuritiba42.3724156.9918
03Arena das DunasNatal32.0504158.1675
04Arena Fonte NovaSalvador50.0256300.67424
05Arena PantanalCuiabá44.0004158.71712
06Arena PernambucoRecife44.3005204.88211
07Arena de São PauloSão Paulo66.7956375.59311
08Estádio Beira-RioPorto Alegre56.0005214.96922
09Estádio CastelãoFortaleza63.9036356.89617
10Estádio Nacional de Brasília Mané GarrinchaBrasília72.7887478.21820
11Estádio do MaracanãRio de Janeiro78.8387519.18910
12Estádio MineirãoBelo Horizonte61.8466345.35017
TOTAIS643.429.873171

     Foram marcados 171 gols em 64 jogos (para efeito de estatísticas não são contabilizados os gols provenientes de decisões por penalidades máximas). A média de gols ficou em 2,7 gols por partida, empatando com o recorde da Copa do Mundo de 1998 na França com o mesmo índice.



     Em termos de distâncias entre as cidades-sede da Copa do Mundo, algumas equipes tiveram que viajar muito mais do que outras, conforme a tabela a seguir (distâncias em quilômetros):

     Manaus prova ser uma cidade longe de todas as demais cidades-sede do Brasil (menos de Porto Alegre, onde Fortaleza consegue ser mais distante).

O desempenho do Brasil nos jogos da copa

     A tabela a seguir mostra os jogos apenas do Brasil (no arquivo de dados são disponibilizadas todas as partidas da copa):
FaseTime 1PlacarTime 2PênaltisDataHoraEstádio
Grupo ABrasil3x1Croácia 12/06/201417:00Arena de São Paulo
Grupo ABrasil0x0México 17/06/201416:00Castelão
Grupo ABrasil4x1Camarões 23/06/201417:00Mané Garrincha
OitavasBrasil1x1Chile3x228/06/201413:00Mineirão
QuartasBrasil2x1Colômbia 04/07/201417:00Castelão
Semi-finaisAlemanha7x1Brasil 08/07/201417:00Mineirão
Terceiro lugarBrasil0x3Holanda 12/07/201417:00Mané Garrincha
Brasil: 7 jogos, 11 gols pró e 14 gols contra

     No jogo do 7x1, dia 08/Julho/2014, no Mineirão (gentilmente apelidado de Minerazo em 2014, pois em 1950 havia tido um Maracanazo no Maracanã), a seguinte sequência de gols foi anotada:
JogadorMinuto
Thomas Müller11'
Miroslav Klose23'
Toni Kroos24'
Toni Kroos26'
Sami Khedira29'
Andre Schürrle69'
Andre Schürrle79'
Oscar dos Santos Emboaba90'
     A vantagem é que ficamos 11 minutos sem levar gols da Alemanha ou ficar atrás do placar!

Dados sobre o time brasileiro que jogou a partida dos 8 gols

     O sonho do Hexa-Campeonato Mundial foi desmanchado em 18 minutos (11' a 29') do primeiro tempo. Com 5x0, bastou que a Alemanha administrasse o jogo. O time brasileiro não esboçou nenhuma reação ou gana para tentar (de alguma forma) reverter o placar ou amenizá-lo. A zaga brasileira parecia um queijo suíço, e o jogo parecia de várzea de tão fácil que a Alemanha atacava. A impressão de todos era que aqueles jogadores brasileiros nunca haviam jogado futebol escrevendo para sempre esta escalação no imaginário das pessoas (ordenados pelo número da camiseta, exceto o goleiro):
NúmeroJogadorFunção
12Júlio CésarGoleiro
4David LuizZagueiro
5Fernandinho (Paulinho)Volante (Volante)
6MarceloLateral
7Hulk (Ramirez)Atacante (Volante)
9Fred (Willian)Atacante (Meia)
11OscarMeia
13DanteZagueiro
17Luiz GustavoVolante
20BernardAtacante
23MaiconLateral
     O Neymar teve a sorte das sortes e não jogou esta partida pois estava machucado por uma entrada covarde de um jogador da Colômbia, assim como o zagueiro Thiago Silva que também não jogou. Agora, a possibilidade é que a Alemanha alcance o Penta-Campeonato, mas meu palpite é que a Holanda será campeã do mundo antes.

Dados

     Os dados a seguir mostram alguns arquivos que mostram os gastos e as estatísticas da Copa do Mundo 2014. Faça o download dos seguintes arquivos:
  1. Dados gerais dos jogos: neste arquivo tem as distâncias das cidades-sede, os estádios da copa, as informações dos países que jogaram (PIB, população, etc - dados de Julho de 2014 obtidos no CIA World Factbook), a tabela da copa com o nome dos jogadores que marcaram gols e o tempo de jogo, e a listagem dos times participantes.
  2. Dados do Portal da Transparência - originais
  3. Dados do Portal da Transparência - formatados: os arquivos sofreram alguns tratamentos de formatação por exemplo para conter apenas um registro por linha e também foram retirados os nomes das colunas dos arquivos .txt e colocados como cabeçalhos nos arquivos .csv, para facilitar a construção de parsers específicos. Também foram removidos alguns problemas nos dados (por exemplo, em alguns pontos tinha caracteres ';' ou duas aspas duplas ("") no meio do texto que não poderiam ficar onde estavam)
     Sobre os dados obtidos do Portal da Transparência do Governo Federal, os seguintes arquivos são os mais interessantes:
  1. 20150412_AcaoGoverno.csv - ações do governo federal para a copa
  2. 20150412_Desembolso.csv - mostra os desembolsos realizados
  3. 20150412_ExecucaoFinanceira.csv - mostra dados interessantes sobre datas e gastos de toda a copa
  4. 20150412_FonteRecurso.csv - mostra as fontes de recursos em uma listagem
  5. 20150412_Instituicao.csv - mostra a lista das instituições que participaram de alguma iniciativa
  6. 20150412_PessoaFisica.csv - mostra o nome e o cpf de pessoas físicas que trabalharam nos projetos
  7. 20150412_RelatorioExecucao.csv - mostra relatórios (por exemplo, um relatório fotográfico) de algum projeto da copa
Questões interessantes deste projeto
  1. Baseando-se nas informações dos jogos
    1. Mostrar as estatísticas gerais das partidas: total de gols, conforme os placares, contando penalidades, gols contra e gols realizados em continuações (após 45' e após 90'), média de gols da copa (conforme o total de partidas)
    2. Mostrar o ranking dos gols dos jogadores (qual jogador marcou mais gols)
    3. Mostrar o total de partidas por país (ordenados pelo total de forma ascendente)
    4. Descobrir o jogo (da fase de grupos) com maior número de gols
    5. Mostrar a incidência de todos os placares: quantos 0x0, quantos 1x0, etc
    6. Mostrar estatísticas do total de gols marcados no primeiro (0' a 45') tempo e no segundo tempo (46' a 90')
    7. Conforme as vitórias (3 pontos) e empates (1 ponto), mostre a tabela de jogos (completa, com gols pró e gols contra) das oitavas de final
  2. Baseando-se nas informações dos países (#País;Área Total;População;EVH(Esperança de vida para homens);EVM(Esperança de vida para mulheres);PIB(Produto Interno Bruto))
    1. Qual é o país com menor PIB que ganhou o maior número de jogos? Qual é o país com menor PIB que fez mais gols?
    2. Qual é a relação (total de gols)/(população) que existe para todos os países na Copa do Mundo 2014?
    3. Qual é a relação (total de gols)/(área total) que existe para todos os países na Copa do Mundo 2014? Qual é o maior e o menor país em termos de área que fez mais gols?
    4. Qual país com a maior distância entre a Esperança de Vida entre Homens e Mulheres que fez mais pontos na fase de grupos da copa?
  3. Baseando-se nos dados do Portal da Transparência (formatados)
    1. Quanto foi gasto em todas as ações do governo para a Copa do Mundo e Copa das Confederações conforme os dados dos arquivos?
    2. Mostre uma lista das fontes de recursos da copa
    3. Crie um arquivo chamado instituicoes-datas.txt e coloque o nome da Instituição Contratante (campo IdInstituicaoContratante presente nos arquivos de Execução Financeira e IdInstituicao no arquivo de Instituições) e data inicial e final de vigência de todas as execuções financeiras da Copa do Mundo
    4. Mostre uma lista dos recursos destinados a pessoas físicas na Copa do Mundo (descubra os campos onde encontram-se estas informações)
  4. Desafios gerais do projeto
    1. DESAFIO 1: dada a lista de times e as distâncias entre as sedes, implemente uma tabela de jogos para a copa do mundo, escolhendo uma seleção para se deslocar o mínimo (não vale fixar a seleção em uma cidade-sede, ela tem que sair pelo menos 2 vezes durante seus jogos). Mostre o total em quilômetros que serão deslocados e os dados das partidas (duas seleções não podem jogar no mesmo horário, etc)
    2. DESAFIO 2: tente remontar um banco de dados a partir das informações presentes nos arquivos do Portal da Transparência

sexta-feira, 22 de maio de 2015

[P10] Programa = Estruturas de Dados + Algoritmos

     Uma definição interessante de programa relacionando o conceito à estruturas de dados e algoritmos foi proposta por Niklaus Wirth, em 1976: Algorithms + Data Structures = Programs. Trata-se de um livro de mesmo nome que discute sobre tópicos fundamentais de programação de computadores. Para maiores informações acesse este site da Wikipedia.

Considere o seguinte problema:
Um professor ministra aulas para uma turma de alunos e estes realizam três avaliações por semestre. A turma possui 30 alunos e cada aluno, além do nome e das notas das três avaliaçôes (valores entre 0 e 10 - assumindo que uma nota válida é sempre inserida para o aluno), possui um total de presenças no semestre. O professor guarda o total de encontros realizados em cada turma. O professor gostaria de calcular algumas estatísticas que julga interessantes, tais como a média das notas da turma, o número de alunos com notas abaixo da média (7,0) e o número de alunos com frequência tanto acima quanto abaixo de 75%. O professor também gostaria de buscar (procurar) alunos pelo nome do aluno e mostrar suas notas e o número de presenças em um relatório.

Modelagem

     Como modelar este problema?
     Sem considerar o paradigma de programação envolvido (orientado a objetos ou imperativo), quais são as estruturas de dados envolvidas e as funcionalidades que o professor deseja realizar? Como transformar esta especificação escrita em alto-nível em um código-fonte compilável e executável?

Estruturas de dados:
  1. Turma
    1. lista de alunos (uma estrutura homogênea que guarda um aluno (uma estrutura heterogênea, ou seja, um registro))
    2. total de encontros (provavelmente um valor inteiro)
  2. Aluno
    1. nome (um valor textual, ou seja, uma estrutura homogênea que trababalhe com caracteres)
    2. presenças (um valor inteiro)
    3. notas (de 1 a 3 valores reais, ou seja, números com ponto flutuante, sendo uma estrutura homogênea)
Funcionalidades desejadas:
  1. Cálculo de estatísticas
    1. Cálculo da média das notas da turma
    2. Cálculo do total de alunos com frequência acima de 75%
    3. Cálculo do total de alunos com frequência abaixo de 75%
  2. Criação de uma turma
    1. Associação do total de presenças em uma turma
  3. Criação de um aluno
    1. Associação das notas de um aluno
  4. Inserção de um aluno em uma turma
  5. Mostrar os dados dos alunos (todos, inclusive estatísticas) de uma turma
  6. Busca de um aluno em uma turma pelo nome
  7. Função principal main() necessária sempre em qualquer implementação de um programa
Programa:
  1. main.c (Linguagem C) e main.cpp (Linguagem C++) = contém a criação das turmas, alunos e associações necessárias (nome e notas a alunos, alunos a turmas, total de presenças à turmas)
  2. Estrutura de dados Aluno
  3. Estrutura de dados Turma
  4. Algoritmos para cálculos das estatísticas

OBSERVAÇÃO: antes de começar a mostrar alternativas de implementação, é importante que se mencione que existem muitas formas de modelar e implementar este problema, sendo a apresentada aqui apenas uma alternativa viável. É importante que você como programador implemente outras formas a fim de aprimorar sua própria técnica de programação.

Paradigma Imperativo, ou Estruturado

     A característica principal do paradigma imperativo (ou estruturado) é definir funções que operam sobre as estruturas de dados (que são passadas por parâmetro). Os acessos são públicos, ou seja, é possível alterar os valores de quaisquer estruturas de dados a qualquer momento (cabe ressaltar que estamos trabalhando com ponteiros, então os endereços de memória que são passados referem-se às estruturas de dados, ou seja, qualquer alteração é realizada diretamente sobre os dados).
     O paradigma foi e ainda é amplamente utilizado, necessitando um nível de experiência alto por parte dos programadores para acessar e operar de forma eficiente os algoritmos e os tratamentos com a memória.

Paradigma Orientado a Objetos

     Em orientação a objetos, as estruturas de dados são chamadas de classes. As instâncias de cada classe são chamadas de objetos. As classes possuem atributos (características dos objetos) e operações (métodos). Os objetos são instanciados a partir de classes, podendo existir muitos objetos (com estados diferentes) de uma mesma classe. No nosso exemplo, será criado um objeto da classe Turma e um aluno da classe Aluno. Cada objeto terá suas próprias características, ou seja, possuirá um estado diferente. Para o caso dos alunos, cada objeto terá um nome específico e uma listagem de notas.
     As classes no projeto são: Turma e Aluno, além do método main(), sempre necessário em qualquer implementação. A turma e o aluno, em termos de características são idênticas à forma imperativa anterior, mas agora possuem operações (métodos) que operam sobre seus atributos (variáveis internas - sempre privadas). Por exemplo, a turma trata com uma lista de alunos e cada aluno trata das suas notas, seu nome e seu total de presenças.
     O conceito chave em orientação a objetos é a proteção aos dados. A forma que é feita esta proteção é através dos modificadores de acesso aos atributos, ou seja, os modificadores public e private (OBS: o modificador protected será explicado em um outro momento pois não faz sentido sem o conceito de herança).
     Como sugestão (uma forte sugestão), todos os atributos de um objeto devem ser privados, ou seja, não deve ser permitido modificá-los exceto através de métodos públicos. Por exemplo, o nome do aluno: apenas a própria classe pode ter acesso irrestrito. Por isso que ao instanciar um aluno na função principal main(), não é permitido fazer a seguinte chamada: aluno->nome = "João da Silva"; - o que era permitido antes. As maneiras de se alterar o nome do aluno são duas: através do método especial construtor (método invocado quando um objeto é instanciado) ou através do método público chamado void setNome(string novo); definido na classe aluno (a chamada seria feita desta forma: aluno->setNome("João da Silva");, onde aluno é uma instância (um objeto), do tipo ponteiro, da classe Aluno).
     A implementação é bem parecida com o paradigma imperativo, exceto que agora, ao operar sobre a turma, não é mais necessário passar uma referência de turma por parâmetro, basta disparar o método do objeto turma.

Resumo das diferenças de definições e nomenclaturas

     A tabela a seguir mostra as principais diferenças entre as abordagens estruturada ou imperativa e orientada a objetos. Cabe ao programador escolher a melhor linguagem e paradigma para resolver seu problema. Idealmente, um programador sabe e domina diversos paradigmas e linguagens de programação (pelo menos o básico, depois é possível se aprofundar). Os conceitos inerentes à cada paradigma devem ser firmemente entendidos pelos programadores, auxiliando-os a resolver problemas e transformar especificações escritas por clientes em códigos-fonte consistentes, coerentes e lógicos.

Programação imperativa Programação orientada a objetos
Registros (structs) Classes (class)
Funções Métodos (operações)
Variáveis Atributos (características)
Instâncias de classes (objetos)
Acesso público Acesso público e privado
Referências e ponteiros Referências e ponteiros
Variáveis locais de funções Variáveis locais de métodos
Bibliotecas de funções Bibliotecas de classes (STL em C++)

Arquivos dos projetos

     Existem basicamente duas ideias principais utilizando a ferramenta (IDE - Integrated Development Environment) CodeBlocks:
  1. Um projeto utilizando o paradigma imperativo, ou estruturado: foi utilizado apenas um arquivo (main.c) para codificar a solução
  2. Dois projetos que utilizam modelagem orientada a objetos: foi criado um arquivo para cada classe e mais um arquivo para a função main (main.cpp). Estas soluções poderiam ter sido escritas utilizando-se outras linguagens de programação orientadas a objetos tais como Java ou C# - o que importa aqui é o paradigma, a forma de se modelar o problema em um código-fonte.
     Observe e compare ambas as soluções e entenda as principais diferenças e características de cada abordagem. Disseque o código-fonte. Entenda tudo que foi feito. Modifique o código-fonte para oferecer outras funcionalidades às classes.

Programando a função main antes

     Às vezes, é melhor pensar na função main() e como seriam instanciados os objetos ou criadas as variáveis que executarão o programa. Por exemplo:
int main() {

   Aluno* jorge = new Aluno();
   jorge->adicionaNotas(4.5, 5.0; 9.0);
   Aluno* joao = new Aluno("Joao");
   joao->adicionaNotas(6.0);
   joao->adicionaNotas(8.0);
   joao->adicionaNotas(4.0);
   Aluno* jonas= new Aluno("Jonas", 5.5, 6.5, 7.5);
   jonas->setFaltas(12);

   Turma* turma128 = new Turma("Turma 128");
   turma128->adicionaAluno(jorge);
   turma128->adicionaAluno(joao);
   turma128->adicionaAluno(jonas);

   float media = turma128->calculaMedia();
   cout << "Media da turma: " << media << endl;

   delete jorge;
   delete joao;
   delete jonas;   // realizar estas chamadas *apenas* 
                   //    se o método destrutor de turma 
                   //    não chamar o delete de alunos
   delete turma;
   return 0;
}
     O interessante desta abordagem é que ela auxilia a criar os métodos das classes necessários para o projeto, por exemplo, já é possível saber os construtores das classes Aluno e Turma, os métodos existentes na classe Turma (void adicionaAluno(Aluno* al);), alguns métodos presentes na classe Aluno (como void adicionaNota(float nota);, void adicionaNota(float* nota); e void setFaltas(int num);) e o método que retorna a média dos alunos da turma (float calculaMedia();). O mesmo procedimento é possível para o paradigma funcional. Claro que evidentemente ainda faltam diversos outros métodos, sendo esta apenas uma alternativa de programação.

Programando de forma mais geral

     O presente projeto definiu que seriam utilizadas apenas 3 notas para 30 alunos, com percentual de presenças igual a 75% e média 7,0. Entretanto, o professor pode solicitar que deseja realizar quatro avaliações ou cinco (ou mais) para 10 ou 50 alunos (validar que estes números encontram-se em limites razoáveis e possíveis). O professor pode também desejar que a média de uma turma seja definida em 5,0 ou 7,5. Também, para diferentes turmas, o percentual de faltas permitido pode ser 50% ou 90% (não permitir valores abaixo de 0% e acima de 100%). Ainda, o professor comunicou que alguns alunos faltam às provas (conforme o total de provas existentes), ou seja, suas médias devem ser computadas apenas para as avaliações que estavam presentes. Para implementar estes novos requisitos, quais alterações nas estruturas de dados e nos algoritmos devem ser implementadas para resolver estes problemas e possibilitar estas novas funcionalidades?

Dados

     Os dados a seguir mostram três projetos construídos a partir da problemática acima. Faça o download dos seguintes arquivos:
  1. Projeto implementado com paradigma imperativo na Linguagem C
  2. Projeto implementado com paradigma orientado a objetos na Linguagem C++, implementado com valores constantes para o total dos alunos, frequências permitidas, etc
  3. Projeto implementado com paradigma orientado a objetos na Linguagem C++, implementado com valores variáveis para os totais de alunos nas turmas, entre outras características gerais
Questões interessantes deste projeto
  1. Alguns alunos fazem todas as provas, outros fazem apenas algumas. Deve ser possível fazer a média apenas das provas que foram feitas pelos alunos e saber quantas provas ele faltou
  2. Ás vezes os alunos perguntam: "Professor, quantas faltas ainda posso ter para não reprovar por faltas?". Deve ser possível mostrar um relatório contendo o total de encontros e, para cada aluno, o total de faltas permitidas conforme as regras (o nível de frequências permitidas)
  3. Deve ser possível também, dada (n-1) notas dos alunos, indicar quanto é necessário que eles tirem para passar por média e dado que suas presenças estão dentro das regras de frequências permitidas
  4. Os alunos, além das provas, possuem notas de trabalhos realizados ao longo da disciplina. Deve ser possível configurar o total de trabalhos
  5. O professor pode decidir usar pesos para cada avaliação (de prova e de trabalho) e calcular a média final dados estes pesos para cada avaliação
  6. O professor pode querer ver as médias das provas e a média dos trabalhos
  7. Deve ser possível saber o melhor e o pior aluno da turma, ou seja, o aluno com maior média com menor número de faltas e o aluno com a menor média e maior número de faltas (nesta ordem de preferência - caso empatem na melhor ou pior nota, deve ser olhado as faltas, caso empatem novamente, retorna-se o aluno com mais notas abaixo da média, caso ainda empatem, retorna-se o aluno em ordem alfabética)
  8. Podem existir provas de recuperação para os alunos que faltaram a alguma prova (só podem recuperar as provas que faltaram)
  9. Implemente os vetores de alunos e de notas utilizando a classe da STL vector (mantenha o uso de ponteiros para alunos)
  10. Acrescente outros atributos (características) tais como: data de nascimento (string), número de matrícula (string), valor booleano indicando se é um bolsista de iniciação científica e filiação (nome do pai e nome da mãe - em uma classe separada). A seguir, faça métodos para retornar e configurar estes atributos, calcular a diferença de dias existente entre hoje e a data de nascimento de cada aluno da turma e um relatório contendo todos os dados de todos os alunos (de forma visualmente atraente)
  11. Implemente no aluno um índice que guarda sua vontade de aprender, variando de 0 até 1. Este índice, afeta suas notas de prova, sendo decrescidas conforme o índice em percentual, por exemplo, um aluno com índice de 0,10 este aluno teria suas notas (todas) decrescidas em 10% e assim sucessivamente. Mostre as notas de cada aluno e a média da turma antes e depois de aplicar o índice nas notas dos alunos
  12. Implemente que o índice de cada aluno é um valor sorteado entre 0 e 1 (utilize srand() e rand())
  13. Carregue um arquivo com os alunos chamado alunos.txt e salve o relatório completo (com tudo) em um arquivo chamado resultados.txt
  14. Implemente a criação de alunos de forma aleatória para todos os atributos (inclusive os nomes e filiação)

sexta-feira, 8 de maio de 2015

[P9] Alguns dígitos de PI

     O número PI é a relação entre o perímetro de uma circunferência e o seu diâmetro e é bastante estudada em geral. O principal interesse aqui é sobre a obtenção numérica dos dígitos de PI, buscas e aspectos interessantes de serem realizadas. O Dia de PI é 14 de Março, pois em inglês escreve-se 3/14, equivalendo aos primeiros dígitos de PI.
     Para decorar PI, em inglês, basta decorar a seguinte frase e daí contar o tamanho de cada palavra:
May I have a large container of coffee beans
3 1 4 1 5 9 2 6 5

     Como curiosidade, é possível usar a letra grega em HTML para representar PI, por exemplo, π (para maiores informações, consulte o este site).

     A tabela a seguir mostra onde foram obtidos os arquivos dos dígitos de PI:
Tamanho (em dígitos) Local (site)
100.000 http://www.geom.uiuc.edu/~huberty/math5337/groupe/digits.html
10.000.000 http://pi.karmona.com/
100.000.000 https://ia801404.us.archive.org/4/items/Pi_to_100000000_places/pi.txt
Para os cem milhoes, o seguinte foi fornecido:
QPI-Quick Pi v2.90, (c) 2000-2004 S. Pagliarulo
Freely distributable, email: s_pagliarulo@hotmail.com

Intel(R) Pentium(R) 4 CPU 2.53GHz detected
System speed measured at 2.5 GHz
Using custom training data

Computation of Pi to 100,000,000 digits
Method used : Chudnovsky
Started : Fri Dec 16 16:06:49 2005

Series size : 7051368  (100,000,015 digits)
Initialization time : 0.06
Series processing time : 1002.95
Final value time : 225.98

Total time : 1229.00 seconds (20 mins, 29.00 secs)
Total memory used : 639,608,980 (609.98 MB)
CPU utilization : 99.97%

     Mas qual a chance de encontrar números nos dígitos de PI? O site http://www.angio.net/pi/whynotpi.html tenta responder esta pergunta, conforme a seguinte tabela a seguir (as chances foram computadas para 100 milhões de dígitos):

Tamanho do número Chance de encontrar
1-5 100%
6 Quase 100%
7 99,995%
8 63%
9 9,5%
10 0,995%%
11 0,09995%

Computando PI em C


     Existem três métodos (baseado em http://www.codeproject.com/Articles/813185/Calculating-the-Number-PI-Through-Infinite-Sequenc):

1. Wallis's Series (1655) - Double Precision

2. Gregory-Leibniz's Series (1671-1674) - Double Precision

3. Nilakantha's Series (Século XV) - Double Precision


     Um outro método chamado Método de Chudnovsky computa dígitos para PI de forma rápida:

4. Chudnovsky's Method (1989)


     O problema deste método é que é necessário trabalhar com bibliotecas BigInt, ou seja, com grandes inteiros, pois acima de 27, o fatorial começa a ficar muito complicado de ser calculado (como desafio, programe este algoritmo e tente passar de 27).



1. Wallis's Series - Double Precision
// Approximation of the number pi through the Wallis's series
// Language: C
// Author: Jose Cintra (jose.cintra@html-apps.info)

#include <stdio.h>
#include <stdlib.h>

main() {

   double n, i         // Number of iterations and control variable
   double pi = 4;

   printf("Approximation of the number pi through the Wallis's series\n");
   printf("\nEnter the number of iterations: ");    
   scanf("%lf",&n);
   printf("\nPlease wait. Running...\n");

   for(i = 3; i <= (n + 2); i+=2)
      pi = pi * ((i - 1) / i) * (( i + 1) / i);

   printf("\nAproximated value of PI = %1.16lf\n", pi);  

}

2. Gregory-Leibniz's Series - Double Precision
// Approximation of the number PI through the Leibniz's series
// Language: C
// Author: Jose Cintra (jose.cintra@html-apps.info)

#include <stdio.h>
#include <stdlib.h>

main() {

   double n, i;       // Number of iterations and control variable
   double s = 1;      //Signal for the next iteration
   double pi = 0;

   printf("Approximation of the number PI through the Leibniz's series\n");
   printf("\nEnter the number of iterations: ");    
   scanf("%lf",&n);
   printf("\nPlease wait. Running...\n");      

   for(i = 1; i <= (n * 2); i += 2) {
     pi = pi + s * (4 / i);
     s = -s;
   }

   printf("\nAproximated value of PI = %1.16lf\n", pi);  

}

3. Nilakantha's Series - Double Precision
// Approximation of the number pi through the Nilakantha's series
// Language: C
// Author: Jose Cintra (jose.cintra@html-apps.info)

#include <stdio.h>
#include <stdlib.h>

main() {
   double n, i;    // Number of iterations and control variable
   double s = 1;   //Signal for the next operation
   double pi = 3;

   printf("Approximation of the number PI through the sequence of the Nilakantha's series\n");
   printf("\nEnter the number of iterations: ");
   scanf("%lf",&n);
   printf("\nPlease wait. Running...\n");

   for(i = 2; i <= n*2; i += 2) {
     pi = pi + s * (4 / (i * (i + 1) * (i + 2)));
     s = -s;
   }
   printf("\nAproximated value of PI = %1.16lf\n", pi);
}

Dados

     Existem quatro arquivos para baixar:
  1. a1-cem-mil-digitos-de-PI.txt: como o nome diz, possui cem mil dígitos de PI, em 98Kb de tamanho em disco.
  2. a2-dez-milhoes-digitos-de-PI.txt: este arquivo contém dez milhões de dígitos de PI, com aproximadamente 9,8Mb de tamanho.
  3. a3-cem-milhoes-digitos-de-PI.txt: finalmente, cem milhões de dígitos de PI, ocupando aproximadamente 98Mb.
  4. arquivos dos projetos escritos em C
     Cabe ressaltar que os arquivos com os dígitos de PI em questão possuem apenas uma linha, então tenha *muito* cuidado na hora de carregá-los para a memória!

Questões interessantes deste projeto

Observação: considere sempre que o primeiro dígito a ser usado encontra-se após o 3., ou seja, para PI=3,141592..., o quinto dígito é 9.
  1. Verificar se é verdade que qualquer número de tamanho 3 existe ou não nos 1 milhão de dígitos, ou seja, para todos os números com tamanho 3 (por exemplo, 005, 456, ou 768) entre 000 e 999, verifique sua primeira ocorrência nos dígitos de PI no arquivo de 1 milhão de dígitos
  2. E para a totalidade de números de tamanho igual a 6 (por exemplo, 567333), quantos e quais não existem?
  3. Conte o total de ocorrências deste número de tamanho 3 para todos os 1 milhão de dígitos, fazendo o mesmo para dez e cem milhões
  4. Conte quantas sequências de números idênticos de tamanho 4 e 5 existem nos dígitos de PI. Por exemplo, para o número 7777 ou 55555, quantas ocorrências existem?
  5. Mostre o dígito (caso ocorram) da primeira ocorrência bem como o total de ocorrências das seguintes sequências especiais de números: 0123456789 ou 9876543210, 112233 ou 223344 ou 998877, 000111222 ou 999444111, 0000011111 ou 8888822222, 3141592653 (estes são os primeiros 10 dígitos de PI). Pense em outras e implemente
  6. Para sequências de números pares e ímpares de tamanho igual a 10, conte o total de ocorências nos dígitos de PI (por exemplo, sequências, 0204060810 ou 0602081004)
  7. Procurar ocorrencias de strings baseadas em datas de nascimento (formato ddmmaaaa, mas procure também por mmddaaaa, aaaaddmm, aaaammdd) em todos os arquivos, contando o total de ocorrências existente
  8. Mostrar uma determinada sequência de dígitos de PI, onde é passada uma posição qualquer (por exemplo, 495959) e uma função mostrando os N dígitos anteriores e os M dígitos posteriores (inclusive a sequência)
  9. Procure o total de ocorrências de números primos (começando em I e percorrendo até J) nos primeiros K dígitos dos cem milhões de dígitos de PI. Por exemplo: para os números primos compreendidos entre 1000 e 10000, busque suas ocorrências em PI
  10. Faça uma função que salva N novos arquivos dos dígitos de PI contendo M caracteres cada (padrão de nomes: PI_i.txt)
  11. Faça um arquivo chamado PI-colunas.txt contendo N linhas e M colunas onde os primeiros K dígitos de PI são utilizados. Por exemplo, para tamanho de coluna igual a 3, linha igual a 3 e os primeiros 27 dígitos, ficaria:
    1. 141 592 653
    2. 589 793 238
    3. 462 643 383
  12. Para cada dígito de 0 a 9, conte quantas ocorrências existem nos primeiros N dígitos de PI (tente contar no arquivo com cem milhões de dígitos)
  13. Faça uma função onde é passado um total de dígitos totais N, um valor K e um valor M e esta pega os primeiros N dígitos de PI e cria um arquivo com M linhas e tamanho de coluna igual a K (esta é uma combinação de funções implementadas anteriormente)
  14. Compute as seguintes funções geométricas com o valor de PI com diferentes precisões mostrando as diferenças nas respostas (seja π o valor de PI com diferentes precisões (cuidado) e r o valor do raio)
    1. Área de um círculo: Ac = π*r2
    2. Perímetro de um círculo: Pc = 2*π*r
    3. Área de uma esfera: Ae = 4*π*r2
    4. Volume de uma esfera: Ve = 4*π*r3/3


sexta-feira, 24 de abril de 2015

[P8] Nascimentos e mortes por dia do ano


     Existem 122.069 nascimentos e mortes (86.975 nascimentos e 35.094 mortes) disponíveis publicamente na Wikipedia (dados atualizados até 31/12/2014). São informações de pessoas que a enciclopédia on-line pensa ser relevante, como políticos, artistas, músicos, arquitetos, enfim, pessoas que possuem entradas no site relatando algum acontecimento extraordinário em suas vidas. Veja por exemplo os dados do dia 1o. de Janeiro ou 31 de Dezembro (os nascimentos e mortes estão listados no final da página).

Dados

     A listagem a seguir mostra o primeiro e o último registro do arquivo para explicar seu cabeçalho:
Birth/Death;Date;Name,Observation
B;01/01/871;Zwentibold, Frankish son of Arnulf of Carinthia (d. 900)
...
D;31/12/2009;Justin Keating, Irish surgeon, and politician (b. 1930)

     O primeiro registro do arquivo é um nascimento (B, ou birth) e o último registro é uma morte (D, ou death). O arquivo mostra a data de nascimento/morte (formato DD/MM/AAAA) separando os dados por ';'. A ordem dos registros é por data, da menor para a maior.

     Um dos desafios ao se trabalhar com estes dados não dizem respeito à data de nascimento ou morte, mas sim a desestruturação existente quanto a observação que foi feita na página da Wikipedia (no arquivo, equivale ao campo Name,Observation). Por exemplo, existem muitas atividades realizadas pelas pessoas, o que dificulta a análise do arquivo, bem como o local de nascimento. As vezes, na morte, é indicada a data de nascimento e vice-versa e, às vezes, nada é informado.

Gentílicos e adjetivos pátrios

     Gentílicos e adjetivos pátrios são classes de palavras que indicam o local de nascimento ou morte de uma pessoa (para maiores informações, entre nesta página da Wikipedia). O arquivo com os nascimentos e mortes possuem uma série de denominações do país de nascimento e morte das pessoas relacionadas, então será útil para descobrir os países que fazem parte da listagem e suas quantidades (ambas as listagens estão em inglês). Os gentílicos e adjetivos pátrios, em inglês, são chamados de Demonym (http://en.wikipedia.org/wiki/Demonym).

Dados

     Existem três arquivos principais para baixar:
  • nascimentos-e-mortes.txt: listagem dos nascimentos e mortes obtidos da Wikipedia (em inglês)
  • gentilicos.txt: arquivo contendo os adjetivos pátrios (em inglês)
  • datas-comemorativas-brasil.txt: arquivo contendo todas as datas comemorativas (dias normais, ou seja, dias úteis) e os feriados oficiais do Brasil (em português)
     Cuidado: pode haver mais de um gentílico por país (por exemplo, Argentinian, Argentinean ou Argentine).
     Salve os arquivos neste link (2.35Mb).

Questões interessantes deste projeto
  1. Faça um relatório geral dos seguintes dados do arquivo:
    1. Por dia do ano, de 1/Janeiro a 31/Dezembro, quantos nascimentos e quantas mortes existem no arquivo (separe o total por tipo)?
    2. Qual é o dia que mais possui nascimentos e qual possui mais mortes? (dias mais férteis e dias mais sangrentos)
    3. Qual é o mês que mais possui nascimentos e qual possui mais mortes? Ordene do maior para o menor
    4. Qual dia possui menos nascimentos e qual possui menos mortes?
    5. Qual mês possui menos nascimentos e qual possui menos mortes?
    6. Qual é o percentual de nascimentos e mortes em relação ao total da listagem?
  2. Mostre o número total de pessoas nascidas conforme as seguintes profissões (liste o total por profissão): polititian, photographer, author, mathematician, actor, actress, singer, songwriter, poet, journalist, football player, baseball player, soccer player, tennis player, illustrator, boxer, comedian, screenwriter, composer, cyclist, geographer, activist
  3. Descubra o país de cada nascimento de cada pessoa do arquivo (utilize o arquivo auxiliar de gentílicos). Cuidado: às vezes, o país é duplo, por exemplo, English-American ou Indian-Bangladeshi
  4. Mostre a contagem de pessoas por país usando a listagem de gentílicos, ordenando da maior para a menor
  5. Mostre em uma listagem todos os nascimentos e mortes de pessoas nascidas nos Estados Unidos (American e derivados, por exemplo, Canadian-American ou Chinese-American) com profissão igual a actor ou actress, ordenando por ano de nascimento
  6. Para as pessoas no arquivo que possuem uma data de nascimento E uma data de morte, mostre uma listagem com o nome e o total de anos que ela viveu
    1. Mostre o total em anos, indicando quantos dias faltariam para seu próximo aniversário
    2. Mostre também o total de meses, dias, horas e minutos vividos
  7. Mostre o total de Sir e Madame existentes e o intervalo entre cada morte, ordenada por ano de forma crescente
  8. Mostre o nome completo das pessoas com King no nome (em qualquer lugar, podendo ser no meio do nome, por exemplo, Stephen Hawking
  9. Para todas as profissões com player, liste apenas o nome, a profissão e o ano de nascimento em um novo arquivo, chamado player.txt
  10. Coloque todas informações (data de nascimento e morte, nome, profissão) das pessoas nascidas no Brasil (Brazilian e derivados, por exemplo, Brazilian-French) em um arquivo chamado brazilian.txt
    1. [DESAFIO] Faça um arquivo por país conforme a lista de gentílicos, com nome igual ao nome do gentílico
  11. Liste as informações das pessoas com apelidos no nome, por exemplo, Yolanda "Tongolele" Montes
  12. Construa uma tabela mostrando os 5 países que mais possuem entradas no arquivo em nascimentos, listando o nome do país e o total de nascimentos e mortes. Faça outra tabela com as mesmas características mostrando as mortes
  13. Mostre as informações completas (nome, datas, observações) de todas as pessoas santas (ou seja, com observação igual a Saint)
  14. Para todos os primeiros nomes do arquivo, construa uma listagem mostrando o total de ocorrências de cada nome e salve-a em um arquivo chamado nomes-pessoais.txt (ordene a listagem por ordem crescente do total de nomes)
  15. Usando o arquivo datas-comemorativas-brasil.txt:
    1. Liste, para cada feriado (no arquivo marcado com a letra F), o total de pessoas nascidas e o total de mortes, ordenando a listagem produzida pelo dia com o maior número de ocorrências até o menor
    2. Mostre o total de pessoas nascidas em dias normais (que não são feriados, marcadas no arquivo pela letra N). Informe também o total de pessoas nascidas e mortas por dia
  16. Mostre todas as informações das pessoas que tem o gentílico Frankish. Os francos (wikipedia: http://en.wikipedia.org/wiki/Franks) foram uma tribo da europa.
  17. Mostre o número de nascimentos e mortes por país
  18. [DESAFIO] Crie uma nova listagem de nascimentos e mortes (chamada listagem.txt conforme o seguinte formato: Dia de nascimento;Dia de morte;Nome completo;Pais;Profissao. Faça isso apenas para as entradas completas, ou seja, que possuem dia de nascimento e morte, um país da lista de gentílicos e pelo menos uma profissão (escolha uma profissão para salvar na nova listagem). Ordene pelo dia de nascimento

sexta-feira, 10 de abril de 2015

[P7] Sobrenomes da língua portuguesa


     Indiscutivelmente, Portugal no Século XV foi uma potência naval. No mapa-múndi, Portugal é um país de proporções pequenas e encontra-se encravado em um pequeno estreito de terras no oeste da Europa. Os grandes (e corajosos) navegadores portugueses circularam o mundo levando a sua cultura por onde passavam, influenciando o globo terrestre. Hoje em dia, a língua portuguesa é falada em pelo menos 10 países, por aproximadamente 269 milhões de pessoas, muito mais que as 11 milhões de pessoas de Portugal de onde tudo se originou. As línguas românicas são hoje faladas em muitos locais (Itália, França, Espanha, Romênia, etc) sendo estas derivadas do latim (e latim vulgar), com influências de muitas línguas (no Brasil, inclusive, as línguas dos índios foram mescladas no português brasileiro).
     Os historiadores marcam que o Império Português durou de 1415 (Conquista de Ceuta, no norte da África) até 1999 (com a entrega de Macau), ou seja, 584 anos (o Brasil tem em 2015 apenas 515 anos).

Curiosidades

     O português é a língua oficial dos seguintes países (dados obtidos em Wikipedia em 15/03/2015, e ordenados por população):

País População(*) Percentual (%)
Brasil 202.656.788 75,3% 93,5%
Moçambique 24.692.144 9,2%
Angola 24.300.000 9,0%
Portugal 10.813.834 4,0% 6,5%
Guiné-Bissau 1.693.398 0,6%
Goa (Índia) 1.457.723 0,5%
Timor-Leste 1.201.542 0,4%
Guiné-Equatorial 722.254 0,3%
Macau 587.914 0,2%
Cabo Verde 538.535 0,2%
Índia Damão e Diu (Índia) 242.911 0,1%
São Tomé e Príncipe 190.428 0,1%
Total 269.097.471 100%
(*) baseando-se em estimativas populacionais.






     A imagem a seguir explica os dados acima, onde o Brasil detém 75,3% da população total de falantes da língua portuguesa. Angola e Moçambique vem logo a seguir, com 18,2% dos falantes e estes três países tem 93,5% do total.


     A figura a seguir mostra o mapa-múndi e os países que falam português, destacando-se Portugal.

     A próxima figura detalha a zona de influência do português ao redor do mundo. Tirando a área do mar da figura (33 milhões de km2, aproximadamente), a área possui 11 milhões de km2 (olhar próxima tabela), o que é bastante considerável em relação ao resto do mundo (estes números não são exatos, mas fornecem uma ideia da área aproximada de pessoas que estão falando português).

Dados

     Os dados a seguir listam os primeiros 200 sobrenomes dos países que falam português, obtidos no site http://forebears.io/. A tabela a seguir lista as siglas utilizadas no arquivo (estes dados também estão comentados no cabeçalho) relacionando-as com o país (no primeiro arquivo). O segundo arquivo contém 1951 sobrenomes gerais (sem origem definida).

     Faça o download dos seguintes arquivos:
  1. 200 sobrenomes mais comuns em países de língua portuguesa (arquivo sobrenomes-lingua-portuguesa.txt)
  2. Outros 1951 sobrenomes (arquivo sobrenomes-gerais.txt)
     Legenda dos sobrenomes do arquivo sobrenomes-lingua-portuguesa.txt:
Sigla País/RA* Área (km2)
BRA Brasil 8.515.767
ANG Angola 1.246.700
MOZ Moçambique 801.590
POR Portugal 92.090
GUI Guiné Bissau 36.544
MAU Macau 28.600
EQU Guiné Equatorial 28.051
TIM Timor Leste 15.007
CAB Cabo Verde 4.033
- Goa** 3.702
SAO São Tomé e Príncipe 1.001
Total 10.773.085
Área Mundial 149.000.000
(*) Região Administrativa
(**) Para Goa não existem dados relativos à sobrenomes

Questões interessantes deste projeto
  1. Qual é o sobrenome mais comum de cada país (a partir do arquivo dos 200 sobrenomes mais comuns)?
    1. Quais são os menores (em número de caracteres) e maiores (idem) sobrenomes de cada país?
  2. Por ordem alfabética, qual é o número total de sobrenomes existentes de cada letra? (por exemplo: sobrenomes com 'A': 3.444.200, ...)
  3. A listagem fornece um total de pessoas com um sobrenome específico. Qual é o sobrenome (entre todos os países) com o maior número de pessoas?
  4. Para a listagem fornecida, quantas pessoas no total estão contadas nas listagens de sobrenome?
  5. Qual é o percentual de pessoas listadas no arquivo em relação à população de cada país?
  6. Separe o arquivo original em um arquivo de sobrenome por país, colocando a sigla no cabeçalho e informando o nome do arquivo como sendo a sigla com terminação .txt
  7. Construa um arquivo novo ordenando pelo maior número de sobrenomes da listagem, preservando a sigla do país (também ordenada alfabeticamente)
  8. Crie um novo arquivo de dados (chamado sobrenomes-unicos.txt) contendo a listagem de sobrenomes únicos (retira os sobrenomes repetidos, e somam-se os totais dos sobrenomes de cada país), sem a sigla
  9. Qual é o sobrenome com o maior número de caracteres de cada país?
  10. Para cada sobrenome de cada país, mostre o percentual deste em relação à população total do país (use a tabela acima que mostra a população)
  11. Quais são os sobrenomes em comum entre todos os países? (se é que existe algum - se não existir, mostre o sobrenome em comum com o maior número de países)
  12. Quantos sobrenomes e quantas pessoas possuem hipocorismos (apenas com sufixos -inho e -inha) no nome? Liste-os.
  13. Quantos sobrenomes são patronínicos, ou seja, terminados em ES (significando 'filho de'), em IZ (idem)? Liste-os, bem como a população por país que os possui
  14. Análises sobre os dois arquivos de sobrenomes do problema
    1. Quais e quantos sobrenomes em comum existem nos dois arquivos?
    2. Qual país possui o maior número de sobrenomes nos dois arquivos?
    3. Quais sobrenomes do arquivo de nomes gerais (o segundo arquivo) não existem nos 200 sobrenomes (primeiro arquivo) de qualquer país?
    4. Quantos habitantes que falam português existem por metro quadrado em cada país? (ordene a lista do maior para o menor número)

sexta-feira, 27 de março de 2015

[P6] Brincando com Cadeias de Markov


     A modelagem com Cadeias de Markov está na sua simplicidade: apenas estados e transições e frequências de mudança entre os estados. O simples é facilmente entendível, necessário em muitos aspectos e fundamental. As seguintes frases representam bem este sentimento, aplicável a diversas esferas:

(1) "The KISS (Keep it simple, stupid) Principle."
(2) "Less is more."
(3) "Perfection is achieved, not when there is nothing more to add, but when there is nothing left to take away." - Antoine de Saint-Exupery
(4) "If you can't explain it to a six year old, you don't understand it yourself." – Albert Einstein
(5) "Simplicity is the ultimate sophistication." - Creditada a Leonardo da Vinci, apesar de não existir nenhum local indicando o mesmo.

     A seguir, utilizando estes princípios, é mostrado um estudo sobre as Cadeias de Markov, idealizadas por Andrey Andreyevitch Markov, circa 1905.
     O conceito chave de Cadeias de Markov deve ser obrigatoriamente simples de entender e modelar. Qualquer pessoa com conhecimentos básicos de Álgebra Linear (sim, será necessário...), abstração e criatividade pode utilizar as premissas simples de Cadeias de Markov para modelar e trabalhar com sistemas mais complexos e intrincados, realizando diversas análises e entendendo sua operação fundamental.
     A principal ideia por trás da modelagem Markoviana é considerar um sistema como tendo um espaço de estados bem definido com transições entre os estados e a passagem entre os estados não tem memória (memoryless property), ou seja, para chegar em um estado, não importa os estados visitados anteriormente, apenas os estados possíveis a partir do estado atual (vamos esquecer destes detalhes por enquanto e focar na descrição e solução de um problema).

Os humores do Prof. Steigerschülz

     O Prof. Steigerschülz (lê-se SH-TAY-GUER-SHI-L-TZ), trabalha em uma renomada instituição de ensino superior brasileira e é uma pessoa extremamente simples, inclusive quanto aos seus humores. O professor possui apenas três condições de humor: 'Feliz' (F), 'Irritado' (I) e 'Pensativo' (P). Um dos seus alunos resolveu documentar as mudanças de humor do Prof. Steigerschülz e chegou às seguintes conclusões:

(i) quando o professor está feliz, 30% das vezes ele fica irritado e 40% ele entra em um modo introspectivo de amplo pensamento (o professor chama este estado de profundo PENSO, e não gosta de ser importunado). No resto das vezes (30%) ele permanece feliz;
(ii) quando o professor está irritado, apenas uma piada faz com ele volte a ficar apenas feliz, em 50% das vezes;
(iii) quando está pensativo, pode ficar feliz (em 70% das vezes) ou irritado (em 30% das vezes);

     O problema é que, apesar de saber as vezes que o professor transita entre os estados, o aluno tem a seguinte dúvida: "chegando para trabalhar em um dia qualquer, dadas as chances verificadas acima, qual é a probabilidade do professor estar feliz, irritado ou pensativo?". Para responder esta pergunta, pode-se modelar o problema com uma Cadeia de Markov, mapeando os estados e as transições possíveis para este problema em particular, como segue:
Estados: F, I e P, respectivamente para Feliz, Irritado e Pensativo.
Transições: matriz M
     O modelo é mostrado na figura a seguir (observe que o modelo possui probabilidades nas transições entre os estados):
     Para criar a Matriz M (também chamada de Matriz de Transição ou Matriz Estocástica) é necessário criar uma matriz quadrada para representar os estados que o Prof. Steigerschülz assume:

M=
  F I P
F 0,3000 0,3000 0,4000
I 0,5000 0,5000 0,0000
P 0,7000 0,3000 0,0000

     A ideia é simular o dia-a-dia do professor e tentar encontrar um regime onde não existem mais mudanças (não é garantido que isto será conseguido, pois as cadeias devem ser ergódicas), ou seja, estimando seu comportamento no infinito. Para fazer isso, podem ser usados Métodos Diretos (Método de Gauss, fatoração LU, etc) ou Iterativos (Método da Potência, Subespaços de Krylov - Arnoldi, GMRES - etc) de solução (olhar a referência PHILIPPE 1989).
     Nesta postagem será utilizada a técnica de elevar uma matriz à sua enésima potência (URGENTE: revisar multiplicação entre matrizes de mesma ordem), como mostrado a seguir (estão sendo mostrados os valores arredondando para 4 casas após a vírgula, para simplificação do método - utilize o máximo de precisão sempre).

M2=
  F I P
F 0,5200 0,3600 0,1200
I 0,4000 0,4000 0,2000
P 0,3600 0,3600 0,2800
 
M3=
  F I P
F 0,4576 0,3744 0,1680
I 0,4400 0,3760 0,1840
P 0,4320 0,3744 0,1936





M4=
  F I P
F 0,4467 0,3750 0,1783
I 0,4463 0,3750 0,1787
P 0,4461 0,3750 0,1789
 
M5=
  F I P
F 0,4464 0,3750 0,1786
I 0,4464 0,3750 0,1786
P 0,4464 0,3750 0,1786

     Observe que ao elevar a matriz à quinta potência (M5), os valores das linhas já não se alteram mais. Este é o resultado (corresponde ao eigenvector, ou autovetor, da matriz em questão), e demonstra as probabilidades de permanência de cada estado do professor:
     Isto quer dizer que o Professor Steigerschülz está Feliz mais ou menos 45% (44,64% ou 0,4464) do seu dia (ou mês, ou ano). Mas, existe uma probabilidade não irrisória de 38% (37,50% ou 0,3750) do professor estar Irritado e, tecnicamente, não deveria ser importunado. Por fim, em 18% (17,86% ou 0,1786) do tempo, ele está Pensativo, ou seja, uma baixa probabilidade do professor estar em um estado de pensamento puro.

Questões relativas à solução e ao desempenho do processo

     De uma maneira relativamente simples, foi construído um modelo que foi resolvido e teve seus resultados obtidos. Entretanto, por mais interessante que seja a abordagem de elevar uma matriz à sua enésima potência, ela é computacionalmente custosa, pois consome muitos recursos (muitas multiplicações e somas cada vez). Isso é uma pena pois a convergência deste modelo em particular foi atingida logo na quinta potência, evidenciando o fato que este processo encontra resultados rapidamente, mas é custoso em termos de recursos dispendidos.
     Cabe ressaltar que a matriz dos modelos desta postagem possuem baixa ordem, ou seja, matrizes com poucas células, por exemplo, 3x3 (3 linhas e 3 colunas). Pense que o modelo do Professor Steigerschülz poderia considerar toda a gama das suas emoções, aumentando a ordem da matriz consideravelmente.
     Logo, é necessário que se pense em uma maneira alternativa de calcular estas probabilidades sem gastar muitos recursos computacionais. A técnica mostrada aqui consiste em multiplicar um vetor de probabilidades por uma matriz de transição (soma das linhas igual a 1). O vetor de probabilidades inicial pode ser arbitrário (ou seja, pode ser representado por quaisquer valores diferentes de zero) e uma matriz de transição M (que já tínhamos antes). Ao realizar este processo iterativamente, usando o vetor como entrada e calcular quando este não mais varia, chega-se às probabilidades de permanência de cada estado, ou seja, o nosso objetivo.

     Então, vamos utilizar a mesma matriz M definida anteriormente, mas desta vez, vamos criar um vetor de probabilidades inicial V, como mostrado abaixo.
Vetor de probabilidades inicial - V
1,0000 0,0000 0,0000

     Vamos utilizar este vetor V para multiplicar a matriz iteradas vezes (onde busca-se um vetor estacionário de probabilidades, ou seja, um vetor que ao ser multiplicado por uma matriz resulta no próprio vetor), usando o vetor como entrada de dados a cada iteração e observando um resíduo entre cada iteração do método (vamos supor 0,0002, ou seja, quando a diferença de cada elemento do vetor da iteração i menos o vetor da iteração (i-1) for menor que 0,0002 - neste caso, pois normalmente o resíduo é da ordem de 0,000000001). Nota: a função ABS retorna o valor absoluto de um parâmetro.
Iteração Vetor de probabilidades - V Resíduo Total
ABS(Vi,j - Vi-1,j)
0 1,0000 0,0000 0,0000 1,4000
1 0,3000 0,3000 0,4000 0,5600
2 0,5200 0,3600 0,1200 0,2000
3 0,4200 0,3720 0,2080 0,0800
4 0,4576 0,3744 0,1680 0,0310
5 0,4421 0,3749 0,1830 0,0124
6 0,4482 0,3750 0,1768 0,0050
7 0,4457 0,3750 0,1793 0,0020
8 0,4467 0,3750 0,1783 0,0008
9 0,4463 0,3750 0,1787 0,0004
10 0,4465 0,3750 0,1785 0,0002
11 0,4464 0,3750 0,1786 -

     Com um processo um pouco diferente, mas computacionalmente menos custoso, chega-se aos mesmos resultados de antes: o vetor de probabilidades final contém as probabilidades de permanência. Foram necessárias 11 iterações de multiplicações entre um vetor e uma matriz. Como a matriz é pequena, o ganho não é muito aparente, mas, à medida que a matriz aumenta, os custos começam a ficar bem mais interessantes.

Tipos de Cadeias de Markov

      As Cadeias de Markov vistas no exemplo do Professor Steigerschülz são conhecidas por serem definidas utilizando-se uma escala de tempo discreta (ou Discrete Time Markov Chains, DTMC). Isso quer dizer que o sistema evolui conforme passos discretos bem definidos (por isso que é dito que o tempo passa de forma discreta). O exemplo anterior modela um sistema que evolui conforme probabilidade em cada estado assumido pelo professor, entretanto, uma outra forma de modelagem Markoviana é possível, utilizando-se uma escala de tempo dita contínua (ou Continuous Time Markov Chains, CTMC), onde as transições entre os estados mapeiam taxas e a passagem do tempo segue premissas da distribuição exponencial (que é memoryless).
      Em termos de solução numérica, o procedimento é bem parecido, exceto que a matriz não é mais de probabilidades e sim de taxas e a diagonal principal da matriz contém a soma das taxas de saída de cada estado de forma negativada, ou seja, a linha soma zero. Estas matrizes especiais são chamadas pelo nome pomposo de Gerador Infinitesimal Q.

Matriz Exemplo
       
       
       
       

      Para resolver esta matriz, será necessário utilizar o conceito de Matriz Identidade. Uma matriz identidade possui valores iguais a 1 na diagonal principal e 0 nos demais elementos, conforme mostrado a seguir:

Matriz Identidade I3 (ordem 3)
1 0 0
0 1 0
0 0 1

      A ideia é modelar um sistema com taxas entre os estados, criar uma matriz que mapeie estas transições, modificar a diagonal principal para conter a soma das taxas negativadas e depois aplicar um mecanismo de solução numérica.
      Considere o seguinte problema: um aluno possui três estados, trabalhando (T), estudando (E) e surfando na internet (I). Observou-se que este aluno em questão visita os estados conforme taxas ou frequências (estes dados foram obtidos a partir de observações ou logs de entrada em laboratórios de estudo/Internet, etc), que aconteceram conforme uma unidade de tempo (horas, minutos ou dias).

     A figura a seguir explica o modelo (observe que existem taxas nas transições entre os estados). Pode-se pensar, por exemplo, que o aluno em questão, em uma hora (ou outra unidade de tempo qualquer), vai de Estudando para Internet com uma frequência de 30 vezes (também pode-se considerar tempo em cada estado, uma vez que Tempo=1/Frequência).
     As taxas com que este aluno visita os estados estão definidas na matriz a seguir.

Matriz de Taxas T
  Trabalhando  Estudando      Internet    
Trabalhando   10 20
 Estudando  5   30
Internet 7 8  

     Para transformar esta Matriz de Taxas T em um Gerador Infinitesimal Q (onde a diagonal contém a correção das taxas do modelo) precisamos somar os valores das taxas da linha e colocar este número na diagonal, de forma negativada, conforme a matriz a seguir:

Gerador Infinitesimal Q
  Trabalhando  Estudando      Internet    
Trabalhando -30 10 20
 Estudando  5 -35 30
Internet 7 8 -15

     A ideia agora é criar uma nova matriz, onde a soma das linhas é igual a 1, usando a matriz identidade. Então, segue-se a seguinte operação: cada célula desta nova matriz contém o valor da célula correspondente da Matriz Identidade menos o valor da célula da matriz sendo calculada dividido pelo maior valor da matriz (em módulo). O maior valor (em módulo) da matriz certamente encontra-se na diagonal. Neste caso, o maior valor (em módulo), ou MAXij=-35 encontra-se na linha 2 e coluna 2.

Matriz de Transição M
0,1429 0,2857 0,5714
0,1429 0,0000 0,8571
0,2000 0,2286 0,5714

     Por exemplo, vamos calcular juntos a célula M00 que corresponde à célula da primeira linha e primeira coluna: equivale a pegar o valor da célula da matriz identidade (que é igual a 1), menos o valor da célula (-30) dividido por (-35).
Isso é igual a 1-(-30/-35)=1-30/35=1-0,8571=0,1429.
     Observe que esta nova matriz é uma matriz onde a soma das linhas é igual a 1, ou seja, voltamos ao problema anterior das Cadeias de Markov do tipo DTMC, onde a solução foi descrita anteriormente. Então, usa-se um método numérico de solução, ou seja, eleva-se a matriz à uma potência ou pode-se utilizar a multiplicação de um vetor de probabilidades (que guarda o resultado) por uma matriz de transição. A seguir é mostrado a operação de elevar a matriz à uma potência:

M2=
  T E I
T 0,1755 0,1714 0,6531
E 0,1918 0,2367 0,5714
I 0,1755 0,1878 0,6367
 
M3=
  T E I
T 0,1783 0,1933 0,6284
E 0,1794 0,1962 0,6244
I 0,1786 0,1941 0,6273
 
M4=
  T E I
T 0,1787 0,1944 0,6270
E 0,1787 0,1944 0,6270
I 0,1787 0,1944 0,6270

     Este é o resultado, e demonstra as probabilidades de permanência de cada estado do professor:

Probabilidades de permanência (resultado)
Trabalhando 17,87%
Estudando 19,44%
Internet 62,70%
     Os resultados mostram que o aluno em questão encontra-se aproximadamente 63% do seu tempo surfando na Internet e o resto do tempo mais ou menos dividido entre Trabalhando (18%) e Estudando (20%). Esta análise não era clara antes de modelar o problema em uma Cadeia de Markov e solucionar o problema obtendo as probabilidades de permanência de cada estado. Isso demonstra o poder e a simplicidade do formalismo.
     Pode-se utilizar a multiplicação do vetor de probabilidades pela matriz de transição para resolver o problema, assim como poderia ter sido utilizado um método direto ou outro método iterativo.

Como replicar estes resultados de forma fácil

     É possível replicar tudo que foi feito nesta postagem utilizando-se uma ferramenta específica para este propósito (Matlab, Maple, Matematica ou resolvedor próprio de Cadeias de Markov) ou então utilizando-se o MS-Excel ou qualquer planilha eletrônica que forneça operações com matrizes.
     Aqui, a ferramenta a ser utilizada é o MS-Excel, e a ideia é utilizar a função MATRIZ.MULT().
     Para este exemplo, estou assumindo que você já está trabalhando com a matriz na forma DTMC (soma das linhas igual a 1). Depois de criar uma matriz, vamos supor, nas células D3:F5, vamos selecionar nove células em branco (em outro local da planilha), vamos supor, D7:F9, apertar a tecla F2 e inserir a fórmula =MATRIZ.MULT(D3:F5;D3:F5) e então, magicamente, apertar a sequência de teclas CTRL-SHIFT-ENTER. Estas teclas realizam a operação da multiplicação de matrizes no MS-Excel. Faça isso até a matriz não variar mais nas linhas. Você chegará aos resultados apresentados aqui. O mesmo procedimento pode ser feito para realizar a operação da multiplicação do vetor pela matriz.
OBSERVAÇÃO: no MS-Excel, você *deve* selecionar as células em branco - onde serão calculados os novos valores da matriz - e então apertar F2, inserir a fórmula e teclar CTRL-SHIFT-ENTER. Se estes passos não forem seguidos, não funcionará!

Implementando seu próprio resolvedor

     Implementar um resolvedor de Cadeias de Markov é simples. Basta criar um formato de entrada para receber matrizes descritas com modelos Markovianos do tipo DTMC ou CTMC e entrar outras informações secundárias (mas não obrigatórias), tais como a descrição dos estados. Por exemplo, a seguir, é mostrado um esboço de formato de entrada (arquivo chamado markov.txt):
#FELIZ
#IRRITADO
#PENSATIVO
0.3 0.3 0.4
0.5 0.5 0.0
0.7 0.3 0.0
     Para facilitar, observe que a entrada de dados está no formato americano, com pontos ao invés de vírgulas. Isso facilita a leitura do arquivo, pois este já se encontra com os valores necessários.
     Você precisa fazer a consistência dos dados de entrada, por exemplo, duas consistências obrigatórias seriam (1) o número de descrições de estados equivalem ao total de estados informados? (três linhas e três colunas); (2) a soma das linhas fecha 1? Caso estes problemas sejam detectados, você deve informar ao usuário. Outros problemas que talvez aconteçam é a divergência do modelo. Para contornar este problema, você deve implementar o conceito de total de iterações, que o usuário pode passar no arquivo (#iteracoes=1000) ou pela linha de comando (./markovsolver 1000 para o GNU/Linux). A seguir, é mostrado um exemplo onde passam-se outros parâmetros para o resolvedor:
#iteracoes=1000
#residuo=0.0000001
#precisao=2
...
     A saída poderia ser um arquivo ou a tela, contendo os resultados obtidos:
O modelo obteve a convergência em 15 iterações 
e os resultados estão apresentados a seguir:
FELIZ=44,64%
IRRITADO=37,50%
PENSATIVO=17,86%
Tempo de execução: 00m15s user time
Data: 23/03/2015 09:22:05
     Ou então: "Para X iterações, não foi obtida a convergência do modelo".
     Para os modelos CTMC, não é necessário informar os valores da diagonal principal, já que estes podem ser calculados diretamente por você no programa.
#iteracoes=1000
#residuo=0,0000001
#precisao=2
0 10 20
5 0 30
7 8 0
     O ideal é o seu programa identificar se o modelo é DTMC (soma das linhas é igual a 1) ou CTMC (matriz de taxas). Para resolver o modelo, utilize sempre a técnica iterativa do Método da Potência usando a multiplicação de um vetor por uma matriz. Se for uma CTMC, você deve calcular a diagonal principal, negativá-la e então retirar a matriz identidade e dividir cada célula pelo maior valor (em módulo) da matriz. Se isso não for feito, a solução não funcionará.

Considerações especiais

     A pesquisa em Cadeias de Markov evolui constantemente onde pesquisadores trabalham com formalismos ditos estruturados que trabalham com representações de sistemas situadas acima das Cadeias de Markov, ou seja, definem um formato de descrição de sistemas que gera uma Cadeia de Markov (underlying Markov Chain). Estes formatos permitem a fácil decomposição de sistemas e utilizam primitivas básicas de modelagem que auxiliam os usuários a mapear e entender sistemas complexos, além das análises proporcionadas. Exemplos de tais formalismos são as Redes de Petri Estocásticas, as Álgebras de Processos de Sistemas e suas variações, como Redes de Petri Coloridas, Superpostas, Generalizadas, entre outros exemplos.
     Cada formalismo estruturado apresenta e explica sua lista de primitivas de modelagem e uma técnica específica de solução do modelo. Por exemplo, as Álgebras de Processo combinam os estados dos seus inúmeros processos em uma grande Cadeia de Markov onde os usuários podem usar qualquer ferramenta matemática de solução (por exemplo, GNU/Octave, Matlab, Maple, Matematica, etc). Outros formalismos concentram-se em mecanismos que representam a grande Cadeia de Markov de forma eficiente em memória, utilizando por exemplo, Descritores Markovianos.
     Existem muitas pesquisas correntes em formalismos estruturados baseados em ideias de Cadeias de Markov e palavras-chave são: structured stochastic formalism, process algebra e stochastic petri nets.

Epílogo

     Cadeias de Markov são amplamente utilizadas e empregadas em diversos contextos e domínios de aplicação, desde economia até o Algoritmo principal executado pelo Google (chamado de PageRank, mas isso é uma história para outra postagem...).
     Pesquisadores ao redor do mundo estudam Cadeias de Markov e processos Markovianos com aplicação, por exemplo, em Sistemas Paralelos e Distribuídos, biologia marítima, química, física de multidões, e muitas outras aplicações.
     Se você se interessou pelo assunto, procure na Internet outras informações sobre Cadeias de Markov.
     Alguns links interessantes sobre o assunto:
1. Markov Chains @ Khan Academy
2. Material sobre Cadeias de Markov bem explicativo (em inglês)
3. Gerador de textos
4. Markov and You
... ...

Referências

(PHILIPPE et al. 1989) Bernard Philippe, Yousef Saad, William Stewart. Numerical methods in Markov chain modeling. [Research Report] RR-1115, 1989. . Disponível em HAL

Questões interessantes deste projeto
  1. Crie as estruturas de dados para trabalhar com vetores de alta-precisão (double) e matrizes
  2. Faça uma função que testa se uma matriz tem a soma das linhas iguais a 1,0000
  3. Implemente a leitura de um arquivo de entrada (modelo.txt) e a saída em um arquivo contendo os resultados da convergência ou divergência do modelo (mesmo nome de entrada com terminação .out, por exemplo, modelo.out)
  4. Eleve uma matriz à uma potência qualquer (se a soma das linhas for igual a 1,0000)
  5. Eleve uma matriz até que cada linha da matriz não é mais alterada conforme um resíduo igual a 0,00000001, ou informado em um arquivo de entrada (o resíduo é verificado quando a diferença entre os valores das linhas não excede um valor predeterminado, como 0,00000001)
  6. Faça uma função que multiplica, iteradas vezes (até que o vetor não é mais alterado conforme um resíduo - mesmo do item anterior), não deixando que o método ultrapasse X iterações, onde X é informada em um arquivo de entrada (caso ultrapasse, avisar o usuário)
  7. Faça uma função que lê um arquivo contendo uma matriz de um modelo Markoviano (DTMC ou CTMC - você deve decidir o que a matriz é em tempo de execução e converte-la caso necessário) e retorna o vetor de probabilidades de permanência caso exista convergência até 1000 iterações
  8. Faça as funções para um valor de iterações configurável (ITER=1000, mas podendo variar), passando por linha de comando ou por arquivo de entrada
  9. Faça os resultados aparecerem em um novo arquivo gerado pela sua ferramenta
  10. Implemente uma ferramenta visual para abrir modelos e resolver Cadeias de Markov (dica: usar o wxWidgets)