Manual de Docência para a disciplina de Algoritmia e Programação

Engenharia Informática, 1º ano

José Manuel Torres

 

 

Número de horas do programa: 60 horas

Número de horas Semanal: 4 Horas

Número de horas por aula: 2 aulas de 2 h cada

 

Programa da Disciplina:

1.      Algoritmos e Computação

1.1  Noção de Algoritmo

1.2  Representação de Algoritmos

                                      1.2.1      Linguagem auxiliar (pseudo-código)

                                      1.2.2      Diagrama de fluxo (fluxograma)

                                      1.2.3      Linguagem de programação

1.3  Prova e Teste de Algoritmos

                                      1.3.1      Seguimento de algoritmos

                                      1.3.2      Prova matemática de algoritmos

                                      1.3.3      Teste de algoritmos

1.4  Programação "top-down" e "bottom-up"

1.5  Resolução de Problemas

                                      1.5.1      Análise do Problema

                                      1.5.2      Especificação do Programa

                                      1.5.3      Codificação do Programa

                                      1.5.4      Teste e Refinamento do Programa

                                      1.5.5      Geração da Documentação

                                      1.5.6      Manutenção do Programa

Objectivos:

Introduzir a noção de algoritmo e de problema; apresentar metodologias para representar algoritmos; introduzir as diversas etapas no desenvolvimento de um algoritmo para resolução de problemas.

Bibliografia principal:

·        Damas, Luis “Linguagem C”, Editora FCA, ISBN 972-722-156-4 (capitulo 1)

·        Kernighan, Brian W. "The C Programming Language", Prentice-Hall International, 1988 (capitulo 1)

·        Sampaio, Isabel; Sampaio, Alberto “Fundamental da Programação em C”, Editora FCA, ISBN 972-722-130-0 (capitulo 1)

 

2.      Introdução à Programação

2.1  Conceitos de programa e software

2.2  Tipos de software

2.3  Linguagem máquina, assembly e de alto nível

2.4  Programação em linguagens de alto nível

                                      2.4.1      Programa fonte

                                      2.4.2      Compilador

                                      2.4.3      Interpretador

                                      2.4.4      Programa objecto

                                      2.4.5      Bibliotecas

                                      2.4.6      Programa executável

2.5  Principais linguagens de programação de alto nível e suas aplicações

Objectivos:

Introduzir a noção de programação, software e diversos tipos de linguagens de programação; apresentar o ciclo de desenvolvimento de um programa de software.

Bibliografia principal:

·        Damas, Luis “Linguagem C”, Editora FCA, ISBN 972-722-156-4 (capitulo 1)

·        Kernighan, Brian W. "The C Programming Language", Prentice-Hall International, 1988 (capitulo 1)

·        Sampaio, Isabel; Sampaio, Alberto “Fundamental da Programação em C”, Editora FCA, ISBN 972-722-130-0 (capitulo 1)

 

3.      Estruturas de controlo

3.1  Instruções simples e estruturadas

3.2  Instruções condicionais

                                      3.2.1      Instrução "if-then-else"

                                      3.2.2      Instrução de selecção "case"

3.3  Instruções repetitivas

                                      3.3.1      Instrução "while"

                                      3.3.2      Instrução "for"

3.4  Instruções "goto" e etiquetas (labels)

Objectivos:

Introduzir as diversas estruturas de controlo como ferramentas básicas para construir programas.

Bibliografia Principal:

·        Damas, Luis “Linguagem C”, Editora FCA, ISBN 972-722-156-4 (capítulos 3 e 4)

·        Kernighan, Brian W. "The C Programming Language", Prentice-Hall International, 1988 (capitulo 3)

·        Sampaio, Isabel; Sampaio, Alberto “Fundamental da Programação em C”, Editora FCA, ISBN 972-722-130-0 (capitulo 3)

 

4.      Tipos e declarações de dados, expressões e funções intrínsecas

4.1  Tipos de dados

                                      4.1.1      Tipos ordinais

                                      4.1.2      Tipos reais

                                      4.1.3      Tipo cadeia de caracteres

                                      4.1.4      Definição e conversão de tipos

4.2  Declaração de constantes

4.3  Operadores e expressões

                                      4.3.1      Definição de operando, operador e expressão

                                      4.3.2      Operadores aritméticos

                                      4.3.3      Operadores lógicos

                                      4.3.4      Operadores booleanos

                                      4.3.5      Operadores relacionais

                                      4.3.6      Regras de precedência na avaliação de expressões

4.4  Funções intrínsecas

Objectivos:

Introduzir a noção de tipos de dados, variáveis, constantes, operadores e expressões.

