Wprowadzenie do Algorytmów i Struktur Danych

Wprowadzenie do przedmiotu Algorytmy i struktury danych

• Przedmiot: Algorytmy i struktury danych
• Autor: Jan G. Bazan
• Witryna internetowa wykładu: http://fenix.univ.rzeszow.pl/bazan/archiwum/
• Dostęp wymaga autoryzacji:
  • Konto: asd
  • Hasło: algosys
• Witryna zawierać będzie prezentacje wykładowe, materiały pomocnicze do ćwiczeń, przykłady programów, pytania do egzaminu itp.

Literatura

• Elementy analizy algorytmów (1989), WNT, Banachowski, L., Kreczmar, A.
• Algorytmy i struktury danych - zadania (2006), PJWSTK, Dańko, A, Truong Lan Le, Mirkowska, G., Rembelski, P., Smyk, A., Sydow, M.
• Zbiór zadań z propedeutyki informatyki (1996), PWN, Cichy M., Nomańczuk J., Szpakowicz S.
• Algorytmy i struktury danych (2003), Helion, Aho, A., V., Hopcroft, J., E., Ullman, J., D.
• Algorytmy i struktury danych (1996), WNT, Banachowski, L., Diks, K., Rytter, W.
• Wprowadzenie do algorytmów (2012), WNT, Cormen, T., H., Leiserson, C. E, Rivest, R., L., Stein, C.

Algorytm i algorytmika

• Algorytm to opis metody rozwiązania problemu w skończonej liczbie kroków (operacje elementarne).
• Operacja elementarna to operacja, która z punktu widzenia użytkownika jest całością i realizowana w skończonym czasie.
• Przykłady operacji elementarnych: przypisanie wartości do zmiennej, porównanie dwóch wartości, wczytanie danych z wejścia, wypisanie danych na wyjściu.
• Algorytmika to dział informatyki zajmujący się własnościami algorytmów, ich projektowaniem i analizą.
• Określenie algorytm wywodzi się od nazwiska matematyka perskiego Muhammeda ibn Mūsā al-Chwarizmi (około 800 r. n.e.)

Przykład algorytmu

• Wypranie ubrań w pralce automatycznej:
  • Włączenie pralki, załadowanie ubrań, nasypanie proszku
  • Ustalenie odpowiedniego programu (w zależności od stopnia zabrudzenia)
  • Odkręcenie zaworu doprowadzającego wodę
  • Naciśnięcie przycisku START
  • Czekanie na sygnał zakończenia pracy (kontrolka KONIEC)
  • Zakręcenie zaworu doprowadzającego wodę
  • Wyjęcie ubrań, wyłączenie pralki

Patenty na algorytmy

• W niektórych krajach (np. USA) algorytmy mogą być opatentowane, jeśli są zaimplementowane w konkretnym, praktycznym celu.
• Prowadzi to do sporów prawnych pomiędzy koncernami komputerowymi.
• Argumentacja za patentowaniem algorytmów opiera się na prawie własności intelektualnej, traktując oprogramowanie jako wytwór intelektu i pracy jego twórców.

Oczekiwane cechy algorytmów

• Poprawność (algorytm daje dobre wyniki, odzwierciedlające rzeczywistość)
• Jednoznaczność (identyczne dane dają taki sam wynik)
• Skończoność (algorytm kończy się po skończonej ilości kroków)
• Sprawność (czasowa - szybkość wykonania, pamięciowa - zużycie zasobów)
• Prostota (operacje powinny być jak najprostsze)

Cel przedmiotu w pierwszym semestrze

• Nauka projektowania prostych algorytmów
• Nauka analizy algorytmów pod kątem złożoności (efektywności) i poprawności
• Analiza algorytmów bez rekurencji i rekurencyjnych

Algorytm i zagadnienia towarzyszące

• Znajomość problemu
• Podejście do definicji algorytmu
• Rozwijanie algorytmów
• Poprawność
• Złożoność
• Optymalność

Problemy nierozstrzygalne

• Problem decyzyjny jest rozstrzygalny, jeśli istnieje algorytm, który dla dowolnych danych po skończonej liczbie kroków daje rozwiązanie problemu.
• W przeciwnym razie problem jest nierozstrzygalny.
• Przykładem problemu nierozstrzygalnego jest problem domina.

Sposoby zapisu algorytmów

• Opis słowny (opis kolejnych czynności)
• Schemat blokowy (symbole graficzne)
• Pseudokod (umowny język programowania)
• Język programowania (języki programowania)

Aspekty różnych metodologii tworzenia algorytmów

