Парадигмы программирования



Скачать 151.51 Kb.
Дата22.12.2012
Размер151.51 Kb.
ТипЗадача
Программа учебного курса

ПАРАДИГМЫ ПРОГРАММИРОВАНИЯ


  1. Организационно-методический раздел.

    1. Курс реализуется в рамках направления 552800 «Информатика и вычислительная

техника», относится к циклу специальных дисциплин.

Цели и задачи курса

Цель курса - систематизация знаний о возможностях и особенностях разных стилей и методов программирования при решении различных задач системного программирования, а также создания и применения информационных систем.

Задача курса - изучение исторически существенных парадигм программирования, оказавших влияние на лицо современных информационных технологий.

    1. Требования к уровню освоения содержания курса

По окончании изучения указанной дисциплины студент должен


иметь представление:

  • о наиболее общих концепциях и идеях программирования

  • о проблемах, решаемых при разработке программ на разных языках программирования

  • об особенностях реализации систем программирования на примере ряда языков (Lisp, Forth, ассемблер, Apl, Sisal, Setl, Python, Perl, Gpm и др.)

знать

  • методы представления программ и данных в языках и системах программирования

  • эффективные методы реализации языков программирования

уметь

  • применять и обосновано выбирать стили и методы программирования при решении задач информационной обработки




    1. Формы контроля

Итоговый контроль. Для контроля усвоения дисциплины учебным планом предусмотрен дифференцированный зачет и экзамен.

Текущий контроль. В течение семестра выполняются ряд лабораторных работ, готовится реферат и проводится дистанционное тестирование знаний по функциональному программированию. Выполнение указанных видов работ является обязательным для всех студентов, а результаты текущего контроля служат основанием для выставления оценок в ведомость контрольной недели на факультете.


  1. Содержание дисциплины

    1. Новизна и актуальность курса

Используя актуальные знания о современных, постоянно развивающихся методах и технологиях программирования, учебный курс концентрирует внимание на фундаментальных проблемах, принципах и правилах разработки сложных программных комплексов для решения задач информационной обработки и системного программирования, анализе способов решения этих проблем и причин, ограничивающих возможности.

Тематический план курса (распределение часов).





Наименование разделов и тем

К о л и ч е с т в о ч а с о в


Лекции


Семинары

Лабора-торные работы

Самосто-ятельная работа

Всего

часов

Раздел 1 Общие сведения о парадигмах программирования.

6




4

8

18

Раздел 2. Рекурсивные представления данных и программ. Отображения и функционалы.

6




6

6

18

Раздел 3. Реализационные решения. Низкоуровневое программирование.

6




4

8

18

Раздел 4. Основные стратегии на разных интервалах жизненного цикла программ. ООП. Недетерминизм. Отложенные действия.

8




8

18

34

Раздел 5. Программирование

функций высших порядков. Языки сверхвысокого уровня.

6




8

12

26

Раздел 6. Обработка текстов программ и методы оптимизации.

Суперпрограммирование

4




6

8

18

Итого по курсу:

36




36

60

132



    1. Содержание отдельных разделов и тем.


А) Теоретическая часть
Раздел 1. Общие сведения о парадигмах программирования. Основные идеи функционального программирования. Элементарный Лисп. Универсальная функция.

Изучается ключевой метод программирования – выбор первого шага при освоении класса решаемых задач на примере организации информационной обработки символьными выражениями в языке Лисп. Вводятся базовые понятия, достаточные для символьного представления программ. Формализм рекурсивных функций и простые алгоритмы символьной обработки привлечены для обоснования и демонстрации разных подходов к представлению программ. Дано представление о функциональном программировании и сфере его применения с иллюстрациями на материале истории языка Лисп и его реализаций. Рассматривается роль функционального стиля в жизненном цикле программного обеспечения и эволюции информационных технологий.
Раздел 2. Рекурсивные представления данных и программ. Отображения и функционалы. Имена, определения, контексты. Свойства атомов и категории функций. Ввод и вывод данных. Структуры и деревья. Список как частный вид структуры. Работа со списками. Добавление элемента в список. Удаление элемента из списка. Рассматривается классическая программотехника использования функций и вспомогательных параметров при организации обычных вычислений как альтернатива операторам присваивания и глобальным переменным, а также как метод управления эффективностью вычислений. Приводится простейшее определение универсальной функции, задающей границы вычисления правильных программ, представленных в символьной форме. Программирование отображений и использование функционалов демонстрируется как результативный метод резкого повышения темпа программирования и отладки программ. Изучается механизм безымянных определений функций и методика их использования в отображающих функционалах. Заодно происходит знакомство с лисповской арифметикой и мультиоперациями, а также со средствами обработки строк и литер.
Раздел 3. Детализация базовых функций. Компиляция функциональных программ. Реализационные решения. Низкоуровневое программирование. Изучаются требования к компиляции функциональных программ и строится определение компилятора. Для Лиспа такое определение написано на Лиспе как и определение интерпретатора. Определение дано согласно Венской методике в форме отображения абстрактного синтаксиса языка на язык абстрактной машины. Разложение программы на категории функций с разным уровнем отладки является отправной точкой при выборе оптимизационных решений. Компиляция программ рассматривается как один из методов статической оптимизации процессов. Рассматривается язык Forth и ассемблер.
Раздел 4.Основные стратегии на разных интервалах жизненного цикла программ. ООП. Недетерминизм. Отложенные действия.

