Algorytmy i podstawy programowania w języku C++

Skrypt

Wstęp

Poniżej udostępniam skrypt do wykładu (wraz z przykładowymi zadaniami na ćwiczenia) z Algorytmów i Podstaw Programowania w języku C++, który prowadziłem w latach 2010-2016 na Wydziale Matematyki i Nauk Informacyjnych Politechniki Warszawskiej. Słuchaczami byli studenci I roku kierunku Matematyka.

Na laboratoriach, podczas których rozwiązywaliśmy zadania praktyczne, większość studentów korzystała z Visual C++. Zainteresowanych pracą w tym środowisku zachęcam również do zajrzenia do naszych samouczków. W przeciwnym przypadku polecam pracę z kompilatorami typu g++ (GNU Compiler Collection) lub clang++.

CC By 3.0
Niniejsze materiały zostały udostępnione na licencji Creative Commons Attribution 3.0 Unported License.

1. Etapy tworzenia oprogramowania. Algorytm

Pobierz

Spis treści:

  1. Wprowadzenie
  2. Etapy tworzenia oprogramowania
    1. Sformułowanie i analiza problemu
    2. Projektowanie
    3. Implementacja
    4. Testowanie
    5. Eksploatacja
    6. Podsumowanie
  3. Ćwiczenia
  4. Wskazówki i odpowiedzi do ćwiczeń

2. Podstawy organizacji i działania komputerów. Zmienne w języku C++ i ich typy. Operatory

Pobierz

Spis treści:

  1. Zarys historii informatyki
    1. Główne kierunki badań w informatyce współczesnej
  2. Organizacja współczesnych komputerów
  3. Zmienne w języku C++ i ich typy
    1. Pojęcie zmiennej
    2. Typy liczbowe
    3. Identyfikatory
    4. Deklaracja zmiennych
    5. Operator przypisania
    6. Rzutowanie (konwersja) typów. Hierarchia typów
  4. Operatory
    1. Operatory arytmetyczne
    2. Operatory relacyjne
    3. Operatory logiczne
    4. Operatory bitowe (*)
    5. Operatory łączone
    6. Priorytety operatorów
  5. Reprezentacja liczb całkowitych (*)
    1. System dziesiętny (*)
    2. System dwójkowy (*)
    3. System szesnastkowy (*)
    4. System U2 reprezentacji liczb ze znakiem (*)
  6. Ćwiczenia
  7. Wskazówki i odpowiedzi do ćwiczeń

3. Instrukcja warunkowa i pętle. Struktury. Funkcje – podstawy

Pobierz

Spis treści:

  1. Instrukcje sterujące
    1. Bezpośrednie następstwo instrukcji
    2. Instrukcja warunkowa if
    3. Pętle
  2. Struktury, czyli typy złożone
  3. Funkcje – informacje podstawowe
    1. Funkcje w matematyce
    2. Definiowanie funkcji w języku C++
    3. Wywołanie funkcji
    4. Zasięg zmiennych
    5. Przekazywanie parametrów przez referencję
    6. Argumenty domyślne
    7. Przeciążanie funkcji
  4. Przegląd funkcji z biblioteki języka C
    1. Funkcje matematyczne
    2. Liczby pseudolosowe
    3. Asercje
  5. Ćwiczenia
  6. Wskazówki i odpowiedzi do ćwiczeń

4. Wskaźniki i dynamiczna alokacja pamięci. Tablice jednowymiarowe. Proste algorytmy sortowania

Pobierz

Spis treści:

  1. Dynamiczna alokacja pamięci
    1. Organizacja pamięci komputera
    2. Wskaźniki
    3. Przydział i zwalnianie pamięci ze sterty
    4. Tablice
    5. Przekazywanie tablic funkcjom
  2. Proste algorytmy sortowania tablic
    1. Sortowanie przez wybór
    2. Sortowanie przez wstawianie
    3. Sortowanie bąbelkowe
    4. Efektywność obliczeniowa
  3. Ćwiczenia
  4. Wskazówki i odpowiedzi do ćwiczeń

5. Rekurencja. Abstrakcyjne typy danych

Pobierz

Spis treści:

  1. Rekurencja
    1. Przykład: silnia
    2. Przykład: NWD
    3. Przykład: wieże z Hanoi
    4. Przykład (niemądry): liczby Fibonacciego
  2. Podstawowe abstrakcyjne typy danych
    1. Stos
    2. Kolejka
    3. Kolejka priorytetowa
    4. Słownik
  3. Ćwiczenia

6. Napisy i macierze

Pobierz

Spis treści:

  1. Własne biblioteki funkcji
  2. Napisy (ciągi znaków)
    1. Kod ASCII
    2. Reprezentacja napisów (ciągów znaków)
    3. Operacje na napisach
    4. Biblioteka cstring
  3. Reprezentacja macierzy
  4. Przykładowe algorytmy z wykorzystaniem macierzy
    1. Mnożenie wiersza macierzy przez stałą
    2. Odejmowanie wiersza macierzy od innego pomnożonego przez stałą
    3. Zamiana dwóch kolumn
    4. Wiersz z największym co do modułu elementem w kolumnie
    5. Dodawanie macierzy
    6. Mnożenie macierzy
    7. Rozwiązywanie układów równań liniowych
  5. Ćwiczenia
  6. Wskazówki i odpowiedzi do ćwiczeń

7. Dynamiczne struktury danych

Pobierz

Spis treści:

  1. Wprowadzenie
  2. Stos
  3. Kolejka
  4. Kolejka priorytetowa
  5. Słownik
  6. Podsumowanie
  7. Ćwiczenia