Wstęp do programowania (podejście imperatywne)
Informacje ogólne
| Kod przedmiotu: | 1000-211bWPI | Kod Erasmus / ISCED: |
11.301
 /
(0612) Database and network design and administration
|
| Nazwa przedmiotu: | Wstęp do programowania (podejście imperatywne) | ||
| Jednostka: | Wydział Matematyki, Informatyki i Mechaniki | ||
| Grupy: |
Przedmioty obowiązkowe dla I roku informatyki Przedmioty obowiązkowe dla I roku JSIM |
||
| Punkty ECTS i inne: |
13.00  zobacz reguły punktacji |
||
| Język prowadzenia: | polski | ||
| Rodzaj przedmiotu: | obowiązkowe |
||
| Skrócony opis: |
Podstawowy przedmiot studiów, mający zapoznać studentów z pojęciami algorytmu i programu oraz nauczyć ich projektowania, zapisywania, dowodzenia poprawności i uwzględniania złożoności algorytmów. Prezentacja technik programistycznych i struktur danych wykorzystywanych w programowaniu w małej i średniej skali. |
||
| Pełny opis: |
* Pojęcie algorytmu: o historia powstania pojęcia algorytmu o algorytmy znane ze szkoły (Euklidesa, Hornera, rozwiązywanie równań liniowych i kwadratowych) * Języki formalne: o alfabet, składnia i semantyka o gramatyki bezkontekstowe jako narzędzie definiowania składni o definiowanie semantyki przez interpretację wyrażeń poprawnych składniowo * Reprezentacja liczb w komputerze: o stałe całkowite i rzeczywiste o reprezentacje binarne stało- i zmiennopozycyjne o systemy znak-moduł i uzupełnieniowy o rachunek zmiennopozycyjny ? pojęcie zakresu i błędu zaokrągleń * Zmienne i wyrażenia: o typ zmiennej i wartościowanie zmiennych o wyrażenia arytmetyczne i logiczne: składnia i semantyka * Instrukcje while-programów: o pusta, przypisania, warunkowa, iteracji, wyboru, czytania, pisania, wywołania procedury o składnia i semantyka powyższych instrukcji o obliczenia skończone i nieskończone o błędy obliczeń o przykłady algorytmów * Asercje w programach i niezmienniki pętli: o formuły Hoare'a o uzasadnianie poprawności programów o własność stopu i metody jej dowodzenia * Typy danych: o tablice o rekordy o zbiory o pliki o typy wyliczeniowe i okrojone o typy wskaźnikowe * Pliki: o pliki o dostępie bezpośrednim o pliki tekstowe * Funkcje i procedury: o składnia i semantyka o sposoby przekazywania parametrów: przez wartość i przez zmienną o widoczność zmiennych w zagnieżdżonych procedurach * Miary złożoności algorytmów: o koszty algorytmu: czasowy i pamięciowy, pesymistyczny i średni o rozmiar danych o przykłady wyznaczania kosztów o koszt zamortyzowany * Rekurencja: o rekurencyjne wyrażanie pojęć o zastosowania i implementacja o dowodzenie poprawności procedur rekurencyjnych * Programowanie z nawrotami: o przeszukiwanie pełnej przestrzeni stanów o ucinanie rekursji * Metoda dziel i rządź: o metoda inkrementacyjna o podział binarny * Dynamiczne struktury danych: o typy wskaźnikowe o wskaźnikowa realizacja list o podstawowe operacje na listach o listy jednokierunkowe, dwukierunkowe i cykliczne o atrapy i strażnicy * Liniowe struktury danych: stosy i kolejki: o implementacja tablicowa i listowa o implementacja grafu za pomocą list sąsiedztwa o algorytmy DFS i BFS * Drzewa: o implementacja drzew dowolnego rzędu o drzewa binarne o obiegi drzew o konwersja wyrażeń z postaci infiksowej na prefiksową i postfiksową (ONP) * Programowanie zachłanne: o algorytm Huffmana * Metoda spamiętywania: o programowanie dynamiczne |
||
| Literatura: |
1. S.Alagić, M.Arbib, Projektowanie programów poprawnych i dobrze zbudowanych, Wydawnictwa Naukowo - Techniczne 1982 2. L. Banachowski, A.Kreczmar, Elementy analizy algorytmów, Wydawnictwa Naukowo - Techniczne 1987 3. W. Kernighan, Dennis M. Ritchie, Język ANSI C. Programowanie. Wydanie II, Wydawnictwo Helion, Gliwice 2010 4. N.Wirth, Wstęp do programowania systematycznego, Wydawnictwa Naukowo - Techniczne 1999. 5. N.Wirth, Algorytmy+Struktury danych=Programy, Wydawnictwa Naukowo-Techniczne, Warszawa 2001. |
||
| Efekty uczenia się: |
Wstęp do programowania jest podstawowym przedmiotem informatycznym na I roku. Zakładamy, że maturzyści mogli się nie zetknąć z programowaniem, więc naukę programowania prowadzimy od zera. W trakcie nauki programowania studenci poznają jeden język (Pascal) - składnię wraz z semantyką (K_W03). Rzecz jasna w trakcie nauki programowania nie o składnię głównie chodzi. Podstawowym celem kursu jest wyrobienie myślenia algorytmicznego - umiejętność rozpoznania problemu algorytmicznego, jego analiza, zaprojektowanie algorytmu i zakodowanie go, jak również pokazanie poprawności rozwiązania. (K_W04). W tym celu uczymy studentów programowania oszczędnego zarówno pod względem czasowym jak i pamięciowym. Studenci poznają podstawowe struktury danych i techniki algorytmiczne umożliwiające efektywne rozwiązywanie problemów. (K_W05). Sporo uwagi poświęcamy jakości kodu. Zwracamy zatem uwagę na jego poprawność, ale również na właściwe nazewnictwo zmiennych, estetykę tekstową, komentarze, używanie stałych. Na związanych z wykładem zajęciach laboratoryjnych studenci poznają środowisko programistyczne i podstawowe metody uruchamiania programów, (K_U05). Wymagamy też od nich rozumienia algorytmów i ich analizy (K_U06). Ze względu na specyfikę organizacji zadań laboratoryjnych uczymy studentów sumienności i dotrzymywania terminów (K_K05). |
||
| Metody i kryteria oceniania: |
Zaliczenie przedmiotu składa się z trzech elementów:
Kolejne wymagania przedstawione są poniżej:
|
||
Zajęcia w cyklu "Semestr zimowy 2020/21" (zakończony)
| Okres: | 2020-10-01 - 2021-01-31 |
 
 zobacz plan zajęć |
| Typ zajęć: |
Ćwiczenia, 60 godzin więcej informacji Laboratorium, 30 godzin więcej informacji Wykład, 60 godzin więcej informacji |
|
| Koordynatorzy: | Piotr Chrząstowski-Wachtel | |
| Prowadzący grup: | Łukasz Bożyk, Piotr Chrząstowski-Wachtel, Konrad Durnoga, Marcin Dziubiński, Piotr Hofman, Grzegorz Pierczyński, Marek Sokołowski, Michał Startek, Daria Walukiewicz-Chrząszcz, Artur Zaroda | |
| Lista studentów: | (nie masz dostępu) | |
| Zaliczenie: | Egzamin |
Właścicielem praw autorskich jest Uniwersytet Warszawski.