Рассмотрены основные принципы объектно-ориентированного программирования и проанализированы схемы их реализации в рамках функционального программирования на базе ряда структур данных на примере простой модели ОО-языка, встраиваемого в Лисп. Отмечены особенности CLOS, поддерживающей ООП на GNU Clsip. Реализация методов обработки объектов заданного класса сводится к отдельной категории функций, вызов которых управляется анализом принадлежности аргумента классу.
Описаны приемы организации недетерминированных вычислений в рамках функционального стиля программирования. Реализация программ с возвратами, перебор вариантов, откат влекут расширение семантического базиса механизмами обработки прерываний. Анализируется соответствие точности решения задач и уровня их изученности. Исследуются связь диагностической интерпретации и средств логического программирования. Обработка множеств, последовательностей и хэш-таблиц дает материал для простых примеров.
Рассматривается особенно эффективное обобщение процесса информационной обработки, вытекающее из возможности отложенных действий (lazy evaluation), органически присущей функциональному программированию благодаря унификации представления данных и программ. Анализируются резервы производительности обобщенных процессов и методы динамической оптимизации вычислений, приводящие к смешанным и параллельным вычислениям.
Раздел 5. Программирование функций высших порядков. Языки сверхвысокого уровня.
Изучается аппарат функций высших порядков при организации высоко квалифицированных процессов синтаксически управляемой информационной обработки, использующей формализацию и спецификацию данных, таких как синтаксический анализ, кодогенерация, конструирование интерпретаторов и компиляторов по формальному определению реализуемого языка.
Техника разработки сложных программ иллюстрируется на задаче поддержки полного жизненного цикла с помощью быстрого прототипирования, оперативного тестирования и уточняемой спецификации программ. В этом плане по существу используется возможность введения частично определенных функций, варьируемых и улучшаемых конструкций, а также специализация интерпретатора программ с целью оценки уровня достоверности построений.
Раздел 6. Обработка текстов программ и методы оптимизации. Суперпрограммирование.
Анализируются наиболее очевидные закономерности эволюции языков программирования, отражающие расширение класса решаемых задач, прогресс элементной базы и рост квалификации программистов. Рассматривается ряд наиболее популярных свободно распространяемых реализаций языков программирования, их инструментальная поддержка. Рассматриваются языки Apl, Sisal, Setl, Python, Perl, Gpm и др. как примеры разных подходов к решению особо сложных задач.
Б) Практические занятия

Цели практикума по курсу "Парадигмы программирования" заключаются в приобретении навыков работы с разными стилями подготовки и совершенствования программ, а также понимания разных точек зрения на качество программирования и эффективность программ.
Ознакомительные лабораторные работы:
1)Основные элементы языка Lisp, отладчик

2)Операции над списками, строками и арифметические операции

3)Операции ввода-вывода и списки свойств атомов, базы данных

4) Отображения

5) ООП

6) Варианты и обработка событий

7) ФВП для конструирования лексических и синтаксических анализаторов текстов
Типовые примеры выполняемых индивидуальных заданий:
1. Определить отладочную версию калькулятора.

2. Определить проверку выражений на согласованность по арности

функций /в списке свойств информация о числе аргументов/.

3. Определить интерпретацию выражений с типовым контролем:

/в списке свойств имени функции хранится предикат,

проверяющий типы аргументов/

4. Написать функцию, анализирующую определения функций

и строящую предикат для типового контроля.

5. Проверить выражение на определенность входящих в него

функций, не учитывая изменение определений при интерпретации.

6. Пусть логические операции заданы как тесты, хранимые в списке свойств. Определить интерпретацию логических выражений.

