Uniwersytet Warszawski - Centralny System Uwierzytelniania
Strona główna

Wstęp do programowania

Informacje ogólne

Kod przedmiotu: 1000-211bWPI
Kod Erasmus / ISCED: 11.301 Kod klasyfikacyjny przedmiotu składa się z trzech do pięciu cyfr, przy czym trzy pierwsze oznaczają klasyfikację dziedziny wg. Listy kodów dziedzin obowiązującej w programie Socrates/Erasmus, czwarta (dotąd na ogół 0) – ewentualne uszczegółowienie informacji o dyscyplinie, piąta – stopień zaawansowania przedmiotu ustalony na podstawie roku studiów, dla którego przedmiot jest przeznaczony. / (0612) Database and network design and administration Kod ISCED - Międzynarodowa Standardowa Klasyfikacja Kształcenia (International Standard Classification of Education) została opracowana przez UNESCO.
Nazwa przedmiotu: Wstęp do programowania
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: 12.00 Podstawowe informacje o zasadach przyporządkowania punktów ECTS:
  • roczny wymiar godzinowy nakładu pracy studenta konieczny do osiągnięcia zakładanych efektów uczenia się dla danego etapu studiów wynosi 1500-1800 h, co odpowiada 60 ECTS;
  • tygodniowy wymiar godzinowy nakładu pracy studenta wynosi 45 h;
  • 1 punkt ECTS odpowiada 25-30 godzinom pracy studenta potrzebnej do osiągnięcia zakładanych efektów uczenia się;
  • tygodniowy nakład pracy studenta konieczny do osiągnięcia zakładanych efektów uczenia się pozwala uzyskać 1,5 ECTS;
  • nakład pracy potrzebny do zaliczenia przedmiotu, któremu przypisano 3 ECTS, stanowi 10% semestralnego obciążenia studenta.

zobacz reguły punktacji
Język prowadzenia: polski
Rodzaj przedmiotu:

obowiązkowe

Skrócony opis:

Podstawowy przedmiot studiów wprowadzający w dziedzinę informatyki, 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:

◦ historia powstania pojęcia algorytmu

◦ przykłady algorytmów (Euklidesa, Archimedesa, Hornera, rozwiązywanie równań liniowych i kwadratowych)

◦ pojęcie dziedziny algorytmicznej

• Podstawy języka programowania:

◦ notacja do opisu składni języka (np. gramatyki bezkontekstowe lub BNF),

◦ pojęcie składni i semantyki

◦ dziedzina algorytmiczna:

▪ wyrażenia arytmetyczne (liczby całkowite i zmiennopozycyjne)

▪ wyrażenia logiczne

▪ znaki i napisy

◦ zmienne, ich typ, instrukcja przypisania

◦ definiowanie funkcji (bez rekurencji):

▪ parametry

▪ wartość przekazywana i typ void

▪ wywoływanie funkcji

▪ zmienne lokalne

◦ instrukcja warunkowa,

◦ pętla while

◦ pętla for

◦ instrukcja wyboru

◦ znaki i napisy

◦ wczytywanie i wypisywanie

◦ instrukcja pusta

◦ reprezentacja liczb całkowitych

◦ reprezentacja liczb zmiennopozycyjnych, pojęcie zakresu i błędów zaokrągleń

• Dekompozycja problemu i weryfikacja programów:

◦ specyfikacja problemu, warunek początkowy i końcowy,

◦ częściowa poprawność i własność stopu,

◦ asercje

◦ formuły Hoare’a

◦ niezmienniki pętli

◦ własność stopu i metody jej dowodzenia

◦ uzasadnianie poprawności programów

◦ przykłady dekompozycji problemów i weryfikacji programów

• Typy danych:

◦ tablice,

◦ struktury,

◦ unie,

◦ deklaracje typów

◦ reguły zgodności typów

• Pliki:

◦ nośniki pamięci

◦ pliki tekstowe

◦ mechanizm buforowania

◦ standardowe wejście i wyjście jako strumienie

• Przydatne narzędzia i technikalia

◦ makrodefinicje i pre-processing

◦ definicje stałych

◦ klasy: typy obiektów z ograniczonym zestawem metod operujących na nich

◦ wywoływanie metod obiektu

◦ metody wywoływane implicite: konstruktory, destruktory, kopiowanie, rzutowanie typów

◦ przeładowanie operatorów

◦ typy wyliczeniowe

◦ przydatne typy danych

• Typy wskaźnikowe:

◦ pojęcie wskaźnika, dereferencja,

◦ przekazywanie argumentów (i wyników) przez wartość, wskaźnik i referencję

◦ zmienne globalne i lokalne,

◦ pamięć alokowana dynamicznie,

◦ smart pointers -- wskaźniki unikalne i współdzielone

• Modularyzacja i bariery abstrakcji

◦ pliki nagłówkowe i implementacja

• Rekurencja:

◦ rekurencja i jej sposób implementacji

◦ rekurencyjne wyrażanie problemów

◦ weryfikacja programów rekurencyjnych