Bibliografia Principal:

·        Damas, Luis “Linguagem C”, Editora FCA, ISBN 972-722-156-4 (capitulo 2)

·        Kernighan, Brian W. "The C Programming Language", Prentice-Hall International, 1988 (capitulo 2)

·        Sampaio, Isabel; Sampaio, Alberto “Fundamental da Programação em C”, Editora FCA, ISBN 972-722-130-0 (capitulo 2)

 

5.      Variáveis indexadas e cadeias de caracteres

5.1  Introdução à indexação

5.2  Conceitos de vector e matriz

5.3  Utilização de vectores

                                      5.3.1      Pesquisa em vectores: linear e binária

                                      5.3.2      Ordenação de vectores: por selecção, por fusão, "Buble sort", por partição e troca

5.4  Utilização de matrizes

5.5  Utilização de cadeias de caracteres

                                      5.5.1      Conceito de cadeia de caracteres

                                      5.5.2      Operações sobre cadeias de caracteres

Objectivos:

Introduzir a utilização de tipos de dados indexados em programas e respectivos algoritmos de pesquisa e ordenação.

Bibliografia Principal:

·        Damas, Luis “Linguagem C”, Editora FCA, ISBN 972-722-156-4 (capítulos 6 e 7 )

·        Kernighan, Brian W. "The C Programming Language", Prentice-Hall International, 1988 (capitulo 5)

·        Sampaio, Isabel; Sampaio, Alberto “Fundamental da Programação em C”, Editora FCA, ISBN 972-722-130-0 (capitulo 7)

 

6.      Procedimentos e funções

6.1  Conceitos de procedimento e função

6.2  Variáveis locais vs globais

6.3  Procedimentos

                                      6.3.1      Introdução aos procedimentos

                                      6.3.2      Tipos de parâmetros

                                      6.3.3      Passagem de parâmetros por valor

                                      6.3.4      Passagem de parâmetros por referência

6.4  Funções

                                      6.4.1      Introdução às funções

                                      6.4.2      Diferenças relativamente aos procedimentos

                                      6.4.3      Parâmetros de entrada

                                      6.4.4      Parâmetro de retorno

6.5  Introdução à recursividade

Objectivos:

Introduzir a noção de programação estruturada; apresentar o conceito de função e procedimento. Definir o conceito de recursividade.

Bibliografia Principal:

·        Damas, Luis “Linguagem C”, Editora FCA, ISBN 972-722-156-4 (capítulos 5 e 9)

·        Kernighan, Brian W. "The C Programming Language", Prentice-Hall International, 1988 (capitulo 4)

·        Sampaio, Isabel; Sampaio, Alberto “Fundamental da Programação em C”, Editora FCA, ISBN 972-722-130-0 (capitulo 4)

 

7.      Tipos Estruturados

7.1  Noção de tipos estruturados

7.2  Registos definidos pelo utilizador

                                      7.2.1      Noção de registo

                                      7.2.2      Operações com registos

Objectivos:

Introduzir a noção de variáveis estruturadas e estudar as operações sobre elas.

Bibliografia Principal:

·        Damas, Luis “Linguagem C”, Editora FCA, ISBN 972-722-156-4 (capitulo 11)

·        Kernighan, Brian W. "The C Programming Language", Prentice-Hall International, 1988 (capitulo 6)

·        Sampaio, Isabel; Sampaio, Alberto “Fundamental da Programação em C”, Editora FCA, ISBN 972-722-130-0 (capitulo 9)

 

8.      Ficheiros

8.1  Noção de ficheiro

8.2  Tipos de ficheiros

8.3  Utilização de um ficheiro

                                      8.3.1      Declaração de um ficheiro

                                      8.3.2      Associação com uma variável

                                      8.3.3      Abertura do ficheiro

                                      8.3.4      Operações comuns com ficheiros

                                      8.3.5      Fecho de um ficheiro

8.4  Utilização de ficheiros de texto

8.5  Utilização de ficheiros de acesso directo

Objectivos:

Introduzir a noção de ficheiro e respectivas operações.

Bibliografia Principal:

·        Damas, Luis “Linguagem C”, Editora FCA, ISBN 972-722-156-4 (capitulo 10)

·        Kernighan, Brian W. "The C Programming Language", Prentice-Hall International, 1988 (capitulo 7 e 8)

·        Sampaio, Isabel; Sampaio, Alberto “Fundamental da Programação em C”, Editora FCA, ISBN 972-722-130-0 (capitulo 10)

 

9.      Programação modular

9.1  Introdução à noção de módulo ou biblioteca