7. Выберем списочное представление физических формул. Определить вывод размерности величин, соответствующих заданой формуле.

8. Для произвольного списка построить список частот вхождений атомов /можно список атомов, а частоты - в списках свойств

с заданным индикатором свойства/.

9. Построить список уникальных атомов выражения,

т.е. входящих по одному разу, не более.

10. Пусть имеется множество атомов, внешне совпадающих с названиями музыкальных ансамблей /автомобилей, городов, фирм и т.п.

Список свойств каждого атома хранит некоторые характеристики,

выделяемые с помощью заданного набора индикаторов.

а) Промоделировать обычную работу базы данных

/наполнение, доступ, коррекция, выборки-вырезки, сводки

б) Организовать оценку информации экспертами

/имя эксперта - индикатор его оценки.

    1. Перечень примерных контрольных вопросов и заданий для самостоятельной работы



Задания для рефератов



1. Сравнить 2-4 языка программирования (классика и модерн)

  1. Дать характеристику особенностей заданного языка программирования




  1. Учебно-методическое обеспечение дисциплины

    1. Имеется Интернет-поддержка части курса, посвященной функциональному программированию.

    2. Образцы вопросов для подготовки к экзамену


1. Функциональное программирование в отличие от традиционного

2. Рекурсивные функции в сравнении с итерациями при вычислениях

3. Представление информации списками

4. Использование вспомогательных параметров функций

5. Программирование отображений произвольных списков

6. Локальные определения при определении сложных функций

7. Основы обработки списков - чистый Лисп

8. Общая схема интерпретации Лисп-выражений

9. Абстрактная машины для определения языка программирования (secd)

10. Общая схема компиляции Лисп-выражений в код secd-машины

11. Организация недетерминированных вычислений

12. Реализация отложенных действий

13. Эффективность замедленных (lazy) вычислений

14. Моделирование работы с множествами

15. Списки свойств и моделирование баз данных

16. Структура памяти и данных, используемых при реализации Лиспа

17. "Сборка мусора" - повторное использование памяти

18. Функциональные аргументы

19. Вычисление функций при интерпретации выражений. Примеры

20. Конструирование функций по ходу вычислений. Примеры

21. Ассоциативный список, его организация и применение в интерпретаторе

22. Спецификация типов данных и их анализ при программировании

23. Динамический котроль соотвествия типов данных

24. Логика и предикаты, истиность, вычислимость и неопределенность

25. Расширенная обработка списков, их анализ и реорганизация

26. Моделирование графов и функции их обработки

27. Подстановки и сцепления списков

28. Символьные вычисления на примере дифференцирования

29. Конструирование анализатора с помощью функций высших порядков

30. Отладка и режим обработки программы
31. Forth - основная идея, подход к построению ПО, история

32. Forth - стек и организация памяти

33. Forth - арифметика и непосредственно исполнимые выражения

34. Forth - определения, новые слова и управление интерпретацией

35. Forth - словари, компиляция и шитый код
36. Python - основная идея, подход к построению ПО, история

37. Python - структуры данных и организация памяти

38. Python - блоки и специфика синтаксиса

39. Python - выражения и функции, типы данных
40. Perl - основная идея, подход к построению ПО, история

41. Perl - структуры данных, организация памяти и программы

42. Perl - динамика функционирования сценариев в Интернете

43. Perl - стыковка интерфейса с базами данных
44. PHP - основная идея, подход к построению ИС, история

45. HTML - основная идея, подход к представлению данных, история

46. XML - основная идея, подход к представлению данных, история

47. JavaScript - основная идея, подход к построению ИС, история
48. Компонентная технология разработки ИС

49. UML - изобразительные средства в процессе разработки ИС

50. Распределенные ИС и Grid-технологии


    1. Список основной и дополнительной литературы


П.Хендерсон. Функциональное программирование. Применение и реализация. Перевод Л.Т.Петровой под редакцией А.П.Ершова. М.:"Мир",1983, с.349
John McCarthy, Paul W. Abrahams, Daniel J. Edwards, Timothy P. Hant, Michael L. Levin. Lisp 1.5 Programmer Manual. MIT Press, 1962
С.С. Лавров Г.С. Силигадзе "Входной язык и интерпретатор системы программирования на базе языка лисп для машины БЭСМ-6" Москва 1969
Э.Хювенен Й.Сеппянен "Мир Лиспа" в 2х томах. Перевод А.А.Рейтсакаса под редакцией В.Л.Стефанюка Москва "Мир" 1990
А.Филд, П.Харрисон Функциональное программирование. Перевод под редакцией В.А.Горбатова. - М. <Мир>, 1993, с. 638
Д. Браун. Рекурсивные методы в программировании. М."Мир", 1974, с. 80
Евстигнеев В.А. Применение теории графов в программировании.-

