heap sort

The heapsort algorithm can be divided into two partes
- Step 1: a heap is built out of the data
- Step 2: a sorted array is created by repeatedly removing the largest element from the heap, and inserting it into the array.

The heap is reconstructed after each removal. Once all objects have been removed from the heap, we have a sorted array. The direction of the sorted elements can be varied by chossing a min-heap or mar-heap in the step one.

Complexity: O(n.log n)

Design algoritmica

-> Divisão e conquista (divide and conquer)
->Atacar/resolver um problema algorítmico em que a dimensão dos dados de entrada é N através  da divisão dos dados de entrada em partes mais pequenas (duas ou mais partes), aplicar a resolução (geralmente de modo recursivo )a cada uma das partes e finalmente fazer a combinação dos resultados obtidos de modo a obter a solução final.

Etapas:

1) Divisão dos dados N => P1,P2...
2) Conquista/resolução a cada uma das partes Pi
3)Combinação dos resultados para obter solução final

 Processo de divisão e conquista/recursivo) aplicado em ordenação por partes(merge sort)

Grafo

O que é um grafo?

Grafo é uma abstracção matemática, mais genérica do que a árvore, que serve para descrever organizações e armazenar informação, e que se apresenta estruturada de forma complexa

Para que serve um grafo?

Os grafos são usados para simular sistema de redes. 

Ex: Nas redes de transporte, podem ser usados para calcular custos associados aos percursos e determinar percursos óptimos.

Nas redes de comunicação podem ser usados para determinar percursos alternativos de encaminhamento de informação ou para verificar se o desligamento de parte da rede não impede o encaminhamento da informação, ou seja determinar a conectividade  da rede.

Propriedades do Grafo

Um grafo é uma colecção de vértices ou nós que são os elementos  que contêm informação que se pretende armazenar e de arestas que são os elementos que ligam os vértices.Um grafo tem pelo menos um vértice, mas pode não ter qualquer aresta.Cada aresta esta associada a um par de vértices, chamando-se esses vértices por vértices adjacentes.

Um conjunto de vértices ligados entre si e desligados dos restantes vértices chama-se por componente conexa. Um grafo diz-se conexo se só possuir uma componente conexa, senão diz-se que é um grado desconexo.

Um grafo diz-se nulo se possuir apenas vértices e diz-se completo quando entre cada par de vértices existe uma aresta. Um grafo com V vértices tem no máximo V*(V-1)/2 arestas, quando é um grafo completo.

Um caminho num grafo é uma lista de vértices, que  os sucessivos vértices estão ligados por arestas. Os vértices e as arestas de um caminho podem não ser distintos, pelo que, ao contrário de um árvore, em que só pode existir mais de um caminho entre dois vértices. O número de arestas do caminho determina o seu comprimento.

Um caminho diz-se simples se não tiver arestas repetidas e diz-se elementar se todos os seus vértices forem distintos, Um circuito é um caminho que começa e acaba no mesmo vértice. Um circuito é simples se não possuir arestas repetidas e designa-se por ciclo se todos os seus vértices, com excepção inicial forem distintos. Assim sendo, um ciclo atravessa pelo menos três vértices distintos. 

Álgebra relacional

Álgebra relacional e uma linguagem procedimental que define operações sobre a base de dados, através de expressões algébricas. 

Operadores

Os cinco operadores básicas que definem a álgebra relacional, no sentido em que não podem ser definidos a partir de outros operadores, são os seguintes:

* Operadores sobre conjuntos:  Os operadores básicos sobre conjuntos são a união e a diferença;

* Selecção: Também chamado restrição, é um operador unário que produz o conjunto de tuplos (campos )de uma relação  R que satisfazem uma condição;

* Projecção: Operador unário que produz a mesma relação apenas com as colunas especificas, na ordem especificada;

* Produto:Operador unário binário que aplicado ás relações R e S, produz uma relação cujo o esquema é a união dos esquemas de R e S, e que combina cada tuplo de R com cada tuplo de S.

 # Selecção