9.2  Utilização de Bibliotecas

                                      9.2.1      As Bibliotecas como forma de estruturação de programas

                                      9.2.2      Criação de Bibliotecas pelo Programador

                                      9.2.3      Reutilização de Módulos entre projectos

Objectivos:

Introduzir a noção de programação modular e reutilização de software.

Bibliografia Principal:

·        Damas, Luis “Linguagem C”, Editora FCA, ISBN 972-722-156-4 (capitulo 5)

·        Kernighan, Brian W. "The C Programming Language", Prentice-Hall International, 1988 (capitulo 4)

·        Sampaio, Isabel; Sampaio, Alberto “Fundamental da Programação em C”, Editora FCA, ISBN 972-722-130-0 (capitulo 1, 4 e 6)

 

Teaching Manual for Algorithms and Programming

Computer Science Engineering, 1st year

José Manuel Torres

 

 

Course duration: 60 hours

Week schedule: 4 hours

Hours per class: 2 classes of 2 h each

 

Syllabus:

1.                  Algorithms and Computation

1.1.            Algorithm definition

1.2.            Algorithm representation

1.2.1.      Pseudo-code language

1.2.2.      Flow-graph diagram

1.2.3.      Programming language

1.3.            Algorithm proof and testing

1.3.1.      Tracing algorithms

1.3.2.      Mathematical proof of algorithms

1.3.3.      Algorithm testing

1.4.            Top-down and bottom-up programming

1.5.            Problem solving

1.5.1.      Problem analysis

1.5.2.      Problem specification

1.5.3.      Problem coding

1.5.4.      Program Test and Refinement

1.5.5.      Documentation generation

1.5.6.      Program maintenance

Purpose:

Present the notion of algorithm and problem; introduce methodologies to represent algorithms; present the several stages in the development of an algorithm to solve problems.

Main Bibliography:

·        Damas, Luis “Linguagem C”, Editora FCA, ISBN 972-722-156-4 (chapter 1)

·        Kernighan, Brian W. "The C Programming Language", Prentice-Hall International, 1988 (chapter 1)

·        Sampaio, Isabel; Sampaio, Alberto “Fundamental da Programação em C”, Editora FCA, ISBN 972-722-130-0 (chapter 1)

 

2.                  Introduction to Programming

2.1.            Concept of program and software

2.2.            Software types

2.3.            Machine language, assembly and high level language

2.4.            Programming in high level languages

2.4.1.      Source program

2.4.2.      Compiler

2.4.3.      Interpreter

2.4.4.      Object Code

2.4.5.      Libraries

2.4.6.      Executable program

2.5.            Main high level programming languages and applications

Purpose:

Present the notion of programming, software and of programming languages; introduce the typical development cycle of a software program.

Main Bibliography:

·        Damas, Luis “Linguagem C”, Editora FCA, ISBN 972-722-156-4 (chapter 1)

·        Kernighan, Brian W. "The C Programming Language", Prentice-Hall International, 1988 (chapter 1)

·        Sampaio, Isabel; Sampaio, Alberto “Fundamental da Programação em C”, Editora FCA, ISBN 972-722-130-0 (chapter 1)

 

3.                  Control structures

3.1.            Simple and structured instructions

3.2.            Conditional instructions

3.2.1.      "if-then-else" instructions

3.2.2.      "case" selection instructions

3.3.            Repetitive instructions

3.3.1.      "while" instructions

3.3.2.      "for" instructions

3.4.            "goto" instruction and “labels”

Purpose:

Introduce the several control structures as basic tools to develop programs.

Main Bibliography:

·        Damas, Luis “Linguagem C”, Editora FCA, ISBN 972-722-156-4 (chapters 3 and 4)

·        Kernighan, Brian W. "The C Programming Language", Prentice-Hall International, 1988 (chapter 3)

·        Sampaio, Isabel; Sampaio, Alberto “Fundamental da Programação em C”, Editora FCA, ISBN 972-722-130-0 (chapter 3)

 

4.                  Data types, expressions and declarations

4.1.            Data types

4.1.1.      Ordinal types

4.1.2.      Real types

4.1.3.      String types

4.1.4.      Type definition and type conversion

4.2.            Constant declaration

4.3.            Operators and expressions

4.3.1.      Definition of operand, operator and expression

4.3.2.      Arithmetic operators

4.3.3.      Logic operators

4.3.4.      Boolean operators

4.3.5.      Relational operators

4.3.6.      Precedence rules in expression evaluation

4.4.            Intrinsic functions

Purpose:

Introduce the notion of data types, variables, constants, operators and expressions

