Uniwersytet Kardynała Stefana Wyszyńskiego w Warszawie - Centralny System Uwierzytelniania
Strona główna

Programowanie w logice i funkcyjne

Informacje ogólne

Kod przedmiotu: WM-I-U-PWL
Kod Erasmus / ISCED: (brak danych) / (brak danych)
Nazwa przedmiotu: Programowanie w logice i funkcyjne
Jednostka: Wydział Matematyczno-Przyrodniczy. Szkoła Nauk Ścisłych
Grupy:
Strona przedmiotu: https://zdanowski.blog.uksw.edu.pl/
Punkty ECTS i inne: 0 LUB 5.00 (w zależności od programu) 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
Poziom przedmiotu:

zaawansowany

Symbol/Symbole kierunkowe efektów uczenia się:

I2_W01, I2_W04, I2_W05, I2_K01

Skrócony opis:

Kurs przedstawia dwa główne paradygmaty programowania inspirowane logiką. Pierwszy z nich to Programowanie w Logice. Kurs przedstawia podstawy teoretyczne paradygmatu takie jak unifkacja, metoda rezolucji dla logiki pierwszego rzędu, SLD rezolucja. Opisuje w jaki sposób stanowią one podstawę mechanizmu obliczeniowego Prologu. Następnie w ramach opisu języka Prolog student ma możliwość poznać wykorzystanie tych narzędzi oraz różnice pomiędzy implenetacją i jej teoretycznymi podstawami. W części poświęconej programowaniu funkcyjnemu przedstawione zostają podstawowe cech programowania funkcyjnego jak: przejrzystość referencyjna, niezmienność danych, bezstanowość, brak efektów ubocznych, itp. Kurs prezentuje odstawy rachunku lambda i redukcji termów. Następnie kurs przedstawia podstawowe techniki programowania w Haskellu oraz ich związki z rachunkiem lambda.

Pełny opis:

1. Podstawowe cechy paradygmatu programowania w logice:

deklaratywny styl programowania,

mechanizm wnioskowania, formuły Hornowskie,

środki kontroli nad wnioskowaniem/obliczeniem.

Mechanizm rezolucji dla klasycznego rachunku zdań.

2. Składnia logiki pierwszego rzędu. Uniwersum Herbranda.

Formuły Hornowskie.

Definicja spełniania dla formuł Hornowskich.

Unifikacja i rezolucja w logice pierwszego rzędu. Twierdzenie o istnieniu

najbardziej ogólnego unifikatora (MGU).

3. SLD rezolucja w logice pierwszego rzędu. Twierdzenie o pełności dla rezolucji i SLD rezolucji.

Twierdzenie o nierozstrzygalności SLD rezolucji.

Reprezentowanie wiedzy w Prologu.

Podstawy pracy z interpreterem Prologu (Swi-Prolog).

4. Znaczenie symboli '=' i '==' w Prologu. Kontrola nad przebiegiem wykonania programu: kolejność wyboru

klauzul do unifikacji, nawracanie, odcięcie (cut), wymuszenie nawrotu (fail).Sledzenie wykonania programu. Meta predykaty: clause/2, assert/1, retract/1.

5. Obsługa plików, programowanie wejścia i wyjścia.

Arytmetyka w Prologu. Znaczenie 'is' oraz '=:='.

6. Negacja w Prologu. Założenie o domkniętości świata (closed world assumption).

SLDNF rezolucja. Modele stabilne.

7. Reprezentowanie struktur rekurencyjnych: lista, drzewo.

Technika programowania z akumulatorem.

Listy różnicowe.

8. Wprowadzenie do rachunku lambda.

Interpretacje wartości logicznych, instrukcji

warunkowej, iloczynu kartezjańskiego w rachunku lambda.

Redukcje termów. Operator punktu stałego Y.

9. Arytmetyka w rachunku lambda.

Własności programowania funkcyjnego:

przejrzystość referencyjna, niezmienność danych, bezstanowość, brak efektów ubocznych,

funkcje jako podstawowe obiekty, rekursja, leniwa ewaluacja, typy,

polimorfizm, funkcje wyższych rzędów.

10. Wprowadzenie do języka Haskell.

Podstawy składni, konwencje nazewnicze i pierwsze programy.

Podstawowe typy: logiczny, znakowy, typy liczbowe.

Listy, pary, typy funkcji.

Operacje curry i uncurry.

Polimorfizm. Klasy typów.

Definiowanie typów.

11. Definiowanie funkcji: wyrażenia lambda, złożenie funkcji, rekursja, dopasowywanie wzorca.

Definiowanie funkcji przez równoległą rekursję.

Podstawowe operacje na listach.

12. Typy rekurencyjne. Definiowanie funkcji działających na typach

rekurencyjnych. Implementacja drzewa.

13. Kontynuacje i monady.

Problem obsługi wejścia i wyjścia w językach funkcyjnych, efekty uboczne, niepowtarzalność wyniku.

Typ IO. Obsługa plików.

14. Struktury nieskonczone w Haskellu.

15. Elementy programowania funkcyjnego w imperatywnych językach programowania.

Połączenie paradygmatów: funkcyjne programowanie w logice. Język Curry.

Literatura:

Clocksin, Mellish, Prolog. Programowanie. Helion

Nilsson, Małuszyński, Programming in Prolog, Wiley & Sons Ltd, wolny dostęp: http://www.ida.liu.se/~ulfni53/lpp/

Harold Abelson, Gerald Jay Sussman, Julie Sussman, Struktura i interpretacja programów komputerowych, WNT.

Paul Hudak, John Peterson, Joseph Fasel,

A Gentle Introduction to Haskell, Version 98, 2000,

wolny dostęp: https://www.haskell.org/tutorial/

Richard Bird, Introduction to Functional Programming using Haskell.

Simon Peyton Jones (ed.), Haskell 98. Language and Libraries. The Revised Report. 2002, wolny dostęp: https://www.haskell.org/definition/haskell98-report.pdf

Efekty kształcenia i opis ECTS:

Zna teoretyczne podstawy stojące za deklaratywnym i funkcyjnym paradygmatem programowania (rezolucja, uniwersum Herbranda, rachunek lambda). (I2_W01)

Zna własności deklaratywnych i funkcyjnych języków programowania. (I2_W04)

Zna metody analizy poprawności programów deklaratywnych wykorzystujące SLD rezolucję i funkcyjnych przez analizę termów i ich redukcję. (I2_W05)

Jest świadomy potrzeby aktualizacji wiedzy dotyczącej standardów języków programowania oraz ich implementacji. (I2_K01)

Metody i kryteria oceniania:

egzamin pisemny

Zajęcia w cyklu "Semestr letni 2021/22" (zakończony)

Okres: 2022-02-01 - 2022-06-30
Wybrany podział planu:
Przejdź do planu
Typ zajęć:
Laboratorium, 30 godzin więcej informacji
Wykład, 30 godzin więcej informacji
Koordynatorzy: Konrad Zdanowski
Prowadzący grup: Konrad Zdanowski
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzaminacyjny
E-Learning:

E-Learning (pełny kurs) z podziałem na grupy

Typ przedmiotu:

obowiązkowy

Grupa przedmiotów ogólnouczenianych:

nie dotyczy

Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Uniwersytet Kardynała Stefana Wyszyńskiego w Warszawie.
ul. Dewajtis 5,
01-815 Warszawa
tel: +48 22 561 88 00 https://uksw.edu.pl
kontakt deklaracja dostępności USOSweb 7.0.2.0-1 (2024-03-12)