A Selecção produz uma relação cujos  tuplos satisfazem a condição c. A condição c, é um predicado que pode envolver operadores aritméticos, operadores sobre texto, e conjunções, disjunções ou negações, actuando como um filtro da relação.

Exemplo:

Conclusão: Faz-se uma selecção de uma coluna com uma condição, que neste caso a condição é Ects > 4

O predicado é aplicado a cada linha individualmente, e o seu resultado determina a inclusão ou não da linha na relação resultante. Portanto, não é possível ter na condição de selecção operações sobre mais tuplos do que esta em causa .

#Projecção

A projecção (R) produz uma relação com os mesmo tuplos de R,mas apenas com as colunas constantes da lista L.
Esta lista pode não ter apenas nomes de colunas de R, mas também:
*Uma indicação para renomear colunas de esquema R;
* Uma expressão aritmética 

Exemplo:

π_{Nome,Ects   -->} Créditos

  

Nome	Créditos
Base de Dados	5
Programação	4

Conclusão: 

Com a projecção a coluna Ects, passou a chamar-se Créditos 

Outro exemplo:

π _{Nome, ECTS * 26  ->  Horas}

Nome	Horas
Base de Dados	130
Programação	104

#Produto

O produto permite combinar informação de relações diferentes.O produto de duas relações R e S - R X S resulta numa relação que é a união dos esquemas de R e S, alterando se necessário, colunas que tenham nomes iguais  e cujos tuplos sejam a combinação de cada tuplo de R  com cada tuplo de S.

Exemplo:

Nome                | Sigla         |ECTS    |                     |   Sala   |    Lugares   |
_____________ | _______ | _______ |                    | ______ | _________ |

Base de Dados  | BD            | 5           |                     | S1        | 30              |

Programação     | PG            |4            |                     | S2        | 40              |  

Produto:

Nome                | Sigla         |ECTS   |   Sala   |    Lugares   |
_____________ | ________ | ______ | _____ | _________

Base de Dados  | BD            | 5          | S1        | 30              |

Base de Dados   | BD           |5           | S2        | 30              |

Programação     | PG            |4           |S1          |30              |  

Programação     | PG            |4           | S2        | 40              |   

                   

Research sub-strings in strings: LSD radix sort

