Podręcznik

1. Wprowadzenie do programowania

Można przyjąć, że programowanie sprowadza się do takiego wydawania poleceń komputerowi, aby:

• były poprzez niego zrozumiałe
• doprowadziły do uzyskania przez nas zamierzonego celu.

Ten kurs ma na celu nauczyć Was przede wszystkim formułowania rozwiązań danego zadania w sposób umożliwiający ich rozwiązanie na komputerze, a więc skupimy się na punkcie drugim (fachowo nazywa się to specyfikacją problemu i budową algorytmu). Oczywiście wiedza ta byłaby zupełnie nieprzydatna, jeśli nie poznalibyście choćby podstaw zapisania otrzymanego wyniku w postaci zrozumiałej dla komputera - co z tego, że ja wiem, co powinien zrobić mój pracownik, skoro nie umiem mu tego powiedzieć? Poznacie więc też, niejako przy okazji, sposób zapisu rozwiązań w postaci zrozumiałej dla komputera; proces taki nazywamy często kodowaniem algorytmu.

W podręczniku przedstawimy Wam  podstawy kodowania strukturalnego w języku C++.  Nie został on  opracowany jako język dla początkujących, wręcz przeciwnie - stanowi jeden z najbardziej skomplikowanych i trudnych języków programowania wysokiego poziomu. Lecz nie bójcie się tego - w trakcie kursu nie będziemy wykorzystywali żadnych zaawansowanych struktur i konstrukcji specyficznych dla  C++. Przedstawimy Wam wyłącznie techniki wspólne dla wszystkich strukturalnych języków programowania, które będziemy oznaczać jako C/C++. Ci z Was, którzy będą chcieli kontynuować swoją przygodę z programowaniem, otrzymają tu solidne podstawy jednego z najpopularniejszych  na świecie języków programowania.

Podczas prawie całego kursu będziemy tworzyli programy dla konsoli, działające w trybie tekstowym, swoim wyglądem znacznie odbiegające od aktualnie obowiązujących standardów. Takie podejście pozwoli Wam skupić się na rozwiązywaniu problemów i nauczy Was (przynajmniej mamy taką nadzieję) budowania algorytmów w celu późniejszej implementacji ich na komputerze.

Wasze programy będziecie uruchamiać jako aplikacje konsolowe. Do ich uruchamiania możecie wykorzystywać różne narzędzia (środowiska programistyczne) - my polecamy z darmowych VS Code firmy Microsoft, lub Qt Creator, z płatnych - CLion firmy JetBrains (możecie mieć darmową licencję dla studentów, wystarczy że zarejestrujecie się korzystając z uczelnianego adresu). W podręczniku, ze względów historycznych, powołujemy się czasami na bezpłatne środowisko Code::Blocks - na dzień dzisiejszy jednak tracące popularność. Które ze środowisk będziecie wykorzystywać - Wasza wola, my nie wymagamy jakiegoś konkretnego wyboru. 

2. Algorytmy, programy i dane

Na początku wprowadzimy kilka pojęć. Większość z nich jest już prawdopodobnie Wam znana.

Algorytmem nazywamy metodę rozwiązania danego problemu.

Aby rozwiązać jakiś problem, wykonujemy kolejno pewne czynności, które nazywać będziemy krokami. Krokiem może być zarówno bardzo prosta czynność, nazywana w programowaniu operacją elementarną, jak i całkiem złożona sekwencja prostych czynności, którą będziemy nazywali podprogramem. 

W celu rozwiązania problemu należy wykonać pewne czynności w określonej kolejności. Czynności te nazywamy kolejnymi krokami algorytmu. Krokiem może być prosta operacja, którą w programowaniu nazywamy operacją elementarną lub bardziej złożone operacje, które będziemy nazywali podprogramem.

Istotną cechą algorytmu jest jego ogólność, co oznacza, że nie podaje on metody rozwiązania pojedynczego problemu, lecz całej grupy problemów podobnych.

Każdy sposób rozwiązania problemu można przedstawić na różne sposoby, ale dla komputerów istnieje potrzeba jasnego, formalnego opisu, który uwzględnia nawet najmniejsze szczegóły. W związku z tym stosuje się języki programowania, które zostały stworzone z myślą o precyzji i jednoznaczności. Te języki posiadają specjalną składnię i słownictwo, które umożliwiają komputerom zrozumienie i wykonywanie określonych zadań zgodnie z intencją programisty. Bez tego formalnego opisu, komputer nie byłby w stanie efektywnie przetwarzać informacji ani wykonywać określonych instrukcji.

