domingo, 30 de outubro de 2016

Componentes conectados em Grafos

Em um grafo não-direcionado G, dois vértices u e v são ditos conectados se G contém um caminho de u para v. Senão, eles são chamados de desconectados.  Um grafo orientado (ou direcionado) é chamado de fracamente conectado se a substituição de todas as suas arestas direcionadas por arestas não direcionadas produz um grafo (não-direcionado) conectado. Ele é chamado de conectado se possui um caminho direcionado de u para v ou um caminho direcionado de v para u para cada par de vértices u, v. Ele é fortemente conexo se contém um caminho direto de u para v e um caminho direto v para u para cada par de vértices u, v. Um vértice de corte de um grafo conexo G é um conjunto de vértices que quando removidos torna G desconexo.

Um grafo não direcionado é conectado se cada par de vértices está conectado por um caminho. Os componentes conectados são as porções conectadas de um grafo. Um grafo não direcionado é conectado se ele tem exatamente um componente conectado.
Os componentes fortemente conexos são os subgrafos maximais fortemente conectados.
Os componentes fortemente conectados de um grafo direcionado são conjuntos de vértices sob a relação “são mutuamente alcançáveis”.

Por exemplo {0, 1, 2, 3}, {4} e {5} são os componentes fortemente conectados, {4, 5} não o é, pois o vértice 5 não é alcançável a partir do vértice 4.

O Algoritmo para achar estes componentes é:

  1. Aplicar a busca em profundidade no grafo G para obter os tempos de término t[u] para cada vértice u. 
  2. Obter o grafo G', que é o grafo transposto, isto é, são os mesmos vértices mas as arestas são invertidas. Assim existe uma arestas (u,v) em G' se existe uma aresta (v,u) em G. 
  3. Aplicar a busca em profundidade no grafo G' realizando a busca a partir do vértice de maior t[u] obtido na linha 1.
  4. Se a busca em profundidade não alcançar todos os vértices, inicie uma nova busca em profundidade a partir do vértice de maior t[u] dentre os vértices restantes.
  5. Retornar os vértices de cada árvore da floresta obtida na busca em profundidade na linha 3 como um componente fortemente conectado separado.



quinta-feira, 22 de setembro de 2016

Ativando Wi-Fi no Raspberry PI 2/3 usando a linha de comando

Para rodar o wifi (contando que o driver da placa wifi tenha sido reconhecida e carregada), você precisa do wpa_supplicant. Ele pode ser instalado usando

sudo apt-get instal wpa_supplicant.


Você pode tentar seguir o guia do site do Raspberry Pi. No meu caso o guia não funcionou pois ele considera a alteração no arquivo /etc/network/interfaces, mas no meu Pi  esta alteração não tem efeito.

1) criar o arquivo de configuração do wpa_supplicant
Você terá que editar (criar) o arquivo /etc/wpa_supplicant/wpa_supplicant.conf. Ele deverá ter no mínimo as linhas abaixo.

country=BR
ctrl_interface=DIR=/var/run/wpa_supplicant GROUP=netdev
update_config=1
network={
    ssid="SSID do seu AP"
    psk="senha do seu AP"
}

Edite as linhas SSID e psk para conter o nome da sua rede sem fio (ESSID) e a senha da rede.

2) criar um script para rodar o wpa_supplicant. No meu caso eu coloquei em /etc/init.d/wpa_supplicant. Veja no script que está indicado a interface wlan0 onde será feita a conexão. No caso do seu Pi, você tem que configurar para o nome correto da interface.

#! /bin/sh
### BEGIN INIT INFO
# Provides: wpa_supplicant
# Required-Start:    $local_fs $syslog $remote_fs dbus
# Required-Stop:     $local_fs $syslog $remote_fs
# Default-Start:     2 3 4 5
# Default-Stop:      0 1 6
# Short-Description: Start wpa_supplicant daemon
### END INIT INFO
# este script não estava rodando nos diretorios rcX.d
# ele deveria ficar ativo usando
# update_rc.d wpa_supplicant enable
# contudo apesar de criar os links ele não funcionou
# para ativá-lo eu tive que chamar o script em /etc/rc.local

DAEMON=/sbin/wpa_supplicant
DESC="wpa_supplicant wlan0"
CONF=/etc/wpa_supplicant/wpa_supplicant.conf

test -f $DAEMON || exit 0

# FIXME: any of the sourced files may fail if/with syntax errors
test -f $CONF

case $1 in
  start)
  echo "Starting $DESC"
  $DAEMON -i wlan0 -c $CONF -B
  ;;

  stop)
  echo "Stopping $DESC"
  pkill wpa_supplicant
  ;;
  
  restart|force-reload)
  $0 stop
  sleep 1
  $0 start
  ;;
  
  *)
  echo "Usage: $0 {start|stop|restart}" >&2
  exit 1
  ;;