void lsd_sort(StringElementsArray * a, int N, int W, int R) {
    int i,r,d,c;
    int * count = newIntArray(R + 1);
    StringElementsArray aux; // aux Array
    createStringElementsArray(&aux,N); // create aux array

    for (d = W-1; d >= 0; d--) {

        // reset count[] array
        for (i = 0; i < R+1; i++)
            count[i]=0;

        // compute frequency counts
        for (i = 0; i < N; i++)
            count[a->str[i][d] + 1]++;

        // transform counts to indicies
        for (r = 0; r < R; r++)
            count[r+1] += count[r];

        // distribute
        for (i = 0; i < N; i++) {
            c = a->str[i][d];
            aux.str[count[c]] = a->str[i];
            aux.len[count[c]] = a->len[i];
            count[c]++;
        }

        // copy back
        for (i = 0; i < N; i++) {
            a->str[i] = aux.str[i];
            a->len[i] = aux.len[i];
        }

        // Trace of iterations for LSD string sort
        printf("\nLSD Sorted List (right to left) after sorting key %d:\n",d);
        for (i = 0; i < N; i++)
            printf("\t%s\n",a->str[i]);
    }

Research sub-strings in strings: KeY Index Counting

Key- indexed countig

  
void key_index_counting(StringKeyElementsArray * a, int N, int R) {

    int i,r,c;
    int * count = newIntArray(R + 1);
    // reset count[] array
    for (i = 0; i < R + 1; i++)
        count[i]=0;
    StringKeyElementsArray aux; // aux Array
    createStringKeyElementsArray(&aux,N); // create aux array

    // compute frequency counts
    for (i = 0; i < N; i++)
        count[a->keys[i]]++;

    // transform counts to indicies
    for (r = 0; r < R; r++)
        count[r+1] += count[r];//frequencias acumuladas

    // distribute
    for (i = 0; i < N; i++) {
        c = a->keys[i] - 1;
        aux.str[count[c]] = a->str[i];
        aux.len[count[c]] = a->len[i];
        aux.keys[count[c]] = a->keys[i];
        count[c]++;
    }

    // copy back
    for (i = 0; i < N; i++) {//4º passo
        a->str[i] = aux.str[i];
        a->len[i] = aux.len[i];
        a->keys[i] = aux.keys[i];
    }

                                                                            

MIPS: Addressing and Decisions( Endereçamento e decisões)

Decisions in MIPS (decisões)


Instruction for decisions in MIPS( instruções de decisão) :

*  beq registo1, registo2, L1
*  beq means "branch if equal"

Same as (C): 
  if ( registo1== registo2) goto L1

Instruction supplementary decision in MIPS(Instrução de decisão complementar):

* bne registo1, registo2, L1
* bne means “branch if not equal”

Same as (C): 
  if ( registo1 != registo2) goto L1

"Goto" statement in MIPS(instrução "goto"):

It is the jump instruction ("jump") jumps directly to "label" indicated 

without checking any condition.

For example:

In C:

if (i == j) f=g+h; 

else f=g-h; 

 pseudo instruction                MIPS

if(condicion) goto TRUE;    beq $S3,$S4,TRUE
Code FALSE;                     sub $S0,$S1,$S2
goto NEXT;                         j NEXT
TRUE code TRUE;          TRUE
                                           add $S0,$S1,$S2
NEXT:                               NEXT


Another example:

In C:

do { 
g = g + A[i]; 
i = i + j;

} while (i != h); 

where g,h,i,j,base of A, $s1, $s2, $s3, $s4, $s5

pseudo instruction:

LOOP:  g=g+A[i]
             i=i+j;
             if(i!=h) goto LOOP;


MIPS:

LOOP : sll $St1,$S3,2 # St1=4*I
             //Construction of the vector
             add $t1,$t1,$S5  #St1=addr A[i] (address position for A[i])
              lw $t1,0($t1) # $t1=A[i]
             add $S1,$S1,$t1 # g= g+A[i]
             add $S3,$S3,$S4 # i=i+j
             bne $S3,$S2,LOOP # goto LOOP
                                               # if(i!=h)

Análise de complexidade algoritmica

Razões para análise algorítmica:
→prever o seu desempenho (performance)
→comparar algoritmos
→estabelecer garantias para o algoritmo (T(N)<=Tmax)
T(N)=tempo de execução dum algoritmo com input size=N
→perceber a base teórica subjacente
→evitar bugs de performance

Técnicas algorítmicas:
→dividir e conquistar
→programação dinâmica

Exemplo:
Procurar um valor num determinado vector
Int procuraValor (Int *v,Int n, Int val)
{Int i;
    For(i=0;i<n;i++)
       If(v[i]==val)
            Return i;
Return -1;
}

Num algoritmo com tamanho de n dados ,temos 3 situações:

→melhor caso(best case ): situação mais favorável em termos de configuração dos dados na entrada T(N)=B(N)
→pior caso (worst case): situação mais desfavorável T(N)=W(N)
→caso médio (average case): e determinado estatisticamente o número médio de operações básicas T(N)=A(N)

Int s=0; // está instrução e executada 1 vez
For(i=0;i<n;i++)
S=+v[i] Única Instrução que acede ao vector(modelo de custo usado nesta análise poderia por exemplo: considerar apenas as instruções se acesso ao vector(ler ou escrever))

estas instruções são executadas n vezes

Análise algoritmica

* Utilizar metodologias  e/ou técnicas de análise de desempenho de algoritmos com o objetivo de:

→prever a sua performance temporal e espacial
→comparar algoritmos entre si
→estabelecer garantias de desempenho
→perceber a base teórica subjacente
→evitar bugs de performance

Abordagem empírica

1)variar o tamanho dos dados da entrada n(regra :aumentar o tamanho n, multiplicando o por 2)
2)medir para cada valor de n, o tempo do algoritmo
3)tentar encontrar a lei (função) matemática que melhor se afasta aos dados. Para isso aplica-se regressão LINEAR aos dados log-log

