Курс: Дискретная математика Описание
Введение

Связь с аппликативным компьютингом

Что в курсе изучается

Для кого курс

Как курс читается

Видеокурс

Введение

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

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

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

Вверх

Связь с аппликативным компьютингом

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

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

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

Вверх

Что в курсе изучается?

Вот тот круг вопросов, которые, как ожидается, будут изучены (некоторые -- ознакомительно, другие -- углубленно):
 
  • математические основы вычислений с объектами,
  • аппликативные вычислительные системы,
  • вычисление значения выражений,
  • разложения в комбинаторных базисах,
  • системы типов,
  • вычисления в категории,
  • построение абстрактных машин,
  • динамическое формирование инструкций в процессе вычислений,
  • общие вопросы программирования в суперкомбинаторах.

Вверх

Для кого курс (кому этот курс особенно полезен)

В полном объеме -- это продвинутый курс, который идеально походит для аспирантов и соискателей ученых степеней, при подготовке диссертации магистра или бакалавра на втором году обучения. В этом случае курс особенно полезен для развития навыков выполнения научно-исследовательской работы для тех, кто специализируется в области Информационных Систем, Информационных Технологий, Информатики.  Продвинутый курс отлично подходит для тех, кто уже выполнил некоторую часть НИР и желает систематизировать результаты, понять их взаимосвязи, оценить степень полноты фактов, разбить результаты на классы, сопоставить информацию, полученную из разных источников и т.п. Для целей выполнения комплексной НИР студент должен понимать, что он уже должен разбираться в следующих вопросах:

  • базы данных, информационные системы или принципы искусственного интеллекта (к примеру курс по системам управления базами данных, по глобальным информационным системам) либо  иметь опыт работы по созданию значительных схем баз данных и по приложениям с интенсивным обменом данными (скажем, студент специализируется либо в области баз данных/информационных систем, либо в аспектах СИИ/технологиях семантических сетей);
  • начала или полная техника работы в Web, включая HTML (умение построить домашнюю страницу), XML (общего знакомства может хватить для подготовленного студента;
  • некоторую программистскую подготовку, минимальное знание Java и какого-либо языка сценариев.

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

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

Вверх

Как курс читается?

Организация учебного процесса заключается в следующем:

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

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

Образовательная философия: для всех нас интерес представляет "научиться тому, как учиться", а не просто освоение информации, которая кем-то излагается в упорядоченном виде.

Вверх

Содержание видеокурса (Как купить, см. URL http://www.jurinfor.ru/educ/dvdcl.php)

Часть I. Аппликативный компьютинг.

1. Ламбда-конверсии
1.1. Запись функции с использованием оператора функциональной абстракции.
1.2. Строение формальной системы ламбда-конверсий.
1.2.1. Объекты.
1.2.2. Интерпретация объектов ламбда-исчисления.
1.3. Свободные и связанные переменные.
1.4. Нормальные формы.
1.5. Редукция. Конверсии.
1.6. Подстановка.
1.7. Постулаты формальной системы ламбда-конверсий.
1.8. Метаоператоры аппликации и абстракции.

2. Комбинаторы
2.1. Выражение общих законов комбинаторами.
2.2. Конверсии и строение формальной системы комбинаторной логики.
2.3. Синтез объекта с заданными свойствами.
2.4. Представление абстракции.
2.5. Интерпретация объектов комбинаторной логики.
2.6. Парадоксальный комбинатор Карри Y.
2.7. Неподвижная точка. Теорема о неподвижной точке.

3. Базисы
3.1. Метод погружения.
3.2. Базис I, K, S и алгоритм разложения в базисе .
3.3. Свойство базисности.
3.4. Базис I, B, C, S и алгоритм разложения в базисе .

4. Нумералы
4.1. Представление нумералов.
4.2. Свойства нумералов.
4.3. Функция “следование за”.
4.4. Вычисления с нумералами.
4.5. Вычисления с неподвижной точкой.

5. Встроенные системы
5.1. Погружение и встроенные вычислительные системы.
5.2. Осуществление погружения. Большой пример.
5.3. Содержательная идея, предформализация, формализация.
5.4. Аксиоматизация встроенной системы.
5.5. Пример формулировки теоремы о погружении.
5.6. Доказательство теоремы о погружении разбором случаев.
5.7. Концепт-теория и индивид-теория.

Часть II. Компьютинг в декартово замкнутой категории (д.з.к.).

6. Вычисления в категории.
6.1. Представление о категориальной абстрактной машине (КАМ). Вычисление значения в д.з.к.
6.2. Оценивающее отображение. Среда. Примеры вычисления значения выражений.
6.3. Коллизии переменных. Устранение коллизий. Кодирование по Дебрейну. Числа Дебрейна.
6.4. Вычисление значения в д.з.к. с учетом кодирования по Дебрейну.
6.5. Комбинаторный “клей”.
6.6. Формулировки теорий вычисления и обоснование их свойств.

7. Значение выражений: теория вычислений в категории
7.1. Значение выражений и техника вычисления значений.
7.2. Среда вычисления значений и ее представление.
7.3. Теория вычисления значений по Дебрейну.
7.4. Синтаксическая теория вычислений.
7.5. Различные формы вычисления значения выражений.

8. Значение выражений: способы вычисления в категории
8.1. Способы вычислений.
8.2. Исполнение скомпилированного кода.
8.3. Применение сборки кода.
8.4. Сравнение способов вычислений.

9. Конструирование в категории абстрактной машины (АМ).
9.1. Представление о конструировании абстрактной машины.
9.2. Работа абстрактной машины. Состояния.
9.3. Цикл работы абстрактной машины.
9.4. Примеры вычислений. Компилирование кода и его исполнение.

10. Цикл работы абстрактной машины.
10.1. Описание всевозможных переходов состояний.
10.2. Пример вычисление значения 2-местного предиката.
10.2.1. Компилирование кода.
102.2. Исполнение кода.

11. Оптимизация вычислений в категории.
11.1. Вычисление на абстрактной машине свертывания по постулату (β).
11.2. Компилирование кода и его эквивалентные преобразования
11.3. Экономии кодирования и обоснование вычисления β-свертывания.
11.4. Принцип оптимизации (Beta) и его вывод.
11.5. Оптимизация и экономия на примере вычисления значения 2-местного оператора.

12. Расширение и реализация абстрактной машины.
12.1. Неподвижная точка в вычислениях и инструкция ветвления.
12.2. Кодогенерация для выражения с неподвижной точкой.
12.3. Рекурсивная модификация среды (р.м.с.).
12.4. Пример вычисления с р.м.с.
12.5. Большой пример. Выполнение кодогенерации с оптимизацией.

13. Исполнение кода с рекурсивной модификацией среды на абстрактной машине.
13.1. Большой пример. Вспомогательные обозначения для упрощения кода.
13.2. Большой пример. Исполнение кода с р.м.с.
13.3. Анализ цикличности в вычислениях. Параметры цикла.

Вверх

     

Дискретная математика: учебный курс, Дискретная математика: что читать, Логика: программа, Логика: студенты