esac

exit 0

3) alterar o arquivo /etc/rc.local para chamar o script criado no passo (2). No meu caso eu simplesmente inseri a linha abaixo

/etc/init.d/wpa_supplicant start


Não é necessária nenhuma outra configuração. Meu arquivo /etc/network/interfaces possui 3 linhas relacionadas com wlan0, contudo elas não fazem efeito real. Reproduzo abaixo somente para vocês verem o que são.

allow-hotplug wlan0
iface wlan0 inet manual 
    wpa-conf /etc/wpa_supplicant/wpa_supplicant.conf


terça-feira, 6 de setembro de 2016

Bug PCManFM - Não abre o terminal

Se você é como eu e usa bastante o terminal no linux, tem uma característica interessante que é abrir o terminal no diretório corrente dentro do navegador. O Ubuntu é possível adicional ao menu de contexto uma opção "Abrir no terminal". Para isto basta instalar  esta opção ao Nautilus:

sudo apt-get install nautilus-open-terminal
Basta reiniciar o nautilus com (nautilus -q) para que a opção já esteja ativa.

Contudo se você utiliza o LUbuntu, o navegador é o PCManFM. Ele tem está opção no menu de ferramenta que é acionada via teclado usando <F4>. Contudo ela tem um bug.


A instalação padrão não abre diretórios com espaços como no meu exemplo da "Área de Trabalho". Esta opção de menu aciona um script que está no arquivo /usr/bin/lxsession-default-terminal. Dentro deste script vemos que a variável $PWD não está entre aspas. Basta consertar como na imagem abaixo e pronto. O <F4> funciona.


domingo, 3 de julho de 2016

Instalando owncloud no Raspberry PI 2

Neste nosso post, vou mostrar como instalar o owncloud no seu raspberry pi 2. Eu já vi alguns locais mostrando a instalação e não achei que estavam completos, sempre faltava alguma coisa que a gente tinha que adivinhar.