Multiplicidade

* Os relacionamentos têm uma multiplicidade, que especifica o número de elementos de cada entidade que participam neles

Exemplo anterior:
- Sabe -se que um aluno só se pode inscrever em um só um "curso"
- Sabe-se que num "curso" se podem inscrever nenhum ou N alunos

Modelo E R

Modelo E R

* Representa apenas aspectos estáticos( entidades , os seus relacionamentos e a as propriedades de ambas)
* Destina-se a melhorar o conhecimento do utilizador sobre os dados

Entidade: qualquer objecto indentificavel , por exemplo: aluno,curso, cliente....

Propriedade: é informação/dado sobre uma dada entidade, como por exemplo: idade, nome, morada,...

Relacionamento: entidade que serve para ligar dias ou mais entidades, como por exemplo: frequenta, tem....

* Existe um relacionamento "inscrito" entre as entidade "aluno" e "curso"

* Esse relacionamento é caracterizado pelo atributo "data"

* As entidades "aluno" e "curso" têm os atributos mostrados

Blogs

Venho com uma nova categoria no meu blog.

Em vez de só criar post relacionados com apontamentos sobre o meu curso(Engenharia Informática), decide que também é preciso divulgar novos blogs na minha área de eleição(Informática) e porque não começar com o Blog: "Pegada Digital" http://daft-hferreira.blogspot.pt/ .

O Blog "Pegada Digital" é um blog relacionado com área da informática mas com algumas pequenas curiosidades, também como alguns apontamentos de conteúdos relacionados com a Informática.

O Blog/Site "FU2ion" http://fu2ion.azurewebsites.net/é um site  de entretenimento sobre diversas áreas, com foco na área das Novas Tecnologias.

Por enquanto são estes blogs que eu tenho conhecimento. Mas gostava que vocês deixa-sem em comentário mais blogs/sites para eu fazer a sua divulgação. É desta maneira que todos nós conseguimos manter actualizados.

Gestor de Processos

Um processo pode executar-se no processador ou á espera de ter possibilidade de se executar. O ciclo de vida dos processos vai evoluir desde a sua criação por três estados fundamentais: o primeiro corresponde a deter o processador e portanto, estar em Execução; quando o processo não se pode executar por não ter acesso ao processador está no estado Executável. O terceiro estado, Bloqueado, corresponde a um situação diferente em que o processo mesmo que tivesse o processador não poderia avançar porque uma condição lógica o impedia (já anteriormente nos apareceram funções que esperam pela terminação de outro processo e situações em que um processo se bloqueia á espera de um acontecimento).

·         Em execução- Processo a usar o processador

·         Executável- Processo que pode prosseguir a sua execução e que tal necessita que lhe seja atribuído processador

·         Bloqueado- Processo que espera um acontecimento que enquanto não ocorrer o impede de continuar a executar-se.

As transições entre os três estados correspondem aos seguintes acontecimentos:

·         Executável-> Em execução- O processo foi seleccionado para execução pelo despacho porque é mais prioritário do que o processo corrente ou porque este ultimo deve abandonar o processador (terminou ou bloqueou-se)

·         Em execução-> Executável- Um outro processo na lista dos executáveis tem maior prioridade e o despacho efetua a comutação

·         Em execução-> Bloqueado- O processo tem de interromper a sua execução porque espera um acontecimento sem o qual não pode continuar a executar o respectivo programa.

·         Bloqueado-> Executável- O acontecimento que mantinha o processo bloqueado ocorreu e este passa novamente a poder executar-se. Passa para a lista de executáveis, podendo, se for o mais prioritário, passar de seguida a executar-se ou mais tarde quando for seleccionado pelo despacho.

Quatro objectivos diferentes relacionados com este tipo de gestão:

·         Optimizar a produtividade do sistema, executando o maior numero de programas possível num dado período de tempo (determinado throughput do sistema);

·         Procurar equilibrar a carga do sistema de forma a dar um serviço relativamente uniforme aos diversos clientes;