Programem nazywamy zapis algorytmu w danym języku programowania.

Programowanie to proces tworzenia zestawu instrukcji, które komputer może wykonywać w celu rozwiązania konkretnego problemu lub wykonania określonego zadania. W praktyce, programowanie polega na pisaniu kodu źródłowego przy użyciu specjalnych języków programowania, które komputer może zrozumieć i wykonać. Programowanie wymaga logicznego myślenia, rozwiązywania problemów oraz zrozumienia potrzeb użytkownika lub sytuacji, które mają być obsłużone przez stworzony program. Oprócz samego pisania kodu, programowanie obejmuje również testowanie, debugowanie oraz optymalizację programów w celu zapewnienia ich poprawnego działania i efektywności. Programowanie jest kluczowym elementem w tworzeniu oprogramowania oraz rozwoju technologii informatycznych.

Istotną częścią działania algorytmu jest operowanie na danych. Oznacza to, że algorytm pobiera dane wejściowe, przetwarza je zgodnie z określonymi krokami i generuje wynik lub wyjście. Na początku algorytm otrzymuje dane wejściowe, które mogą być w różnych formach, takich jak liczby, tekst, obrazy, czy inne struktury danych. Następnie, algorytm wykonuje określone operacje na tych danych, przestrzegając określonych reguł i warunków logicznych, aby osiągnąć zamierzony rezultat. Operowanie na danych może obejmować różne czynności, takie jak manipulacja liczbami, porównywanie wartości, sortowanie danych, czy też przeszukiwanie kolekcji danych w celu znalezienia określonych informacji. Wynik działania algorytmu może być przekazywany jako wyjście, które może być dalej wykorzystane lub wyświetlone użytkownikowi.

Komputer wykonuje program składający się z ciągu instrukcji, które dotyczą danych o różnych nazwach.

Podkreślmy to wyraźnie: wszystkie dane są w pełni niezależne od programu.

Rozważmy teraz prosty przykład obliczeniowy.

Problem 1:
Dla danych wartości x, y, z obliczyć i napisać wartość następującego wyrażenia:

$w=\left( x+y \right) \cdot \left( x-z \right)$

Problem ten może być przeznaczony do rozwiązania zarówno przez człowieka, który ma wykonać obliczenie i pokazać (napisać na kartce) jego wynik, jak i przez komputer, który ma ten wynik wyświetlić (wypisać) na ekranie. Trzeba tu przy tym wyraźnie podkreślić, że sformułowanie "dla danych ... " oznacza konieczność pobrania wartości tych danych:

• człowiek może je pobrać z zewnątrz (przeczytać z kartki itp.) lub po prostu ustalić - "pobrać " z własnej głowy,
• komputer (a ściślej jego procesor, czyli jednostka wykonująca obliczenia) też może te dane pobrać z zewnątrz (wczytać z klawiatury, na której napisze je użytkownik lub wczytać z dowolnego pliku) albo też po prostu może je ustalić - wylosować.

A więc bardziej precyzyjne sformułowanie Problemu 1 może mieć postać:

Problem 1 - uściślony:
Wczytać wartości danych x, y, z, po czym obliczyć i napisać wartość następującego wyrażenia:

$w=\left( x+y \right) \cdot \left( x-z \right)$

W języku naturalnym algorytm rozwiązania tego problemu, niezależnie od tego, dla kogo jest on przeznaczony, możemy zapisać następująco:

Algorytm 1:

• wczytaj wartości danych wejściowych x, y, z
• oblicz wartość danej wyjściowej\ ( w=\left( x+y \right) \cdot \left( x-z \right) \)
• napisz wartość danej wyjściowej w

Tu niezwykle istotna uwaga: należy odróżniać od siebie dwa podmioty związane z algorytmem:

1. wykonawca algorytmu (człowiek lub komputer) wykonuje po kolei wszystkie polecenia algorytmu, zaczynając od pobrania danych.
2. użytkownik algorytmu (inny człowiek, użytkownik komputera) podaje dane niezbędne do wykonania algorytmu.