М.: Наука, 1985
Малпас Дж. Реляционный язык Пролог и его применение.- М.: "Наука", 1990, 463с.
Оллонгрен А. Определение языков программирования интерпретирующими автоматами. М.: Мир, 1977, 288 с.
Patrick Suppes. Axiomatic Set Theory. New York, Dover

Publications, Inc. p. 267
Hindley, Lercher, Seldin. Introduction to the Combinatory

Logic.
M.J. Gordon, A.J. Milner, C.P. Wadsworth. Edinburgh LSF.

Berlin, Heidelberg, New York : Springer-Verlag, LNCS 78, p. 159
К.Таунсенд, Д.Фохт Проектирование и программная реализация экспертных систем на персональных ЭВМ
Cann D.C. SISAL: 1.2 A Brief Introduction and

Tutorial. - Preprint UCRL-MA-110620. Lawrence Livermore National Lab., Liermore, California, May 7, 1992.

Л.В.Городняя "Основы функционального программирования" - М.: www.intuit.ru, Серия "Основы информационных технологий", Курс лекций, 2004, 272 с.

Сайты с материалами по языкам программирования:

http://www.marstu.mari.ru/mmlab/home/lisp/title.htm – Дистанционный учебник М.Н.Морозова
http://grimpeur.tamu.edu/~colin/lp/ - Небольшой учебник для начального знакомства с Лиспом
http://www.paulgraham.com/onlisptext.html - Интересные материалы по Clisp Паула Грэхема, автора книги по стандарту ANSI Clisp
http://www.iis.nsk.su/persons/zamulin/OOPCourse.zip – Курс ООП А.В.Замулина

Программу подготовила:

к.ф.-м.н., доцент Городняя Л.В.

Программа утверждена на заседании Ученого совета факультета информационных технологий Новосибирского государственного университета 18 декабря 2003 г., протокол заседания №16.
Декан ФИТ НГУ,

д.ф.-м.н. М.М.Лаврентьев

Похожие:

Парадигмы программирования iconЛекция Определение языков программирования Прежде чем анализировать конкретные парадигмы программирования, рассмотрим задачу определения систем программирования
Прежде чем анализировать конкретные парадигмы программирования, рассмотрим задачу определения систем программирования. Строится простейшее...
Парадигмы программирования iconЭкзаменационные вопросы по информатике
Парадигмы программирования. Основные подходы программирования. Типизация языков. Классификация c и С++ с точки зрения парадигм, подходов...
Парадигмы программирования iconФилософия Lisp. Понятие о побочном эффекте. Цикл repl
Классификация языков программирования. Способы классификации. Методологии, парадигмы и стили яп. Классификация декларативного программирования....
Парадигмы программирования iconПлан-проспект спецкурса "Математические основы функционального программирования"
Целью курса является приобретение фундаментальных знаний в области построения программных систем с использованием современных языков...
Парадигмы программирования iconЛекция Языки и системы программирования
Понятие о системе программирования, ее основные функции и компоненты. Принципы работы сред программирования. "Операционные" и "модульные"...
Парадигмы программирования iconПериод, развитие общества
Эволюция образовательной парадигмы в истории человечества. Современные образовательные парадигмы
Парадигмы программирования icon16 марта в 17. 45 аудитория 402 главного корпуса Программа курса Основы программирования
Основы программирования. Методика программирования во Flash. Носители кода. Язык Action Script (AS), история, корни. Окно Actions....
Парадигмы программирования iconПравила текстовых замен. Алгоритм подстановки текстов. Аппликативные языки программирования. Основные парадигмы аппликативных яп. Вычислительные структуры аппликативных яп
Описание формальных языков. Синтаксические диаграммы. Контекстные условия и семантика
Парадигмы программирования iconЭтнопсихолингвистика и лингвокультурология
Ным состоянием гуманитарной науки, в частности – изменением научной парадигмы и кристаллизацией новой парадигмы исследований, а также...
Парадигмы программирования iconТемы, рассмотренные в курсе «Программирование» для гр. 1100 — 1125 (весна 2009/2010 уч гг., проф. Павловская Т. А. )
Критерии качества программ. Понятия парадигмы и технологии программирования. Модели жизненного цикла по. Гибкие технологии: экстремальное...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org