Lesson01

Apresentação e funcionamento

• Corpo docente: Alexandre Francisco; Luís Russo; Francisco Santos (no Tagus).
• Horários de dúvidas afixados na página da disciplina.
• Aulas teóricas: quinta (VA5) e sexta (AM) das 13:00 às 14:30.
• Aulas práticas: quarta das 12:00 às 13:30 (LAB 13); sexta das 10:30 às 12:00 (LAB 10) e das 15:30 às 17:00 (LAB 13).
• As aulas práticas terão início na quarta-feira, 25 de setembro.
• Não decorrerá qualquer avaliação durante as aulas de laboratório.
• O guia de laboratório será disponibilizado na semana anterior à aula para preparação da mesma.
• Os projectos serão realizados em grupos de 2 ou 3 alunos. A inscrição dos grupos decorrerá entre 19 e 24 de setembro. A inscrição é atómica.
• Os projectos serão sujeitos a avaliação automática com recurso ao sistema Mooshak.

Programa

1. Linguagem de programação C.
2. Análise e estudo da eficiência de algoritmos e estruturas de dados.
3. Algoritmos de ordenação: inserção directa, selecção directa, bubblesort, quicksort, shellsort, heapsort e radixsort.
4. Estruturas de dados: pilhas, filas de espera, filas de prioridade, amontoados, árvores e tabelas de dispersão.
5. Grafos: representação, pesquisa em largura e profundidade, àrvores abrangentes de menor custo, caminhos mais curtos de fonte única.

Avaliação

• Componente Teórica (T): média dos 2 testes, com repescagem de um deles; nota mínima de 8.0 / 20 na média dos testes.
  • 1º Teste: 23 de Novembro de 2013
  • 2º Teste: 8 de Janeiro de 2014
  • Repescagem: 25 de Janeiro de 2014 (os alunos poderão escolher repetir apenas um dos testes ou ambos os testes)
• Projecto (P): média de 2 entregas; sem nota mínima; nota de cada aluno ponderada pela discussão final na última semana de aulas.
  • 1ª Entrega: 4 de Novembro de 2013
  • 2ª Entrega: 6 de Dezembro de 2013
  • Os enunciados são publicados 15 dias antes da data de entrega.
• Nota Final (NF): 60% Componente Teórica; 40% Projecto.
• Não serão consideradas classificações obtidas no projecto em anos anteriores. Todos os alunos a frequentar a disciplina para aprovação ou que pretendam fazer melhoria de classificação serão avaliados em todas as componentes de avaliação. Os alunos não inscritos não serão avaliados.
• Não serão tolerados quaisquer tipos de fraude em qualquer componente da avaliação. Qualquer tentativa de fraude será comunicada aos orgãos do IST e levantado o respectivo processo disciplinar.

Referências

• B. Kernighan e D. Ritchie, The C Programming Language, 1988, Prentice Hall
• R. Sedgewick, Algorithms in C: Parts 1-4, 1998, Addison-Wesley Publishing Company
• T. Cormen, C. Leiserson, R. Rivest, C. Stein, Introduction to Algorithms, 2001, McGraw? Hill e MIT Press
• Material de apoio na página da disciplina.
• man pages, em particular a secção 3.
  • E.g., para consultar documentação a respeito da função printf basta executar o comando man 3 printf na linha de comandos.

Introdução à Linguagem C (K&R: Capitulo 1)

• Desenvolvida em 1972 por Dennis Ritchie, nos Bell Labs, para utilização no sistema operativo UNIX.
  • Mais acerca do Unix: Wikipedia; Bell Labs.
• O standard ANSI C (ISO/IEC 9899:1990) foi adoptado pela ISO em 1990.
• Linguagem de alto nível, mas que permite acesso de baixo nível a memória e dispositivos.
• A maioria dos sistemas operativos actuais (Linux, Windows, MacOS?, etc) continua a ser programado em C.
• Influenciou o desenvolvimento de diversas linguagem como: Java, C++, C#, Perl, PHP, JavaScript?, etc.

Hello world

     1	#include <stdio.h>
     2	#include <stdlib.h>
       
     3	int
     4	main(int argc, char * argv[])
     5	{
     6	    printf("Hello, world!\n");
       
     7	    return EXIT_SUCCESS;
     8	}

• Nas linhas 1 e 2 incluímos duas "bibliotecas" de funções.
• Nas linha 3 temos declarado o tipo de retorno da função main, definida na linha 4. Todos os programas têm uma função main e esta é sempre a primeira a ser executada.
• Nas linhas 6 e 7 temos as instruções associadas à função main. Notar que as instruções são separadas por ; e aparecem entre chavetas (linhas 5 e 8).
• Neste exemplo temos tuas instruções:
  • chamada à função printf, disponível na biblioteca stdio.h, cujo único argumento aparece entre parênteses.
  • instrução de saída return que retorna o valor de saída da função, neste caso a constante EXIT_SUCCESS disponível na biblioteca stdlib.
