Matrizes de Markov IST

Enrollment is Closed

Descrição geral

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:

    wolfram-corporate-logo
  • 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.
  • São disponibilizadas 150 licenças do Mathematica que permitirão o uso gratuito deste software durante a duração do curso.

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 que correspondem a 4 semanas de duração. É antecedido por uma breve introdução ao curso e uma nota histórica sobre A.A. Markov.

Cada tópico semanal inclui vídeos de exposição dos conceitos e dos cálculos a fazer, com ou sem utilização de cálculo numérico computacional. Nalguns vídeos são usadas simulações interativas que são posteriormente disponibilizadas para descarregar com o objetivo de permitir a cada participante praticar livremente.

Nos fóruns de discussão associados a cada vídeo e a cada tópico semanal é possível esclarecer dúvidas e fazer comentários sobre os conceitos expostos e os procedimentos envolvidos.

A equipa do curso (professora e tutor) irá moderar a discussão no fórum pelo menos de 2 em 2 dias.

Disponibiliza-se uma Wiki, onde se vão colocando as definições dos principais conceitos introduzidos, procedimentos descritos, usando uma sintaxe simples. Nalguns casos, remetem-se os participantes para 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

Em cada tópico semanal estão previstos momentos de avaliação (exercícios de escolha múltipla, resposta múltiplas, numéricas, etc.): questionários depois da exposição dos conteúdos vídeo e uma avaliação sumativa por cada tópico (80% da nota final do curso).

No final do curso há uma avaliação sobre os vários conteúdos abordados (20% da nota final do curso).

Os participantes com uma nota final superior a 60% terão direito a um certificado de participação.

Tutores

Ana Moura Santos

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 com tecnologia.

Pedro Ribeiro

Pedro Ribeiro

Aluno finalista do Mestrado em Engenharia Física Tecnológica no Instituto Superior Técnico, atualmente a realizar a tese sobre o desenvolvimento de novos sensores toque para robôs humanoides.

É colaborador na Direção de Serviços de Informática do Técnico, com a função de Back-end Developer no MOOC Técnico, tendo vindo a contribuir para o desenvolvimento desta plataforma e com outras soluções para e-learning no Técnico.

Creative Commons License
Este curso e os seus respetivos conteúdos estão licenciados através da licença Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

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. In this course, all the examples run in the Mathematica software, a computer algebra system (see Pre-Requisites).

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:

    wolfram-corporate-logo
  • Mathematica software to perform several matrix operations, but it is possible to use other softwares, 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.

A total of 150 free Mathematica licenses are available, allowing the usage of this software for the duration of the course.

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

The course runs for 4 weeks/4 topics, preceded by a short introduction to the course and an historical video about A.A. Markov.

Each weekly topic includes expository videos with theoretical contents and corresponding calculations, with or without help of numerical computations. In several videos we make use of interactive simulations that would be afterwards available to download in order to facilitate a free personalized interaction.

In the discussion forums after each video and within each topic it will be possible to ask questions and make comments about the given concepts and the involved procedures. The course team (professor and teaching assistant) will moderate at least the discussion forum each 2 days. Sometimes there will be handouts that support the video contents with complementary explanations.

Assessment and certification

In each weekly topic there will be evaluation moments (multiple choice problems, check boxes, numerical input, etc.): quizzes after the content explanations of the videos and an assessment test at the end of each topic (80% of the final grade).

In the end of the course there will be a final evaluation of all the contents taught during the course (20% of the final grade).

Participants with a final score greater than 60% will receive a completion certificate.

Course Staff

Ana Moura Santos

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.

Pedro Ribeiro

Pedro Ribeiro

Collaborator at the Computer and Network Services in Técnico, as a back-end developer in MOOC Técnico, contributing to the development of this platform as well as other solutions for e-learning at Técnico.

He is also a Physics Engineering student at Técnico, currently conducting his master’s thesis on the development of new touch sensors for humanoid robots.

Creative Commons License
The following course and its contents are licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

The videos shown in this course were recorded at the FCCNstudio.

  1. Course Number

    mmX
  2. Classes Start

    Mar 01, 2017
  3. Classes End

    Apr 09, 2017
  4. Enrollment Start Date

    Feb 06, 2017
  5. Enrollment End Date

    Mar 22, 2017
  6. Language

    Portuguese
  7. Estimated Effort per Week

    05:00
  8. Price

    Free