·         Dotar o sistema de grande reactividade as condições externas;

·         Minimizar o tempo médio para completar a execução de vários programas 

Processos: modo computacional

A multi programação consiste na execução em pseudoparalelismo de vários programas na mesma máquina, onde os vários fluxos de execução são multiplexados no tempo, cada fluxo é designado por processo.

Os elementos principais que constituem um processo são um espaço de endereçamento, que normalmente se divide numa região para o código, outra para a pilha e outra para os dados globais e alocados dinamicamente (heap). Cada processo tem um estado que pode ser salvaguardado e posteriormente reposto, de forma a permitir a comutação entre processos. Um processo tem ao seu dispor um reportório de operações, que consiste nas instruções máquina do processador e nas operações exportadas pelo sistema operativo (chamadas de sistema).

O modelo de segurança baseia-se no isolamento entre processos, o que significa que os processos não podem interferir uns com os outros e na existência de um utilizador que é o dono do processo, em função do qual são definidas as acções que o processo pode executar sobre os restantes recursos do sistema operativo, uma vez que estes acessos são sempre mediados pelo núcleo.

Os processos organizam-se normalmente de forma hierárquica, em que um processo ao criar outro estabelece uma relação de pai-filho nessa hierarquia. Algumas informações são herdadas do processo pai para os processos filhos.

pid_t fork(void)- chamada ao sistema para a criação de um novo processo

1- Quando um processo invoca a chamada ao sistema fork() o sistema operativo vai executa-la em modo protegido (modo sem restrições de execução)

2- O Sistema Operativo verifica se o processo que invoca o fork() ainda não esgotou o número máximo de processos filhos e em caso afirmativo executa o fork()

3- O processo inicial é duplicado (estruturas de dados do núcleo, zonas de memória, etc..) e ao novo processo é atribuído um novo PID

4- O novo processo integra a lista de processos candidatos a usar o  CPU

5- O Sistema Operativo retorna o PID do filho ao Pai e zero ao filho. A execução de cada um destes processos é retornada na instrução seguinte ao fork()

Um processo pode ser visto como objecto, com propriedades e operações. As propriedades fundamentais são um identificador, o ficheiro com o programa executável, o seu espaço de endereçamento, prioridade, estado de execução, processo pau, canais de E/S, ficheiros abertos quotas de utilização de recursos, contexto de segurança e ambiente utilizador

As operações definem a interface do sistema operativo para manipular processos e incluem operações para criar um novo processo auto – terminar, para eliminar outro processo, para esperar pela terminação de outro processo, para suspender a execução de um processo, ou auto suspender-se e para ler o estado do processo.

            A operação sobre processos que se desvia mais do modelo computacional genérico é a operação de criação de processos Unix (fork), que cria um novo processo absolutamente idêntico ao processo pai. Para o processo filho executar um programa diferente do pai, é necessário que este invoque uma segunda função (exec) que altera o programa a ser executado.

exec():
Quando um processo invoca a chamada ao sistema execxx o núcleo do Sistema Operativo vai reescrever as zonas de memória associadas ao processo (filho zona estática e dinâmica de dados e código) com a informação existente no ficheiro executável indicado como parâmetro. A execução do processo é iniciado no main() do novo código.

Em Unix, o tratamento das excepções e de acontecimentos assíncronos tem particular importância. Os signals são muito semelhantes ao modelo de rotinas assíncronas e foram a ideia original desta extensão ao modelo de programação estruturado. Os acontecimentos assíncronos podem ser analisados a um processo em execução através da activação de um signal. Os acontecimentos susceptíveis de gerarem um signal tem origens muitos diversas, e são referenciados num ficheiro de texto (signal.h) que indica o respectivo nome lógico e o valor inteiro que é usado para codifica-lo internamente no núcleo.

Organização do Sistema Operativo

O sistema operativo é usualmente composto por três entidades: o núcleo, as bibliotecas de chamadas sistema e os processos de sistema.

