Arquivo de etiquetas: c

Algoritmo de Dijkstra

Nesta edição da Programar, não quisemos deixar de lado uma das linguagens mais usadas de todos os tempos.

A famosa linguagem C

E nesta edição comemorativa dos 10 anos da nossa revista, achamos que faria todo o sentido recordar um algoritmo, que em algum dia das nossas vidas, todos nós, programadores ouvimos falar… o não menos famoso que a própria linguagem C, o algoritmo de Dijkstra… e porque este algoritmo? Porquê este refere, o caminho do custo mínimo. E todos nós sabemos que a nossa revista já percorreu muitos caminhos até chegamos à edição 53.

Ora para os mais distraídos, e para os menos recordados, este algoritmo data do ano de 1956, tendo tido a sua primeira publicação em 1959. Foi criado por um matemático computacional holandês, Edsger Dijkstra. E trouxe uma solução que vários procuravam na altura, a solução para o problema do caminho mais curto num grafo dirigido.

Continuar a ler

Programação (in)Segura – Transbordo de Memória

Introdução

O software assume cada vez mais uma importância primordial no nosso dia-a-dia. De facto, é crescente o número de dispositivos com o qual interagimos quotidianamente e cujo funcionamento está dependente de software. Exemplos incluem, obviamente, computadores e tablets, bem como dispositivos ditos inteligentes, como telemóveis, relógios e televisões. Outros exemplos abarcam sistemas de transportes como automóveis, aeronaves e barcos, e sistemas de domótica, para citar apenas alguns dos mais conhecidos. Dado a complexidade associada não só à criação e manutenção de programas informáticos como ainda dos sistemas que pretendem controlar, o software está sujeito a ocorrência de erros. Alguns desses erros podem ser aproveitados por indivíduos ou entidades com intenções maliciosas para subverter os dispositivos controlados, comprometendo deste modo, parcial ou totalmente, a segurança dos sistemas.

Este artigo analisa os erros do tipo transbordo de memória, em particular os que poderão ocorrer no segmento de pilha. O artigo foca alguns dos problemas de segurança que estão associados a situações de transbordo de memória afeta ao segmento de pilha. Os exemplos de código apresentados foram testados num sistema Linux – Lubuntu 14.04 / 32 bits, com kernel versão 3.13.04. Os exemplos foram compilados com a versão 4.8.2 do compilador de linguagem C GNU Collection Compiler (GCC).

Continuar a ler

Travessia de uma árvore de diretórios usando recursividade

Introdução

O diretório é um elemento familiar nos sistemas de ficheiros, sendo empregue para organizar o armazenamento de dados em suporte persistente como, por exemplo, discos rígidos. Uma operação relativamente comum num sistema de ficheiros é a travessia da árvore de diretórios, através da qual são visitados todos os subdiretórios e ficheiros. Este artigo foca o uso de recursividade e das funções stat e readdir para a travessia de uma árvore de diretório recorrendo à metodologia denominada de busca em profundidade (depth-first search na designação anglo-saxónica) (Knuth, 1968) (Wikipedia, 2015). Embora o artigo assente no ambiente Linux e na linguagem C, a metodologia utilizada pode ser empregue, com algumas adaptações, noutras plataformas e com outras linguagens de programação.

Continuar a ler

Manipulação ao nível do bit na Linguagem C

É sabido que um computador trabalha em modo binário, armazenando e manipulando bits, isto é, zeros e uns. Este artigo procura resumir as metodologias mais comuns para uso e manipulação de bits através da linguagem C.

Base binária, octal e hexadecimal

A designação bit identifica um valor da base binária. Como o nome sugere, a base binária é composta por dois valores distintos, representados por zero e um, daí também se designar por base dois. Assim, um bit pode assumir um desses dois valores, sendo muitas vezes empregue para representar um estado ativo (bit com o valor a 1) ou inativo (bit com valor a 0).

Continuar a ler

Ordenação Genérica em C

Introdução

Em um artigo anterior, tratei do problema da construção de estruturas de dados genéricas, isto é, estruturas capazes de manipular diferentes tipos de dados, informados no momento da criação destas estruturas. No final deste artigo, levantei a seguinte questão:

