BCM0506 -- Comunicação e Redes -- 2021.1

Turmas NA1 e NB1

Feb 1, 2021

Atualizado em 22/02 Nota: o material didático foi movido para o Moodle-UFABC (detalhes abaixo).

Descrição e objetivos

O curso será uma introdução à ciência das redes complexas. Informalmente, uma rede é uma coleção de objetos interconectados com um determinado propósito. Formalmente, é um grafo ou um digrafo rotulado (formalismos matemáticos para o estudo de endorelações binárias). A qualificação complexa encontrada na literatura se refere ao grande volume de informação representado por e à propriedades implicitamente codificadas em uma rede. Redes complexas encontram uma multitude de aplicações nos mais variados campos, como tecnologia (internet, www, telefonias fixa e móvel), infra-estrutura (água, luz, gás), logística (transporte, roteamento, localização), biologia (metabolismo, interações entre proteínas e/ou medicamentos, cérebro e rede neural), ecologia (filogenia, cadeia predatória, inter e intra-dependência em ecossistemas), educação/informação (enciclopédias, wikipedia, coautorias e citações), sociologia (facebook, instagram, twitter, linked-in, snapchat, whatsapp, clubes, sociedades e castas).

O campo é vasto, varrendo da representação à especificação à inferência e à mineração de propriedades estáticas ou dinâmicas, determinísticas ou estocásticas. Nossa abordagem será primariamente abstrata e matemática, com foco na definição, caracterização e inferência de aspectos estruturais e assintóticos de propriedades em redes massivas (grande número de vértices) e em algoritmos para verificação ou cômputo de tais propriedades. Em momentos adequados ou oportunos, introduziremos aspectos semânticos através de aplicações. Inúmeras técnicas para construção de provas serão apresentadas. O objetivo é desenvolver na/o estudante o raciocínio e a destreza na manipulação de estruturas discretas, espaços lineares e argumentos probabilísticos.

Aulas e Avaliações

  • Professor: Aritanan Gruber
  • Turmas: NA1 (Seg 19–21h, Qui I 21–23h), NB1 (Seg 21–23h, Qui I 19–21h).
  • Página no Moodle-UFABC: CR-21.1 (NA1+NB1)
  • Atendimento: Seg 20–22h via Google Meet
    (você deve estar logado no Classroom (código: qfjdmhv) com sua conta da universidade)
  • Aulas assíncronas: vídeos em Aritanan Gruber’s YouTube , acessíveis também via Moodle.
  • Detalhes de andamento do curso, slides de notas de aulas, links para artigos, avaliações e notas no Moodle.
  • Avaliação: 3 melhores dentre 4 listas de exercícios + um projeto (detalhes em breve)

Critérios

Avaliação Cálculo Peso
Listas ($L$) $L = \frac{1}{3}\max_{S\in\binom{4}{3}}\{\sum_{j\in S}L_j\}$ 60% (20% cada)
Projeto ($P$) 40%
Nota nominal ($N$)     $N = \frac{2}{5}P + \frac{1}{5}L$

Conceito nominal ($C_N$): reflete o seu desempenho frente ao material apresentado e às avaliações realizadas; obtido pelo encaixe de $N$ em um dos intervalos: $$-\infty < \mathbf{F} < 5.0 \leq \mathbf{D} \leq 6.0 < \mathbf{C} \leq 7.0 < \mathbf{B} \leq 8.5 < \mathbf{A} < \infty.$$

Normalização

Sejam $\mu$ e $\sigma$ a média e o desvio padrão das notas $N$ atribuídas a todos os alunos. Cada aluno obterá uma nota normalizada: $$M = (N-\mu)/\sigma.$$

Conceito normalizado ($C_M$): reflete o seu desempenho perante os seus colegas; obtido pelo encaixe de $M$ em um dos intervalos: $$-\infty < \mathbf{F} < 0 \leq \mathbf{D} < \frac{1}{4} \leq \mathbf{C} < \frac{1}{2}\sigma \leq \mathbf{B} < \sigma \leq \mathbf{A} < \infty.$$

Considerando-se a ordenação $\mathbf{A} > \mathbf{B} > \mathbf{C} > \mathbf{D} > \mathbf{F}$, seu conceito efetivo (final / pré-recuperação) será maior ou igual ao seu conceito nominal: $$C_F = \max\{C_N,C_M\}.$$

Recuperação

Caso seu conceito $C_F$ seja $\mathbf{D}$ ou $\mathbf{F}$, você tem direito a uma prova online de recuperação $P_R$. Esta será única e contemplará toda a matéria do quadrimestre. Uma nova nota nominal $\overline{N}=(N+P_R)/2$ será utilizada para gerar um novo conceito (nominal) final pós-recuperação $\overline{C}_N$. Não haverá normalização na recuperação. Seu conceito final pós-recuperação pode ser menor que o pré-recuperação: uma vez feita, a recuperação é parte integrante da sua avaliação.