O núcleo implementa o mecanismo de base do sistema operativo. Em particular, a gestão dos processos, da memória, dos ficheiros, das E/S e a comunicação entre processos.

O funcionamento do núcleo é fortemente influenciado por mecanismos de hardware que permitem garantir o seu funcionamento seguro. A segurança do sistema operativo advém da existência de um isolamento entre os processos dos utilizadores, e entre estes e o núcleo do sistema operativo.

O isolamento é garantido pela gestão da memória que só permite determinadas posições de memória sejam acessíveis por um utilizador. Mas como o funcionamento do núcleo tem de ser partilhado por todos os processos é forçado que exista um mecanismo não controlado directamente pelos programas utilizador para gerir estas alterações do espaço de endereçamento.

Esta componente de hardware gere a dualidade de execução do processador em modo de utilizador e modo núcleo: o modo utilizador restringe o acesso a determinadas posições de memória e certas instruções que podem ultrapassar o isolamento como as que interagem directamente como os periféricos ou com as instruções; em modo núcleo não existem tais restrições, sendo este o modo que o núcleo do sistema operativo se executa.

As chamadas sistema são implementadas por um função que invoca a excepção (trap) que transfere o controlo para o núcleo e automaticamente coloca o processador no modo de execução núcleo.

No núcleo é feita a escolha do código apropriado que implementa a chamada ao sistema em causa. No final da chamada, a instrução de retorno de interrupção devolve o controlo para a função de biblioteca que, por sua vez retorna para o código do utilizador.

Os processos sistema executam funções que podem ser delegas em processos autónomos, de forma a reduzir a complexidade do núcleo ou aumentar a sua robustez. Estes processos executam-se em modo utilizador mas pertencem ao sistema operativo pelo que tem privilégios de administrador, contudo, para invocar funções do sistema tem de o fazer através das chamadas ao sistema, o que é menos eficiente do que se a execução fosse directamente do núcleo.

Uma organização do núcleo em camadas generaliza o conceito de protecção entre modo núcleo e modo utilizador, dividindo o núcleo em várias camadas que implementam diferentes funcionalidades e obrigando as camadas mais externas a invocar funções das camadas internas através do mecanismo semelhante aos das chamadas do sistema.

Chamadas de sistemas

-> fork()
pid_t fork(void)- chamada ao sistema para a criação de um novo processo

1- Quando um processo invoca a chamada ao sistema fork() o sistema operativo vai executa-la em modo protegido (modo sem restrições de execução)
2- O Sistema Operativo verifica se o processo que invoca o fork() ainda não esgotou o número máximo de processos filhos e em caso afirmativo executa o fork()
3- O processo inicial é duplicado (estruturas de dados do núcleo, zonas de memória, etc..) e ao novo processo é atribuído um novo PID
4- O novo processo integra a lista de processos candidatos a usar o CPU
5- O Sistema Operativo retorna o PID do filho ao Pai e zero ao filho. A execução de cada um destes processos é retornada na instrução seguinte ao fork()

->exit()
void exit(int estado)

1- Quando um processo invoca a chamada exit() o núcleo do Sistema Operativo recolhe todos os recursos associados com o processo em causa
2- No entanto, o núcleo do Sistema Operativo preserva o código de finalização enviado como argumento da chamada exit() para terminar a sua recolha pelo processo que termina
3- Só se perde referência completa a um processo desde o seu pai recolher o seu código de finalização

-> exec():

Quando um processo invoca a chamada ao sistema execxx o núcleo do Sistema Operativo vai reescrever as zonas de memória associadas ao processo (filho zona estática e dinâmica de dados e código) com a informação existente no ficheiro executável indicado como parâmetro. A execução do processo é iniciado no main() do novo código

-> wait()

1-Verifica se contêm algum filho a executar (caso falhe, retorna <0)
2- Verifica se algum filho terminou
3- Se nenhum dos filhos terminou o processo fica bloqueado até que algum destes termine
4- Recolhe o estado do primeiro processo filho que terminar
5- Retorna o PID do processo que terminou

-> waitpid()

