Neste curso sobre matrizes de Markov o ênfase principal vai ser dado aos modelos de aplicação das cadeias de Markov, em que as matrizes são um dos principais protagonistas. Os outros protagonistas são os vetores de estado, que contêm, por exemplo a informação sobre a probabilidade de estar sol ou nuvens num determinado dia, ou ainda a distribuição da população entre a cidade e os arredores numa dada região.
Um dos objetivos deste curso será descrever e simular o procedimento do Google, PageRank, enquanto motor de busca, para ordenar por importância as páginas da Internet quando se faz uma pesquisa sobre um determinado tópico. Com este fim, vamos usar conceitos e propriedades de matrizes e vetores, que são objetos matemáticos associados a Álgebra Linear, mas sobre os quais não precisamos de ter muitos conhecimentos a priori.
Objetivos de aprendizagem
No final deste curso, os(as) participantes estarão aptos(as) a:
construir modelos simples que permitem fazer certos tipos de previsões de tempo e de ocupações de salas num labirinto, entre outros modelos;
explicar como funciona o algoritmo de ordenação de páginas web do Google;
saber verificar em que condições (matemáticas) é que uma cadeia de Markov converge para um vetor de estado único (vetor estacionário).
Será de esperar ainda que no final do curso, os participantes saibam usar um software de cálculo numérico para fazer as contas mais trabalhosas destes modelos. Todos os exemplos neste curso correm no software Mathematica que é uma ferramenta de cálculo algébrico (ver Pré-Requisitos).
Público-alvo
Este curso destina-se preferencialmente a um público com curiosidade por aplicações atuais de Matemática e a alunos do ensino secundário e 1º ano do ensino superior das áreas de ciências e tecnologias (tópicos STEM).
Pré-requisitos
Ao nível de conhecimentos na área de matemática:
pressupõe-se que o(a) participante tem alguma familiaridade com cálculos algébricos simples;
facilita ter alguns conhecimentos de operações algébricas com matrizes e vetores.
Ao nível de utilização de software:
Mathematica para algumas operações matriciais, mas podem ser usados outros programas, calculadoras programáveis com operações matriciais ou recorrer ao motor de busca computacional Wolfram Alpha (Wolfram|Alpha);
as simulações deste curso correm num software gratuito (Wolfram CDF Player), que pode ser descarregado do site da Wolfram.
Conteúdos
Os conceitos a abordar são
cadeias de Markov;
matrizes de transição, i.e. matrizes de Markov;
vetores estacionários integrados em modelos lineares, que permitem prever estados futuros (ou tempos de ocupação média) da cadeia, ou seja, prever o comportamento estatístico a longo prazo da cadeia.
Os 4 tópicos semanais são dedicados a:
introduzir os conceitos básicos necessários para prever o longo prazo;
descrever diferentes modelos de passeios aleatórios em labirintos e grafos (redes), que ajudam a entender o funcionamento geral das cadeias de Markov;
explicitar os traços gerais de funcionamento do algoritmo do PageRank.
Este procedimento será fundamentado por um teorema importante (Teorema de Perron-Frobenius), que é a base matemática que explica o comportamento estatístico dos modelos analisados durante o curso.
Organização e duração
O curso encontra-se dividido em 4 tópicos e exige uma média de 5 horas de trabalho semanal.
Os conteúdos são antecedidos por uma breve introdução ao curso e uma nota histórica sobre A.A. Markov. Cada tópico inclui vídeos de exposição dos conceitos e dos cálculos a realizar, com ou sem utilização de cálculo numérico computacional. Em alguns vídeos são usadas simulações interativas que são posteriormente disponibilizadas para que cada participante possa praticar livremente na sua área de trabalho.
Nos fóruns de discussão associados a cada vídeo e a cada tópico é possível tirar dúvidas e fazer comentários sobre os conceitos expostos e os procedimentos envolvidos. São as dúvidas e comentários deixados nos fóruns que tornam a experiência do curso mais rica e única. A moderação da discussão no fórum será assegurada pela tutora do curso a cada 5 dias.
Disponibiliza-se uma Wiki, onde se encontram as definições dos principais conceitos introduzidos, procedimentos descritos, usando uma sintaxe simples. Em alguns casos, os participantes podem consultar outros materiais (vídeos e livros) que auxiliam a compreensão de conteúdos auxiliares e complementares de algumas matérias.
Avaliação e certificação
No final de cada tópico apresentado estão previstos momentos de avaliação com, por exemplo, exercícios de escolha múltipla, respostas múltiplas, respostas numéricas, entre outros. Existem ainda momentos de avaliação formativa em que se realizarão questionários de auto-avaliação e, por fim, uma avaliação sumativa por cada tópico com a ponderação de 80% da nota final do curso.
No final do curso há um teste final sobre os vários conteúdos abordados com a ponderação de 20% da nota final do curso.
Os participantes com uma nota final igual ou superior a 60% terão direito a um certificado gratuito de participação (sem classificação atribuída), que poderá ser descarregado através da barra de progresso. Aconselha-se a todos os participantes que descarreguem o certificado após a conclusão de todas as avaliações sumativas.
Tutores
Ana Moura Santos
Licenciada em Física-Matemática na Universidade de Moscovo, é mestre (1995) e doutora (1999) em Matemática Aplicada pelo Técnico, onde começou a lecionar em 1987 - primeiro no Departamento de Física e, desde 1993, no Departamento de Matemática.
Desenvolve investigação na área da Teoria de Operadores e Análise Funcional com aplicações a Física-Matemática, e também tem desenvolvido trabalho em questões de ordem pedagógica, nomeadamente em projetos de e-learning na área da Matemática.
Passa a maior parte do seu tempo livre em atividades relacionadas com dança, praticando atualmente sevilhanas e flamenco e participando em projetos de dança.
Os vídeos integrados neste curso foram gravados no estúdio da FCCN
About this Course
In this course about Markov matrices the main emphasis will be given to different models of applications of Markov chains, where the matrices are one of the principal. The other actors are the state vectors, which can describe either the probability of being sunny or cloudy in a given day, either the distribution probability of a given population between the city and the suburbs.
One of the main goals of this course will be to describe and simulate the Google search engine algorithm, PageRank, to rank the importance of web pages when one searches for a certain topic. With this end in mind, we are then going to use concepts and properties of matrices and vectors that are mathematical objects related to Linear Algebra, although there is no great need for an a priori knowledge of them.
Main goals
At the end of this course, you will be able to:
Build simple models that allow to predict the weather and occupation times for rooms in a maze, among other models;
Explain how the Google search engine algorithm works in order to rank the importance of web pages;
Know how to verify under which (mathematical) conditions a Markov chain converges to a unique vector state (steady-state vector).
It will be expected that at the end of the course you will be capable of using a numerical software to do the more complicated calculations of these models..
Target audience
This course is aimed mainly at an audience with interest in current applications of Mathematics, and to secondary students and first year undergraduates within Science and Technology (STEM areas).
Prerequisites
In what concerns mathematical background:
We assume that you are familiar with basic algebraic calculations;
The knowledge of algebraic operations on matrices and vectors helps.
In what concerns numerical software:
Mathematica software to perform several matrix operations, but it is possible to use other softwares (Maple, MATLAB, etc.), programmable calculators with matrix capabilities or to use the computational search engine Wolfram Alpha (Wolfram|Alpha);
Simulations of this course run on a free software Wolfram CDF Player) that can be downloaded from Wolfram website.
Contents
The concepts to address are:
Markov chains;
Transition matrices, i.e. Markov matrices;
Steady-state vectors integrated in linear models, which allow to predict future states (or occupation times) of the chain, that is, to predict the statistical behavior on the long-run of the chain.
The 4 weekly topics are dedicated to:
Introduce the basic concepts needed to predict the long-run;
Describe for a while different models of random walks in mazes and graphs (webs), which help to understand the general functioning of Markov chains;
Explain the main features of the PageRank algorithm. This procedure will be supported by an important theorem (Perron-Frobenius theorem), which constitutes the mathematical basis for the statistical behavior of the several models analyzed during the course.
Planning and Duration
This course is divided into 4 topics and requires an average of 5 hours of work per week.
The contents are preceded by a brief introduction to the course and a historical note about A.A. Markov. Each topic includes videos of concepts and calculations to be performed, with or without numerical calculus computational. In some videos, interactive simulations are used and all of them would be available so that each participant can practice freely in their work area.
In the discussion forums associated with each video and each topic, you can ask questions and comment on the concepts and procedures involved. It is the doubts and comments left in the forums that make this experience richer and unique. The moderation of the discussion in the forum will be ensured by the tutor of the course every 5 days.
A Wiki is available, where the definitions of the main concepts introduced and described procedures are found, using a simple syntax. In some cases, participants may consult other materials (videos and books) that helps to understand the contents of some subjects.
Assessment and certification
At the end of each topic presented, there are evaluation moments with, for example, multiple choice exercises, multiple answers, numerical input, among others. There are also moments of formative evaluation in which self-assessment questionnaires will be carried out and, finally, a summative evaluation at the end of each topic with the weight of 80% of the final grade of the course.
At the end of the course there is a final test whith the contents approached along the course with the weight of 20% of the final grade of the course.
Participants with a final grade equal to or greater than 60% will be access to a free participation certificate (without classification assigned), which can be downloaded through the progress menu. All participants are advised to download the certificate upon completion of all summative evaluations.
Course Staff
Ana Moura Santos
Received her diploma in Physics-Mathematics Sciences from the University of Moscow, and the MSc and PhD degrees in Applied Mathematics from Técnico, where she started teaching in 1987, first at the Department of Physics and, from 1993 on, at the department of Mathematics. The area of her research is Operator Theory and Functional Analysis with applications, and also works on pedagogical issues, namely developing e-learning resources for projects in Mathematics. She spends most of her free time in activities related to dance, presently practicing sevillanas and flamenco and participating in dance-technology projects.