Tópicos

(slides e vídeos no Moodle)

  • A01 – Expediente e Introdução à Ciência de Redes
    (Barabási 1.1–1.7; Newman 2.1–5.3)
  • A02 e A03 – Introdução a Grafos (I)
    (Barabási 2.1–2.4; Newman 6.1–6.3, 6.9, 9.3)
  • A04 e A05 – Introdução a Grafos (II)
    (Barabási 2.6–2.9; Newman 6.10–6.12, 9.1, 10.3)
  • A06 – Caminhos Mínimos
    (Barabási 2.8, 2.9; Newman 10.4, 6.4, 6.6, 6.7)
  • A07 – Métricas de Importância Estrutural
    (Barabási 2.10, 2.A; Newman 7.1–7.9, 10.2)
  • A08 – Estrutura de Redes do “Mundo-Real”
    (Barabási 4; Newman 10)
  • A09 – Revisão de Teoria de Probabilidades
  • A10 e A11 – Modelo Aleatório Erdös-Rényi-Gilbert
    (Barabási 3.1 – 3.9; Newman 12.1 – 12.8)
  • A12 – Modelos de Configuração e Mundos Pequenos
    (Barabási 4.1, 4.2, 6.2, 6.4; Newman 8.2, 8.4, 13.2, 13.10, 13.11, 15.1, 15.2)
  • A13 – Modelos de Formação de Redes
    (Barabási 5.1 – 5.6; Newman 14.1 – 14.4)
  • A14 – Sistemas Dinâmicos Lineares
    (Newman 11.1, 18.1)
  • A15 – Passeios Aleatórios e Aplicações
    (Newman 6.13, 6.14, 7.4)
  • A16 – Difusão, Dispersão e Epidemiologia
    (Barabási 10.1 – 10.7; Newman 17.1 – 17.6)
  • A17 – Partição e Detecção de Comunidades
    (Barabási 9.1 – 9.4; Newman 11.2 – 11.8)
  • A18 e A19 – Teoria dos Jogos em Redes
    (Easley-Kleinberg 6, 7, 11, 12)

Bibliografia

As referências básicas são, em ordem: Barabási-Pósfai [0], Newman [7] e Easley-Kleinberg [1]. Figueiredo [3] é uma introdução sucinta em português que não cobre todo o conteúdo. Em momentos oportunos, faremos incursões em Frieze-Karonski [4] e Hofstad [5]. Referência de apoio para grafos e digrafos (com enfoque teórico) são Feofiloff-Kohayakawa-Wakabayashi [2] e Lehman-Leighton-Meyer [6].

Páginas úteis

Estudando para esta disciplina

Este curso tem nível introdutório e contempla uma coleção de problemas elementares e fundamentais na área. Apesar disso, é normal fazer confusões e sentir-se perdido no início. O motivo é, em geral, a falta de familiaridade com formalismo matemático e raciocínio algorítmico -– algo que o curso pretende reverter.

  • Refaça os exemplos fornecidos em sala de aula e re-prove os principais resultados.
  • Preste atenção ao processo de solução e não foque somente no resultado final.
  • Assista às aulas (vídeos) e resolva os exercícios propostos durante as mesmas e os contidos nas listas (não somente os para entrega).
  • Estude a bibliografia indicada (monte grupos de estudo online) e faça um bom uso dos horários de atendimento.
  • Tenha sempre em mente que aprendizado é uma tarefa ativa; não fique somente assistindo.
  • Se ainda estiver se sentindo perdido, repita os passos acima. Mais cedo ou mais tarde, eles convergirão à compreensão.

Integridade acadêmica e transgressões

O Artigo 25 do Código de Ética da UFABC estabelece, à página 23: “Quanto aos trabalhos acadêmicos, é eticamente inaceitável que os discentes:

  • I - fraudem avaliações;
  • II - fabriquem ou falsifiquem dados;
  • III - plageiem ou não creditem devidamente autoria;
  • IV - aceitem autoria de material acadêmico sem participação na produção;
  • V - vendam ou cedam autoria de material acadêmico próprio a pessoas que não participaram da produção.”

Trabalhos (listas, provas, programas) suspeitos de cópia ou de outra representação fraudulenta acarretarão aos envolvidos conceitos $\mathbf{F}$ (falha) no curso. A atividade será reportada à Comissão Disciplinar Discente da universidade para que sejam tomadas todas as providências disciplinares cabíveis.

Avatar
Aritanan Gruber
Assistant Professor

“See, if y’all haven’t the same feeling for this, I really don’t give a damn. If you ain’t feeling it, then dammit this ain’t for you!"
(desconheço a autoria; agradeço a indicação)