Contêm um comportamento semelhante á chamada wait(), no entanto bloqueia somente para aguardar por um PID especifico(passado como argumento) termine.

Como abordar um Problema? Dividir para Conquistar

Projectar o  programa antes de programá-lo

Nunca comece a programar a partir do nada. Deve-se sempre esquematizar alguns pseudo-códigos explicando o que o seu programa vai fazer (em um nível mais elevado) antes de começar a programar.

Quando se começa a escrever um programa sem ter pensado nele antes, fica difícil visualizá-lo como um todo. Criando um rascunho prévio do programa, podem aparecer várias abordagens do problema e as dificuldades ficam mais fáceis de serem superadas. Esquematizar o programa ajudar a fixar exactamente o que se deseja e economiza-se bastante tempo em frente ao monitor na tentativa de escrever um programa que cumpra o desejado.

Escreva um código legível

Escrever um código legível é muito importante para facilitar o entendimento de um programa. Até para o próprio criador do código. Um programa claro e auto-explicativo fica mais difícil  de se perder e torna muito mais fácil a depuração.

Comente seu código enquanto escreve, não depois

Comentários são ferramentas muito úteis para tornar o código mais legível. É interessante comentar tudo que não seja muito claro. Não comente algo que seja óbvio (p/ ex.: "i := 0 { Atribui ovalor 0 à variável i }" ). Comente algo como: "x:= 40 - Lenght(frase)/2 { x recebe a posição para frase ficar centralizada }".

Em programas muito grandes ou complicados, é interessante criar um cabeçalho comentado em cada função, definindo exactamente o que espera-se que ela faça, quais suas entradas e quais suas saídas. O pseudo-código rascunhado pode ser muito útil para isso. Agindo assim, não se precisa ler diversas linhas de código para saber o que uma função faz.

É recomendável que se escreva os comentários enquanto se escreve o programa, pois é menos provável que se escreva alguma coisa útil ou significativa depois. Escreva enquanto programa e seus comentários serão muito mais completos.

Utilize funções e procedimentos curtos e objectivos

Evite sempre funções/procedimentos grandes que englobem todo tipo de processamento. Separe algoritmos distintos em suas próprias funções/procedimentos. Projecte a  sua grande função/procedimento em várias pequenas, de forma que seu programa fique mais fácil de ler e entender.

Dessa forma, cada parte do seu programa fica bem definida e torna-se muito mais fácil escrevê-lo, pois pode-se fazê-lo passo a passo. Dessa forma, a cada parte que se termina, pode-se verificar se ela está correta. Além disso a localização de um problema no programa também fica facilitada, pois ele se restringirá a um bloco menor de código.

Conclusão:

Lembre-se que a maior parte do tempo que se gasta programando é corrigindo e modificando código existente. Relativamente pouco tempo é realmente utilizado para adicionar coisas novas. Isso significa que você gastará muito tempo lendo o seu código, então faz sentido gastar algum tempo aprendendo a escrever um código legível. Código legível é fácil de escrever, fácil de depurar e fácil de manter. Você realmente sai ganhando!

Guia prático para resolução de problemas de programação 

1) Entender o problema

Estar certo de que tenha entendido o problema;
* O que é a entrada?
* O que é a saída?

2) Resolver o problema à mão

Resolva pequenas instâncias do problema à mão;
* O que acontece?
* Pensar  em casos variados;
* Pense em como (qual algoritmo) você utilizou para resolver o problema.

3) Definir o algoritmo

* Defina precisamente o algoritmo a ser utilizado
* Rascunhe as etapas do programa

4) Programar

* Como escrever o algoritmo na linguagem utilizada?
* Que estrutura de dado utilizar?
* Divida o programa em partes menores;

* Escreva um programa de fácil leitura;
* Pense nos casos patológicos.

4) Depurar

* Explique o programa para si mesmo;
* Por que funciona?
* A leitura de dados está sendo feita correctamente?
* Variáveis inicializadas?
* Verificar casos patológicos;
* Localizar o erro restringindo os blocos de códigos (cercando o erro)
* Comandos e loops aninhados correctamente?