Main Bibliography:

·        Damas, Luis “Linguagem C”, Editora FCA, ISBN 972-722-156-4 (chapter 2)

·        Kernighan, Brian W. "The C Programming Language", Prentice-Hall International, 1988 (chapter 2)

·        Sampaio, Isabel; Sampaio, Alberto “Fundamental da Programação em C”, Editora FCA, ISBN 972-722-130-0 (chapter 2)

 

5.                  Arrays and Strings

5.1.            Introduction to indexing

5.2.            Vector and matrix definition

5.3.            Use of vectors

5.3.1.      Search in vectors: linear search and binary search

5.3.2.      Vector sorting: Selection sorting, Fusion sorting, Bubble sorting, Quick sorting

5.4.            Matrix use

5.5.            Strings

5.5.1.      Concept of string

5.5.2.      Operations with strings

Purpose:

Introduce the use of indexed data types in programs and of searching and sorting algorithms.

Main Bibliography:

·        Damas, Luis “Linguagem C”, Editora FCA, ISBN 972-722-156-4 (chapter 6 and 7)

·        Kernighan, Brian W. "The C Programming Language", Prentice-Hall International, 1988 (chapter 5)

·        Sampaio, Isabel; Sampaio, Alberto “Fundamental da Programação em C”, Editora FCA, ISBN 972-722-130-0 (chapter 7)

 

6.                  Procedures and functions

6.1.            Notion of procedure and function

6.2.            Local vs global variable

6.3.            Procedures

6.3.1.      Introduction to Procedures

6.3.2.      Parameters type

6.3.3.      Passing parameters by value

6.3.4.      Passing parameters by reference

6.4.            Functions

6.4.1.      Introduction to functions

6.4.2.      Differences between functions and procedures

6.4.3.      In parameters

6.4.4.      Out parameters

6.5.            Introduction to recursion

Purpose:

Introduce the notion of structured programming; present the concept of function and procedure. Define the concept of recursion.

Main Bibliography:

·        Damas, Luis “Linguagem C”, Editora FCA, ISBN 972-722-156-4 (chapters 5 and 9)

·        Kernighan, Brian W. "The C Programming Language", Prentice-Hall International, 1988 (chapter 4)

·        Sampaio, Isabel; Sampaio, Alberto “Fundamental da Programação em C”, Editora FCA, ISBN 972-722-130-0 (chapter 4)

 

7.                  Structured Types

7.1.            Notion of Structured Types

7.2.            User defined records

7.2.1.      Notion of Records

7.2.2.      Operations with records

Purpose:

Introduce the notion of structured types and variables and associated operations.

Main Bibliography:

·        Damas, Luis “Linguagem C”, Editora FCA, ISBN 972-722-156-4 (chapter 11)

·        Kernighan, Brian W. "The C Programming Language", Prentice-Hall International, 1988 (chapter 6)

·        Sampaio, Isabel; Sampaio, Alberto “Fundamental da Programação em C”, Editora FCA, ISBN 972-722-130-0 (chapter 9)

 

8.                  Files

8.1.            Notion of file

8.2.            File types

8.3.            File operations

8.3.1.      File declarations

8.3.2.      Association with a file variable

8.3.3.      File opening

8.3.4.      Typical operations with files

8.3.5.      File closing

8.4.            Operations with text files

8.5.            Operations with random-access files

Purpose:

Introduce the notion of file and associated operations.

Main Bibliography:

·        Damas, Luis “Linguagem C”, Editora FCA, ISBN 972-722-156-4 (chapter 10)

·        Kernighan, Brian W. "The C Programming Language", Prentice-Hall International, 1988 (chapter 7 and 8)

·        Sampaio, Isabel; Sampaio, Alberto “Fundamental da Programação em C”, Editora FCA, ISBN 972-722-130-0 (chapter 10)

 

9.                  Modular programming

9.1.            Introduction to the notion of module or library

9.2.            Software Libraries and modular programming

9.2.1.      Software libraries as a way of implementing structured programming

9.2.2.      User created Libraries

9.2.3.      Reuse of software libraries between projects

Purpose:

Introduce the notion of modular programming and software reusing.

Main Bibliography:

·        Damas, Luis “Linguagem C”, Editora FCA, ISBN 972-722-156-4 (chapter 5)

·        Kernighan, Brian W. "The C Programming Language", Prentice-Hall International, 1988 (chapter 4)

·        Sampaio, Isabel; Sampaio, Alberto “Fundamental da Programação em C”, Editora FCA, ISBN 972-722-130-0 (chapter 1, 4 and 6)