O presente curso é um segundo curso de programação para alunos que já aprenderam o “básicos” de programação – e já sabem entender e interpretar um algoritmo – mas precisam entender conceitos mais avançados de computação. O curso é baseado na linguagem C e os conceitos incluem os seguintes:
- Como funciona a recursividade e qual o poder dos paradigmas computacionais baseados em divisão-e-conquista
- Abstrações de dados e como os Tipos Abstratos de Dados ajudam a desenvolver aplicações voltadas para áreas específicas.
- Ponteiros e organização de memória: como funciona o computador e como a linguagem C ajuda a entender isso.
- Estruturas de dados e o impacto na eficiência computacional.
Nesta página, apresentamos um guia de estudos para alunos que desejem ter uma primeira formação em Programação de Computadores em Linguagem C. O guia também serve como material de estudo para alunos que estejam fazendo curso Programação II com o Prof. Raphael Machado.
O guia segue uma estrutura em cinco partes:
- Parte 1: Conceitos, Notação e Comandos da Linguagem C
- Parte 2: Recursão e Noções de Análise e Projeto de Algoritmos
- Parte 3: Tipo Abstrato de Dados
- Parte 4: Ponteiros e Organização de Memória
- Parte 5: Noções de Estrutura de Dados
Material de referência: slides do curso.
Material complementar de estudo.
- The C Programming Language (Second Edition) (K&R)
- Apostila do Prof. Silvio Pereira (Apostila)
- Livro Algoritmos e Lógica de Programação em C – Uma Abordagem Didática
- C How to Program 8/E.
- Canal “De aluno para aluno: Linguagem C”.
Desenvolvimento seguro em C:
- How to Write Secure Code in C
- Secure Development Setup in C
- CERT C Guidelines
- Tests with Googletest and Code coverage with Gcov
- Dynamic Analysis with Valgrind to detect Memory Errors
- Static Analysis with CppCheck to detect CERT C Guidelines
Parte 1: Conceitos, Notação e Comandos da Linguagem C
Módulo 1.1. Conceitos Básicos
- Conceitos
- Problema, Algoritmo, Programa
- Código Fonte, Compilador, Código de Máquina
- Variáveis
- Entrada e Saída de Dados
- Expressões
- Controle: Condicional, Repetição Condicional, Iteração (repetição com contador)
- Vetores
- A Linguagem C
- C vs vs Pascal vs Python
- Definição de Programa
- Comentários em C
- Includes e Bibliotecas
- argc e argv
- Delimitadores de Escopo (Chaves{})
- Entrada e saída: printf e scanf
- Tipos de variáveis /
- Exemplos de programas “simples”
Leitura recomendada: Capítulos 1, 2, 3 e 4 da Apostila.
Vídeos de auto-estudo: vídeos 2 a 9 do Canal “De aluno para aluno: Linguagem C”.
Leitura complementar: Capítulos 1, 2 e 3 do K&R, C and C++: spectacular examples of incompetence?
Módulo 1.2. Funções e Procedimentos
- Função vs Procedimento
- Argumentos e Retorno
- Passagem por Valor e por Referência
- Introdução aos Ponteiros
- Exemplos de programas
Leitura recomendada: Capítulo 7 da Apostila.
Leitura complementar: Capítulo 4 do K&R
Módulo 1.3. Escopo de Variáveis
- Conceito de Escopo
- Local de Declaração de Variáveis
- Tempo de Vida de uma Variável
- Variáveis Locais e Globais
Módulo 1.4. Strings
- Strings
Parte 2: Recursão e Noções de Análise e Projeto de Algoritmos
Módulo 2.1. Motivação: algoritmos de ordenação.
- Problema de ordenação
- SelectionSort
- InsertionSort
- BubbleSort
- Análise experimental dos tempos de execução
Slides da atividade de laboratório – Aula 2.1
Módulo 2.2. Divisão-e-conquista: uma estratégia para construir algoritmos rápidos de ordenação
- Análise “matemática” dos algoritmos da aula 2.1
- Limite inferior para o tempo de ordenação
- “Problema” dos algoritmos da aula 2.1 (altura e largura lineares) e estratégia para resolver (altura logarítmica)
- “Ideia” (descrição intuitiva) do MergeSort – motivação para a recursão
Não há slides para a aula 2.2.
Módulo 2.3. Recursão
- Grafo de chamadas de função
- Conceito de função recursiva
- Exemplos básicos: Somatório, Fatorial, Fibonacci
- Exemplo: Progressão Geométrica
- Exemplo: Torre de Hanoi
- Recursão vs Iteração
Módulo 2.4. Algoritmos MergeSort e QuickSort
- MergeSort
- Descrição do Algoritmo
- Análise de Complexidade
- Implementação do Programa
- QuickSort
- Descrição do Algoritmo
- Análise de Complexidade
- Implementação do Programa
Não há slides para a Aula 2.4.
Parte 3: Ponteiros e Organização de Memória
Módulo 3.1. Memória e Endereço
- Memória
- Endereços de Memória
- Hexadecimais
- Memória de um Programa
- Escopo de Variáveis e Memória
- Tipos de Variáveis
- Vetores
- O operador &
Módulo 3.2. Ponteiros
- O operador *
- NULL
- Biblioteca stdlib
- Ponteiros e Registros
- Segmentation Fault
- Ponteiros para Ponteiros
- Operações envolvendo ponteiros
Módulo 3.3. Alocação Dinâmica de Memória
- Exemplos de alocação estática: vetores e matrizes
- Alocação dinâmica com malloc
- Vetor e Matriz com malloc
- Comando free
- Comando calloc
- Comando realloc
- Comando memcpy
- Alocação dinâmica e funções
Parte 4: Tipo Abstrato de Dados
Módulo 4.1. Registros e Tipos
- Registros e o comando struct
- Registros e Funções
- Definição de tipos com o comando typedef
- Tamanho de tipos e o comando sizeof
- Definição de constantes
Módulo 4.2. Tipo Abstrato de Dados
- Conceito e “Paradigma” do TAD
- Tipos, Dados e Operações
- Software em Camadas
- Vantagens do TAD
- Exemplos: Desenho, Polinômio,…
Módulo 4.3. Modularização
- Revisão de “Software em Camadas”
- Arquivos .h e .c
- Compilando em Linha de Comando
- Makefile
- Bibliotecas
Parte 5: Estruturas de Dados
Módulo 5.1. Lista encadeada/ligada
- Conceito
- Lista vs Vetor
- Implementação
- Criação
- Percurso
- Busca
- Insersão
- Remoção
Módulo 5.2. Outras listas
- Lista circular
- Lista duplamente encadeada/ligada
- Lista circular duplamente encadeada/ligada
- Lista encadeada/ligada com cabeça
Módulo 5.3. Fila e Pilha
- Conceito de Fila e Pilha
- Implementação
Módulo 5.4. Arquivos
- Conceito
- Arquivo texto e arquivo binário
- Stream
- fopen e fclose
- printf e scanf
- getchar e putchar
- fgetc e fputc
- gets e puts
- fread e fwrite
- EOF
- fseek