• Analiza złożoności algorytmów:

◦ rachunek rzędów funkcji

◦ koszty algorytmu: czasowy i pamięciowy, pesymistyczny i średni

◦ rozmiar danych

◦ analiza programów rekurencyjnych

◦ koszt zamortyzowany

◦ przykłady wyznaczania kosztów

• Metoda "dziel i rządź":

◦ metoda inkrementacyjna

◦ podział binarny, w tym wyszukiwanie binarne

◦ przykłady -- algorytmy sortowania

• Dynamiczne struktury danych:

◦ typy wskaźnikowe

◦ wskaźnikowa realizacja list

◦ podstawowe operacje na listach

◦ listy jednokierunkowe, dwukierunkowe i cykliczne

◦ stosy i kolejki

◦ atrapy i strażnicy

•  Drzewa:

◦ drzewa binarne, BST

◦ implementacja drzew dowolnego rzędu

◦ obiegi drzew

• Przydatne biblioteczne struktury danych:

◦ słowniki (mapy)

◦ tablice haszujące

◦ zbiory

◦ kolejki

◦ stosy

• Programowanie z nawrotami:

◦ przeszukiwanie pełnej przestrzeni stanów

◦ heurystyki przyspieszające

◦ ucinanie rekursji

• Programowanie dynamiczne

◦ metoda spamiętywania

◦ tablicowanie

◦ programowanie dynamiczne na drzewach

• Programowanie zachłanne:

◦ algorytm Huffmana

◦ inne przykłady

• Przeszukiwanie grafów:

◦ implementacja macierzowa i listowa grafów

◦ przeszukiwanie wszerz

◦ przeszukiwanie w głąb

◦ algorytm Floyda-Warshalla

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ę:

Wiedza: student zna i rozumie:

* teoretyczne podstawy z zakresu programowania, algorytmów i złożoności, architektury systemów komputerowych, systemów operacyjnych, technologii sieciowych, wybranych języków i paradygmatów programowania, baz danych, inżynierii oprogramowania (K_W02);

* w zaawansowanym stopniu podstawowe konstrukcje programistyczne (przypisanie, instrukcje sterujące, wywoływanie podprogramów i przekazywanie parametrów, deklaracje i typy, mechanizmy abstrakcji) oraz pojęcia składni i semantyki języków programowania (K_W03);

* podstawowe metody projektowania, analizowania i programowania algorytmów (projektowanie strukturalne, rekurencja, metoda dziel i rządź, programowanie z nawrotami, poprawność, metoda niezmienników, złożoność obliczeniowa) (K_W04);

* podstawowe struktury danych i wykonywane na nich operacje (reprezentacja danych liczbowych, arytmetyka i błędy zaokrągleń, tablice, napisy, zbiory, struktury, pliki, wskaźniki i referencje, struktury wskaźnikowe, listy, stosy, kolejki, drzewa i grafy) (K_W05).

Umiejętności: student potrafi:

* zastosować wiedzę matematyczną do formułowania, analizowania i rozwiązywania związanych z informatyką zadań (K_U01);

* czytać ze zrozumieniem programy zapisane w językach programowania bazujących na wybranych paradygmatach (K_U06);

* posługiwać się przyjętymi formatami reprezentacji różnego rodzaju danych stosownie do sytuacji (liczby, tablice, tekst) pamiętając o ich ograniczeniach, np. związanych z arytmetyką komputera (K_U08).

Kompetencje społeczne: student jest gotów do:

* krytycznej oceny posiadanej wiedzy i odbieranych treści (K_K01);

* pracy z poszanowaniem uczciwości intelektualnej w działaniach własnych i innych osób; przestrzegania zasad etyki zawodowej i wymagania tego od innych oraz dbałości o dorobek i tradycje zawodu informatyka (K_K02);

* uznawania znaczenia wiedzy w rozwiązywaniu problemów poznawczych i praktycznych oraz wyszukiwania informacji w literaturze oraz zasięgania opinii ekspertów (K_K03).

Zajęcia w cyklu "Semestr zimowy 2023/24" (zakończony)

Okres: 2023-10-01 - 2024-01-28
Wybrany podział planu:
Przejdź do planu
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, Marcin Kubica
Prowadzący grup: Łukasz Bożyk, Paweł Brach, Piotr Chrząstowski-Wachtel, Jacek Chrząszcz, Marcin Dziubiński, Krzysztof Fleszar, Eryk Kopczyński, Marcin Kubica, Paweł Parys, Jakub Pawlewicz, Marcin Peczarski, Jakub Radoszewski, Przemysław Rutka, Marcin Smulewicz, Michał Startek, Daria Walukiewicz-Chrząszcz, Marcin Waniek, Artur Zaroda
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Uniwersytet Warszawski.
ul. Banacha 2
02-097 Warszawa
tel: +48 22 55 44 214 https://www.mimuw.edu.pl/
kontakt deklaracja dostępności USOSweb 7.0.1.0-03d50b88b (2024-02-19)