• Proceduralność (podzielenie na procedury)
• Praca sekwencyjna (kolejne wykonywanie czynności)
• Praca wielowątkowa (konkurencyjne wykonywanie czynności)
• Praca równoległa i współbieżna (współpraca procesów)
• Rekurencja (procedura wywołująca sama siebie)
• Obiektowość (połączenie danych i czynności w obiekty)
• Algorytm probabilistyczny (algorytm z wysokim prawdopodobieństwem daje poprawny wynik)

Podstawy pseudokodu

• Książka Algorytmy i struktury danych – zadania, Dańko, A, Truong Lan Le, Mirkowska, G., Rembelski, P., Smyk, A., Sydow, M. (2006), PJWSTK

Elementy składni pseudokodu

• Omówienie składni pseudokodu (elementy instrukcji).

Operatory i relacje

• Operatory arytmetyczne (+, -, *, / ,div, mod)
• Operatory logiczne (NOT, AND, OR, XOR, ⇒, ⇔)
• Relacje (=, <, >, <=, >=)

Typy podstawowe

• int (liczby całkowite)
• real (liczby rzeczywiste)
• char (znaki)
• bool (wartości logiczne)
• string (łańcuchy znaków)

Deklaracja zmiennych

• Deklarowanie zmiennych (z typami)
• Przykłady
• Dostęp do elementów tablicy

Deklaracja zmiennych tablicowych

• Deklaracja zmiennych tablicowych dla różnego typu danych
• Dostęp za pomocą operatorów tablicowych [] dla elementów tablicy.
• Wartość tablic przy inicjalizacji.

Blok instrukcji

• Bloki instrukcji – pogrupowane grupy instrukcji.
• Separacja instrukcji w blokach instrukcji.
• Wprowadzenie przykładów bloków instrukcji.

Instrukcja przypisania

• Instrukcja przypisania – przypisanie wartości wyrażenia do zmiennej.
• Przykłady instrukcji przypisania

Instrukcja warunkowa

• Instrukcja if-then-else – rozgałęzienie algorytmu w zależności od warunku.
• Zasady tworzenia i stosowania instrukcji warunkowych.
• Własne przykłady instrukcji warunkowych

Przykłady instrukcji warunkowych

• Rozmiarowy przykład if-then-else z różnymi warunkami.
• Przykład w programowaniu

Instrukcja pętli while

• Instrukcja pętli while – iterowanie przez blok instrukcji tak długo, jak warunek jest spełniony.
• Wprowadzenie przykładów

Instrukcja pętli for

• Instrukcja pętli for – iterowanie przez blok instrukcji określony zakres iteracji.
• Formy pętli for – do, downto.
• Przykłady instrukcji pętli for

Definicja funkcji

• Definiowanie funkcji, procedur w pseudokodzie.
• Parametry formalne i aktualne w funkcjach.
• Deklaracja zmiennych.

Przykład funkcji

• Definicja funkcji obliczającej silnię.
• Wywołanie funkcji

Definicja procedury

• Definicja procedury.
• Parametry procedury.
• Deklaracja zmiennych proceduralnych

Przykład procedury

• Definicja procedury obliczającej sumę elementów tablicy.
• Wywołanie procedury.

Trzy predefiniowane funkcje i procedury

• Funkcja i procedura Print (wypisuje dane)
• Funkcja Read (Odczytuje dane)
• Funkcja Length (zwraca długość stringa lub tablicy)

Podstawowe funkcje matematyczne

• Funkcje matematyczne (sqr, sqrt, pow, log, abs, min, max, floor, ceil)

Ręczne śledzenie działania programu metoda tabelkowa

• Jak śledzić ręcznie wartości zmiennych podczas działania programu.
• Tabela do śledzenia wykonania programu.
• Celem śledzenia jest odnalezienie potencjalnych błędów w programie.
• Przykład algorytmu i jego śledzenia.

Notacje asymptotyczne

• Wprowadzenie i definicje notacji asymptotycznych.

Mniejszy, równy i większy rząd funkcji

• porównanie funkcji z punktu widzenia asymptotycznego
• notacje f = Ω(g), f = 0(g), f = Ɵ(g).

Wniosek o rzędach funkcji

• Wnioski na temat rzędów funkcji w oparciu o ich definicje.

Porównanie różnych funkcji z punktu widzenia ich rzędów

• Porównanie funkcji i ich rzędów.
• Poszczególne funkcje jako przykłady.

Ograniczenie funkcji z dołu

• Określenie i uzasadnienie warunków ograniczenia funkcji z dołu.
• Definicje oraz przykłady.

Ograniczenie funkcji z góry

• Określenie i uzasadnienie warunków ograniczenia funkcji z góry.

Ograniczenie funkcji z dołu i z góry

• Zestawienie zasad ograniczeń z dołu i z góry dla funkcji.
• Przykładowa tabelka porównawcza.