To ważne: podawanie danych nie należy do algorytmu - bo to robi kto inny. Zadaniem algorytmu jest wczytywanie danych, które ten ktoś podał.

3. Kod źródłowy, maszynowy i kompilator

Po napisaniu aplikacji, która rozwiązuje określony problem, wykonywane są czynności polegające na przekształceniu kodu aplikacji na kod zrozumiały dla komputera. Kompilacja aplikacji to proces przekształcenia kodu źródłowego aplikacji na język programowania, na kod wykonywalny, który może być uruchomiony na konkretnym systemie komputerowym. Podczas kompilacji, kompilator (narzędzie programistyczne) analizuje kod źródłowy aplikacji i tłumaczy go na kod maszynowy, który jest zrozumiały dla komputera. Ten proces obejmuje kilka etapów, takich jak preprocesowanie, kompilację właściwą i linkowanie. W wyniku kompilacji uzyskuje się plik wykonywalny, który zawiera instrukcje, jakie należy wykonać, aby program działał zgodnie z oczekiwaniami. Kompilacja jest kluczowym krokiem w procesie tworzenia oprogramowania, ponieważ przekształca abstrakcyjny kod źródłowy napisany przez programistę na coś, co komputer jest w stanie zrozumieć i wykonać.

Kompilacja aplikacji w języku C++ składa się z kilku etapów, które prowadzą od kodu źródłowego do gotowego programu. Oto omówienie poszczególnych etapów kompilacji w języku C++:

1. Preprocesor: Pierwszym etapem kompilacji jest preprocesor. Preprocesor wykonuje różne manipulacje na kodzie źródłowym przed właściwą kompilacją. Na przykład, w tym etapie są wykonywane operacje takie jak włączanie plików nagłówkowych (directive #include), zastępowanie makr preprocesora (directive #define), czy usuwanie komentarzy. Wynikiem tego etapu jest kod źródłowy po przetworzeniu przez preprocesor.

2. Kompilacja: W tym etapie kod źródłowy jest przekształcany na kod maszynowy dla konkretnej platformy sprzętowej. Kompilator C++ tłumaczy kod źródłowy na język asemblera, który jest już bardziej zrozumiały dla komputera. Kompilator również sprawdza poprawność składniową i semantyczną kodu, zgłaszając błędy, jeśli są jakieś problemy.

3. Linkowanie: Po kompilacji kodu źródłowego każdy plik źródłowy może mieć swoje funkcje i zmienne. Linkowanie polega na połączeniu tych funkcji i zmiennych w jedną spójną aplikację lub bibliotekę. W tym etapie linkera są również rozwiązane wszystkie odwołania do funkcji i zmiennych zdefiniowanych w innych plikach lub bibliotekach.

4. Optymalizacja: Niektóre kompilatory wykonują również etap optymalizacji, w którym kod maszynowy jest analizowany i przekształcany w bardziej wydajną formę. Optymalizacje mogą obejmować m.in. eliminację zbędnych instrukcji, minimalizację zużycia pamięci, czy też przyspieszenie działania kodu poprzez zmniejszenie liczby operacji.

Po przejściu przez te etapy, gotowy program jest gotowy do uruchomienia na określonej platformie sprzętowej. Proces kompilacji w języku C++ jest złożony, ale dzięki temu możliwe jest tworzenie wydajnych i stabilnych aplikacji komputerowych.

Często mówiąc o wykonaniu programu źródłowego mamy na myśli oba te procesy kolejno: kompilację, a potem wykonanie.

Każdy z tych procesów może prowadzić do błędów. Możemy więc mówić o dwu rodzajach błędów, które mogą się nam przytrafić, a ściślej komputerowi, który próbuje sobie poradzić z naszym programem:

• błędy kompilacji wynikają z tego, że kompilator (nasz program tłumaczący) nie rozumie programu źródłowego, bo są w nim błędy składniowe lub ortograficzne, na przykład brakuje nawiasu zamykającego albo napisaliśmy "flat" zamiast "float".
• błędy wykonania wynikają stąd, że program źródłowy nie daje się wykonać (mimo że jest poprawny pod względem formalnym) - na przykład nie może podzielić przez daną, która jest zerem, albo wyznaczyć pierwiastka kwadratowego z danej ujemnej.

Błędy wykonania są znacznie trudniejsze do wykrycia, niż błędy kompilacji. Najtrudniejsze zaś do wykrycia są błędy, które w ogóle nie są sygnalizowane przez kompilator, czyli:

• błędy logiczne algorytmu, które powstają w procesie tworzenia algorytmu - wówczas program daje się wykonać, ale wyniki jego pracy są nieprawidłowe.

Kod maszynowy jest najniższym poziomem abstrakcji w programowaniu komputerów i jest bezpośrednio wykonywany przez procesor. W odróżnieniu od kodu źródłowego, który jest czytelny dla człowieka, kod maszynowy jest trudny do zrozumienia i pisania bezpośrednio przez programistę.

Kod maszynowy jest wykonywany na procesorze poprzez serię kroków, które obejmują pobieranie, dekodowanie i wykonanie instrukcji.

1. Pobieranie instrukcji: Procesor pobiera kolejne instrukcje z pamięci, zazwyczaj zlokalizowanej w pamięci RAM lub w pamięci podręcznej procesora (ang. cache). Adres kolejnej instrukcji jest przechowywany w specjalnym rejestrze zw. wskaźnikiem instrukcji (ang. Instruction Pointer).

2. Dekodowanie instrukcji: Następnie procesor dekoduje pobraną instrukcję. Oznacza to rozpoznanie, jaką operację należy wykonać (np. dodawanie dwóch liczb, przeniesienie danych z jednego miejsca do drugiego) oraz jakie dane są potrzebne do wykonania tej operacji.

3. Wykonanie instrukcji: Po dekodowaniu instrukcji, procesor wykonuje odpowiednią operację na danych, zgodnie z zrozumieniem instrukcji. Operacje te obejmują m.in. manipulację danymi w rejestrach procesora, dostęp do pamięci, wykonanie obliczeń matematycznych itp.

4. Aktualizacja stanu procesora: Po wykonaniu instrukcji, procesor może zaktualizować swój stan w zależności od efektów tej operacji. Na przykład, jeśli wykonano operację arytmetyczną, to wynik może być zapisany w określonym rejestrze. Jeśli operacja spowodowała zmianę warunków, np. ustawienie flagi wynikowej, procesor może odpowiednio zmodyfikować swoje flagi stanu.

5. Przejście do kolejnej instrukcji: Procesor przechodzi do kolejnej instrukcji, kontynuując wykonywanie programu, aż do osiągnięcia punktu zatrzymania, błędu, lub zakończenia programu.

Ten cykl pobierania, dekodowania i wykonania instrukcji jest kontynuowany, aż do zakończenia działania programu. Procesor wykonuje te kroki bardzo szybko, co umożliwia płynne działanie programów komputerowych.

4. Schemat programu w języku C++

W ramach zajęć z Programowania będziemy na początku pisali aplikacje konsolowe.

Aplikacja konsolowa w języku C++ to program komputerowy, który działa w trybie tekstowym, interakcja z użytkownikiem odbywa się za pomocą wiersza poleceń (konsoli). Tego rodzaju aplikacje nie posiadają interfejsu graficznego użytkownika (GUI), a komunikacja z użytkownikiem odbywa się poprzez wprowadzanie i wyświetlanie tekstu w konsoli. Aplikacje konsolowe uruchamiane są w oknie konsoli lub wiersza polecenia.

Typowe cechy aplikacji konsolowych w C++ to:

1. Proste wejście/wyjście: Dane wejściowe są wprowadzane przez użytkownika za pomocą klawiatury, a wyniki są wyświetlane w konsoli tekstowej.

2. Wykorzystanie strumieni wejścia/wyjścia: Aplikacje konsolowe często korzystają ze strumieni wejścia (cin) i wyjścia (cout) dostępnych w bibliotece standardowej C++, aby odczytywać dane od użytkownika i wyświetlać wyniki.

3. Brak interfejsu graficznego: W przeciwieństwie do aplikacji z interfejsem graficznym użytkownika (GUI), aplikacje konsolowe nie posiadają graficznych elementów takich jak przyciski, okna czy pola tekstowe.

4. Wygodne do zadań związanych z przetwarzaniem tekstu lub działaniami w tle: Aplikacje konsolowe są często wykorzystywane do zadań, które nie wymagają interaktywnego interfejsu użytkownika, takich jak przetwarzanie plików, analiza danych, automatyzacja zadań systemowych itp.