• O argumento da função printf, linha 6, é uma cadeia de caracteres:
  • as cadeias de caracteres aparecem sempre entre aspas;
  • existem algumas sequências de caracteres especiais que são interpretadas, exemplos: \n que representa uma nova linha; \t que representa o tab; \b que representa o backspace; \" que representa uma aspa; \\ que representa a própria \. A lista completa está na man page da função printf.
• As funções podem tomar qualquer nome definido sobre o alfabeto {0,...,9,A,...,Z,_,a,...,z}, com excepção que não podem começar por um digito.
• Como vamos ver mais tarde, as funções podem ser definidas em múltiplos ficheiros.
• Os programas em C têm de ser compilado para que possa ser executado. Assumindo que o exemplo acima está guardado no ficheiro hello.c, podemos compilar e executar o nosso programa da seguinte forma:

[aplf@darkstar ~]$ gcc -Wall -ansi -pedantic -o hello hello.c
[aplf@darkstar ~]$ ./hello 
Hello, world!
[aplf@darkstar ~]$

• Podemos obter informação a respeito das opções utilizadas no comando gcc na man page.

Ambiente de desenvolvimento

Sistema operativo Unix-like, por exemplo uma qualquer distribuição de GNU/Linux (nos laboratórios temos Debian), um dos BSD, incluindo o Mac OS X. Nas aulas vamos utilizar GNU C Compiler (gcc), o gdb e o valgrind para debugging, e um qualquer editor de texto (vi, emacs, vim, gedit, kate, textmate, sublime, jedit, etc.). Podem existir outros compiladores de C nos vossos sistemas, por exemplo o Clang no FreeBSD? e no Mac OS X, e que podem utilizar. Notar no entanto que os projectos serão compilados com o gcc no sistema de submissão.

Nota importante: quer o compilador quer as outras ferramentas podem não vir instaladas por omissão no sistema, caso em que teremos de as instalar (normalmente disponíveis através do gestor de pacotes).

Embora nas aulas não seja utilizado um IDE (Integrated Development Environment), seguindo a escolha na maioria das disciplinas da LEIC, sugerimos o Eclipse a todos aqueles que preferirem utilizar um IDE nesta disciplina.

Unix/Linux Command Reference. Linux Command. Command line reference for common operations.

No Técnico existe pelo menos um repositório de onde podemos fazer download de várias distribuições de Linux ou de um dos BSD: http://darkstar.ist.utl.pt/

É também possível aceder a um dos servidores disponíveis no IST e que têm todas as ferramentas necessárias, nomeadamente ao sigma.ist.utl.pt e ao nexus.rnl.ist.utl.pt. Para aceder a partir de um sistema Unix-like basta utilizar os comandos ssh, scp, e sftp para obter acesso a shell e para transferir ficheiros. A partir de um sistema Windows sugerimos a utilização do putty e ferramentas associadas (http://www.putty.org/).

Para instalar o ambiente de desenvolvimento em Mac OS X sugerimos seguir as instruções da Apple a respeito das Command Line Tools for Xcode package e do próprio Xcode. Ou, em alternativa, a utilização do Fink e/ou do OS X GCC Installer. No caso do Windows recomendamos o MinGW ou o Cygwin.

C vs Python (factorial como exemplo)

O factorial em python pode ser implementado como:

def factorial(n):
  if n == 0:
    return 1
  else:
    return n*factorial(n-1)

Em C podemos implementar da seguinte forma:

int factorial (int n)
{
  if (n == 1) {
    return 1;
  }
  else {
    return n*factorial(n-1);
  }
}

Principais diferenças:

• tipificação estática em C, a linguagem não permite tipificação dinâmica, o tipo de cada variável é definido na compilação;
• blocos delimitados por chavetas em vez de indentação, indentação é apenas utilizada em C para tornar o código mais legível e, se o bloco só contém uma instrução as chavetas são opcionais (excepto no caso do corpo das funções, onde as chavetas têm de ocorrer sempre);
• em C temos de declarar o tipo de dados do valor de retorno da função, no caso do factorial o tipo do retorno é int;
• tipos básicos em C: char, int, long int, double e float;
• tipos complexos: estruturas, uniões, tabelas, etc.
• todos os parâmetros são precedidos pelo seu tipo, no caso do factorial o parâmetro n é do tipo int;
• as condições nas estruturas de controlo aparecem entre parênteses, como acontece no caso do if no exemplo do factorial;
• todas as instruções terminam com ; (ver por exemplo a instrução de retorno no exemplo acima).

Mais detalhes em C for Python programmers.