Celem przedmiotu jest przedstawienie struktury logicznej i zasad działania komputera, cyfrowej reprezentacji informacji oraz sposobu wykonywania programów przez komputer. Istotnym celem jest też umożliwienie studentom nabycia podstawowych umiejętności z zakresu konstruowania i analizy algorytmów, w tym weryfikacji poprawności i szacowania złożoności obliczeniowej. W ramach przedmiotu umożliwia się poznanie podstawowych struktur danych i ich implementacji, a także nabycie umiejętności stosowania takich struktur danych do rozwiązywanych problemów.
##### Program:
* Pojęcia: problem, specyfikacja, algorytm, program komputerowy. Budowa komputera – schemat logiczny.
* Elementy programowania w języku niskopoziomowym na przykładzie maszyny RAM
* Reprezentacja danych w pamięci komputera: binarna stałopozycyjna i zmiennopozycyjna reprezentacja liczb, arytmetyka binarna; reprezentacja tekstu, obrazu, dźwięku.
* Programowanie w wysokopoziomowym języku strukturalnym, zstępująca metoda programowania.
* Kompilacja, translacja, interpretacja programów. Zarządzanie pamięcią podczas uruchamiania programu.
* Podstawowe konstrukcje programistyczne: iteracja, zagnieżdżanie, licznik, sumator, rekurencja.
* Elementy analizy algorytmów: poprawność, własność stopu, złożoność czasowa i pamięciowa, miary złożoności; notacja asymptotyczna.
* Podstawowe struktury danych i ich zastosowania: tablica, lista wiązana, stos, kolejka; drzewo przeszukiwań binarnych. Abstrakcyjne typy danych.
* Sortowanie przy pomocy porównań.
* Podstawowe techniki algorytmiczne: metoda nawrotów, metoda dziel i zwyciężaj, programowanie dynamiczne, algorytmy zachłanne.
* Komputerowa reprezentacja grafów.
* Algorytmy grafowe: przeszukiwanie w głąb, wszerz; składowe spójności.
* Gramatyki bezkontekstowe jako narzędzie do opisu składni języków programowania. Notacja BNF i EBNF.
* Pojęcie rozstrzygalności problemów, przykłady problemów nierozstrzygalnych.
###### Wymagania wstępne:
elementarna znajomość języka C lub Python (począwszy od wykładu 5)
###### Przewidywana formie zajęć w przypadku konieczności prowadzenia zajęć zdalnie:
Wykłady będą prowadzone w formie wideokonferencji
Ćwiczenia:
- zajęcia w formie wideokonferencji,
- utrzymany zostanie system deklaracji zadań,
- wskazane jest rekomendowanie studentom zakupu prostych tabletów graficznych w celu wygodnego dostępu do wirtualnej tablicy (np. MS Whiteboard) w trakcie cwiczen,
- wskazane jest przydzielenie nauczycielom prowadzącym ćwiczenia 3h zajęć: 2h na standardowe ćwiczenia, 1h na dedykowane konsultacje, w trakcie których prowadzący sprawdzają i omawiają indywidualnie ze studentami ich rozwiązania wybranych zadań.