Assim vamos começar com uma instalação a partir do zero, isto é, baixamos o raspbian jesse lite do site (https://www.raspberrypi.org/downloads/). Nossa escolha pela versão Lite é que assim temos uma instalação limpa com poucos programas instalados. Esta versão não tem nem mesmo a interface gráfica. Desta forma ganhamos também em desempenho, pois não tem programas que não precisamos rodando no PI2.

Instalando imagem


No nosso caso estamos usando Windows, desta forma precisamos de um aplicativo para copiar o Jesse para dentro do miniSD. O procedimento em raspberry é bastante eficiente. Basicamente você tem que baixar o programa Win32DiskImager do site da Sourceforge e instalá-lo no seu comptuador. Depois de instalado, basta rodar, selecionar a imagem que você fez download (normalmente a iamgem baixada está zipada, portanto você tem que descompactar), selecionar a unidade onde está o miniSD e selecionar a opção de WRITE. Quando acabar a cópia, basta remover o SD e colocá-lo no PI2.

Rodando o PI pela primeira vez

Ligue o seu PI2. Ele dará o boot e você poderá entrar. O usuário padrão é pi com a senha raspberry. Você pode configurar as opções regionais usando o comando sudo raspi-config. O raspi-config apresenta uma tela como a mostrada abaixo:




No meu caso eu começei para trocar as opções de locale para pt-BR.UTF-8, o timezone para São Paulo, o layout para brasileiro e Wifi country para BR. Neste post não mostro o uso do Wifi, fica para uma outra oportunidade. Nossa conexão foi ethernet.




Também aproveitei para trocar o nome do host. Por default o SSH server está habilitado, se no seu caso não estiver também é nesta opção que podemos ativá-lo.




Aparentemente as novas versões do Raspian (a minha é Jesse) já fazem durante a inicialização a expansão do filesystem para ocupar todo o seu cartão SD. O meu por exemplo tem 32GB e já foi totalmente reconhecido pelo PI2. Se no seu caso isto não ocorrer e você quiser aumentar o espaço, use a opção (1) do menu de opções avançadas do raspi-config.





Instalações adicionais e configuração inicial

Para usar o owncloud é necessário ter um servidor web instalado. Iremos usar o NGINX que é bem leve e funciona com o PI2. Iniciamos configurando o usuário:

$ sudo usermod -a -G www-data www-data

Agora precisamos instalar uns pacotes que incluem o nginx, php5, sqlite, certificados, php5-fpm etc. Demora um pouco esta atualização. Pode ser que você tenha um update primeiro.

$ sudo sudo apt-get update

$ sudo sudo apt-get install curl libapr1 libcurl4-openssl-dev libtool memcached nginx openssl php-apc php-pear php5 php5-curl php5-cgi php5-cli php5-dev php5-fpm php5-gd php5-imagick php5-intl php5-json php5-mcrypt php5-sqlite php5-common php5-memcache php-xml-parser sqlite sqlite3 ssl-cert varnish



Vamos criar um certificado SSL. Note que estamos criando um certificado válido por 3 anos (se você quiser mudar o tempo basta alterar 1095 para a quantidade de dias desejada). Você precisará preencher uma perguntas durante a execução da criação do certificado. O comando abaixo irá gerar uma chave RSA de 2048 bits. Você pode dar uma olhada em https://www.openssl.org/docs/manmaster/apps/req.html para mais opções.


$ sudo openssl req $@-new -x509 -days 1095 -nodes -out /etc/nginx/cert.pem -keyout /etc/nginx/cert.key

Modifique as permissões para garantir segurança.

$ sudo chmod 600 /etc/nginx/cert.pem

$ sudo chmod 600 /etc/nginx/cert.key


Eu alterei meu arquivo /etc/hosts para poder chamar o meu PI2 de pi-owncloud.




Altere o arquivo /etc/php5/fpm/php.ini:

  • Ache upload_max_filesize e troque o valor para 2000M
  • Ache post_max_size e troque o valor para 2000M

Grave o arquivo alterado. Isto vai permitir transferências de arquivos de 2GB (este é o limite).

Altere o arquivo /etc/php5/fpm/pool.d/www.conf. Ache a linha:

  • listen = /var/run/php5-fpm.sock

e troque para

  • listen = 127.0.0.1:9000

Grave o arquivo.

Abra o arquivo /etc/dphys-swapfile e altere a linha contendo:

  • CONF_SWAPSIZE=100

para

  • CONF_SWAPSIZE=512

Grave o arquivo.

Vamos ativar o fpm:

$ sudo update-rc.d php5-fpm enable

Altere o arquivo /etc/nginx/site-available/default (este é o conteúdo completo do meu arquivo de configuração):

upstream php-handler {
  # para usar php5-fpm
  server 127.0.0.1:9000;
  #server unix:/var/run/php5-fpm.sock;
}

server {
  listen 80;
  server_name pi-owncloud;
  # garante que será https
  # fazendo um redirecionamento
  return 301 https://$server_name$request_uri;
}

server {
  # SSL configuration (ipv4 e ipv6)
  listen 443 ssl ;
  listen [::]:443 ssl ;

  ssl_certificate /etc/nginx/cert.pem;
  ssl_certificate_key /etc/nginx/cert.key;

  root /var/www/owncloud;

  # Add index.php to the list if you are using PHP
  index index.php

  server_name _;

  add_header X-Content-Type-Options nosniff;
  add_header X-Frame-Options "SAMEORIGIN";
  add_header X-XSS-Protection "1; mode=block";
  add_header X-Robots-Tag none;
  add_header X-Download-Options noopen;
  add_header X-Permitted-Cross-Domain-Policies none;

  location = /robots.txt {
    allow all;
    log_not_found off;
    access_log off;
  }


  # alterar o "max upload size"
  client_max_body_size 2000M;
  Fastcgi_buffers 64 4K;

  # Disable gzip to avoid the removal of the ETag header
  gzip off;

  location / {
    # garante que sempre será chamado o index.php
    rewrite ^ /index.php$uri;
  }

  location ~ ^/(?:build|tests|config|lib|3rdparty|templates|data)/ {
    deny all;
  }

  location ~ ^/(?:\.|autotest|occ|issue|indie|db_|console) {
    deny all;
  }

  location ~
^/(?:index|remote|public|cron|core/ajax/update|status|ocs/v[12]|updater/.+|ocs-provider/.+|core/templates/40[34])\.php(?:$|/) {

    include fastcgi_params;
    fastcgi_split_path_info ^(.+\.php)(/.+)$;
    fastcgi_param SCRIPT_FILENAME $document_root$fastcgi_script_name;
    fastcgi_param PATH_INFO $fastcgi_path_info;
    fastcgi_param HTTPS on;
    #Avoid sending the security headers twice
    fastcgi_param modHeadersAvailable true;
    fastcgi_param front_controller_active true;
    fastcgi_pass php-handler;
    fastcgi_intercept_errors on;
  }

  location ~ ^/(?:updater|ocs-provider)(?:$|/) {
    try_files $uri/ =404;
    index index.php;
  }

  # Adding the cache control header for js and css files
  # Make sure it is BELOW the PHP block
  location ~* \.(?:css|js)$ {
    try_files $uri /index.php$uri$is_args$args;
    add_header Cache-Control "public, max-age=7200";
    # Add headers to serve security related headers (It is intended
    # to have those duplicated to the ones above)
    # Before enabling Strict-Transport-Security headers please 
    # read into this topic first.
    add_header Strict-Transport-Security "max-age=15768000;
    # includeSubDomains; preload;";
    add_header X-Content-Type-Options nosniff;
    add_header X-Frame-Options "SAMEORIGIN";
    add_header X-XSS-Protection "1; mode=block";
    add_header X-Robots-Tag none;
    add_header X-Download-Options noopen;
    add_header X-Permitted-Cross-Domain-Policies none;

    # Optional: Don't log access to assets
    access_log off;
  }

  location ~* \.(?:svg|gif|png|html|ttf|woff|ico|jpg|jpeg)$ {
    try_files $uri /index.php$uri$is_args$args;
    # Optional: Don't log access to other assets
    access_log off;
  }
}


Note que na minha configuração o owncloud ficará em /var/www/owncloud.
Se você quiser mais informações olhe em na documentação do owncloud, ela é bastante precisa.

Instalando owncloud

Faça o download do ownload no site https://owncloud.org/install/.
O meu caso estou utilizando a versão 9.0.3.
As linhas abaixo copiam o owncloud zipado do site para dentro do diretório tmp, descompactam os arquivos no diretório owncloud. Move este diretório para dentro do diretório onde ele irá rodar e acerta as permissões. No meu caso o diretório final será /var/www/owncloud. E por fim apaga o download.

$ cd /tmp

$ wget https://download.owncloud.org/community/owncloud-9.0.3.tar.bz2

$ tar xvf owncloud-9.0.3.tar.bz2

$ sudo mv owncloud/ /var/www/

$ sudo chown -R www-data:www-data /var/www

$ rm -rf owncloud*

$ sudo mkdir -p /var/owncloud/data

$ sudo chown -R www-data:www-data /var/owncloud/data

É necessário fazer uma alteração do arquivo /etc/php5/fpm/pool.d/www.conf. Localize as linhas abaixo de descomente. A linha contendo env[PATH] deve conter o resultado de echo $PATH no shell.

; Pass environment variables like LD_LIBRARY_PATH.
; All $VARIABLEs are taken from
; the current environment.
; Default Value: clean env
env[HOSTNAME] = $HOSTNAME

env[PATH] = /usr/local/sbin:/usr/local/bin:/usr/sbin:/usr/bin:/sbin:/bin:/usr/local/games:/usr/games

env[TMP] = /tmp
env[TMPDIR] = /tmp
env[TEMP] = /tmp

Reinicie o PI2.

A configuração agora é feita via web. No meu caso https://192.168.10.12.
Se você tentar acessar via http, você será redirecionado para https. O meu navegador (chrome) apresenta a seguinte tela ao tentar acesso:



É necessário aceitar a exceção para entrar o owncloud:


Você deve preencher o nome do primeiro usuário (e que será o administrador) do owncloud. Digite a senha (tem um bug que às vezes indica que sua senha é fraca mesmo quando não é - veja meu exemplo). Você pode escolher qualquer senha. Você precisa clicar em "Armazenamento & Banco de dados" para poder indicar onde os dados do owncloud ficarão. No meu caso usei o diretório que criamos no passo inicial (/var/owncloud/data).



Se você quiser criar seu armazenamento em um pendrive sugiro dar uma olhada neste tutorial. Ele tem um passo a passo da instalação do owncloud (com apenas uns passos faltando), mas tem uma parte bacana sobre como montar automaticamente o pendrive (e com NTFS). Se você for utilizar fat, basta trocar a opção ntfs-3g do fstab que ele mostra para vfat.

Após clicar em "Concluir configuração", será aberta a tela inicial do owncloud.

No menu no alto à esquerda, onde está escrito "pi" na minha tela abaixo, você encontrará a opção de administração que permite criar novos usuários.


Aproveite...








quinta-feira, 28 de janeiro de 2016

Instalando Hadoop

Recentemente tive que instalar o Hadoop para um projeto de computação. O Hadoop é uma plataforma de software em Java de computação distribuída voltada para clusters e processamento de grandes massas de dados desenvolvida pelo Apache.

Hadoop possui diversos módulos. Hadoop Common contém as bibliotecas e arquivos comuns utiizados pelos outros os módulos Hadoop. Neste exemplo utilizaremos um sistema de arquivos distribuído que armazena dados em máquinas dentro do cluster, sob demanda, denominado Hadoop Distributed File System ou HDFS.

Hadoop fornece uma plataforma de gerenciamento de recursos responsável pelo gerenciamento dos recursos computacionais do cluster e pelo agendamento dos recursos, denominado Hadoop Yarn. O framework YARN no Hadoop permite utilizar o MapReduce para processsamento de grandes quantidades de dados.

A documentação do Hadoop pode ser achada aqui.

No nosso exemplo fazemos a instalação de 3 máquinas virtuais: uma computador mestre e dois escravos.