Como podemos criar uma função comparar os itens de uma estrutura de dados genérica, uma vez que ela não conhece o seu tipo, a priori. Mesmo sabendo qual é o tipo de dado, em alguns casos, não seria possível compará-los; por exemplo, quando o tipo de dado é uma estrutura complexa, criada pelo próprio desenvolvedor, como uma struct para armazenar os dados de um aluno, entre outros.

Para resolver este problema, utilizando a linguagem C, precisamos lançar mão de um recurso conhecido como funções callback. Esse tipo de função tira proveito do fato de que a linguagem C trabalha com ponteiros para funções, isto é, podemos passar para uma função, um ponteiro que aponta para o bloco da memória onde está localizada outra função do sistema (ou até mesmo a própria função que está recebendo o parâmetro). Isto permite que uma determinada função chame outras funções, mesmo sem ter conhecimentos de quais funções são estas.

Continuar a ler

Estruturas de Dados Genéricas

Introdução

Quando cursamos disciplinas de Algoritmos e Estruturas de Dados nos cursos de computação e áreas afins, em geral, aprendemos a criar Estruturas de Dados (EDs) básicas, como listas, pilhas, filas, capazes de trabalharem apenas com números inteiros. Isto não é essencialmente um problema, uma vez que o intuito destas disciplinas é apresentar os principais tipos de EDs, as operações relacionadas a elas, bem como as formas de uso (aplicação) das mesmas; o que não depende do tipo de dados armazenado pela estrutura.

Contudo, quando vamos para a prática do desenvolvimento e utilização destas EDs, seja num trabalho prático da disciplina ou em outro tipo de aplicação, o nosso desejo é trabalhar com EDs capazes de armazenar qualquer tipo de elemento e não apenas de números inteiros. Por exemplo, nosso interesse pode ser criar uma lista de alunos ou uma fila de processos a serem atendidos por um determinado sistema operacional, entre outros. Obviamente, alunos e processos são entidades complexas (por exemplo, o registro de um aluno pode conter nome, matrícula, data de nascimento, entre outros dados), uma vez que são compostas por outros tipos de dados mais simples, e não pertencem aos tipos primitivos de qualquer linguagem de programação de propósito geral.

Continuar a ler

Paralelização de Aplicações com OpenMP

Introdução

O OpenMP é uma norma/API para programação paralela em sistemas de memória partilhada para as linguagens de programação C, C++ e Fortran, desenvolvida e mantida pelo OpenMP Architecture Review Board. Disponibiliza uma alternativa simples e portável a soluções de mais baixo nível como POSIX Threads, e é suportado por vários compiladores como o GCC ou ICC, e deverá chegar em breve ao Clang/LLVM.

O OpenMP distingue-se de outras soluções para suporte a paralelismo em memória partilhada pelo seu nível de abstracção, na medida em que o essencial das suas funcionalidades é obtido através de um conjunto de directivas do compilador que especificam de forma declarativa como é que diferentes partes do código podem ser executadas em paralelo. Adicionalmente, um compilador que não suporte OpenMP pode simplesmente ignorar estas directivas, continuando a aplicação a funcionar correctamente (embora de forma sequencial). Contudo, aplicações mais complexas podem também necessitar de chamadas a funções de mais baixo nível (disponibilizados pela API do OpenMP), e que tornam a compilação da aplicação dependente do OpenMP.

Continuar a ler

Desbravando o goto!

Introdução

O assunto dos gotos é um dos tópicos mais discutidos nos fóruns de programação. Várias críticas são reiteradas para a sua não utilização, mas será o goto assim tão maléfico? Não terá realmente a sua utilidade? Com este artigo espero convencê-lo que o goto, como uma ferramenta de programação que é, tem lugar na sua caixa de ferramentas.

Continuar a ler

Arduino: const vs #define

Longe vão os tempos em que os computadores possuíam quantidades irrisórias de memória RAM quando comparadas com os dias de hoje. Falo sim em quantidades na ordem dos kbytes de memória.

Actualmente os programadores descuram um pouco essa afinação e optimização na alocação de memória das suas aplicações, mas ainda existe um pequeno grupo onde ainda é necessário optimizar ao pormenor a alocação de memória, refiro-me então às áreas da robótica e electrónica, de um modo geral na utilização de micro-controladores.

Continuar a ler