SEWiki - Вклад участника [ru]

Обобщенное и генеративное программирование

2012-12-28T19:23:35Z

Zalim: /* Презентации, использованные на лекциях */

Лектор - Власьев Михаил Игоревич 
mailto:michael.vlassiev@jetbrains.com

== Презентации, использованные на лекциях ==
[[Медиа:GenProg_1.pdf | Вводная лекция]] 
[[Медиа:Introduction_to_MPS.pdf | Введение в МПС]] ([https://docs.google.com/open?id=0B3pvyfja13p5S29iWVdYd1NZcTQ проект с примером]) 
[[Медиа:GenProg_2.pdf | Лекции]] 

[http://dl.dropbox.com/u/9957315/jetbrains.mps.demo.lazytype.zip Обновленный проект с примером]

== Задания для получения зачета (на выбор) ==

1. Калькулятор. 
Придумать и реализовать язык на котором можно было бы описывать требования к калькулятору (набор действий, расположенных на кнопках). По описанию калькулятора должна генерироваться программа на Java, реализующая этот калькулятор.

2. Конечный автомат. 
Язык описания и реализация на MPS.

3. Трассировка. 
Придумать и реализовать аспект для baseLanguage языка в MPS, управляющий трассировкой выполнения (logging). Небоходимо предусмотреть возможность включать трассировку вызовов методов, обращений к полям.

== Список литературы ==
Generative Programming: Methods, Tools, and Applications 
Krysztof Czarnecki, Ulrich Eisenecker 
Addison-Wesley Professional; 1 edition (June 16, 2000) 
Перевод: Чернецки К., Айзенекер У. Порождающее программирование: методы, инструменты, применение / Пер. с англ. СПб: Питер, 2005.

Domain-Specific Languages 
Martin Fowler 
Addison-Wesley; 2011 

== Полезные ссылки ==
JetBrains MPS: http://www.jetbrains.com/mps 
Загрузка: http://www.jetbrains.com/mps/download/index.html 
Руководство: http://confluence.jetbrains.net/display/MPSD25/MPS+User's+Guide 
Отчеты об ошибках писать сюда: http://youtrack.jetbrains.com/issues/MPS

WhereIsMyMoney

2012-11-15T21:21:02Z

Zalim: /* Where is My Builds */

== Состав команды (а. 432) ==

# Залим Башоров
# Фофанова Мария
# Коровин Алексей
# Опейкин Александр
# Кринкин Михаил

== Репозиторий ==

https://github.com/Temp1ar/WhereIsMyMoney

== Where is My Builds ==
https://play.google.com/store/apps/details?id=ru.spbau.WhereIsMyMoney

https://github.com/Temp1ar/WhereIsMyMoney/wiki

== Описание ==

Пишем приложение под Android, которое парсит СМСки от банка, и на основе полученных данных говорит пользователю что-нибудь полезное.

Фичи:

# Предустановленные фильтры для известных банков
# Возможность создавать свои фильтры
# История транзакций по карте
# Визуализация (опциональная фича, построение всяких разных графиков баланса)

WhereIsMyMoney

2012-11-14T12:36:38Z

Zalim:

== Состав команды (а. 432) ==

# Залим Башоров
# Фофанова Мария
# Коровин Алексей
# Опейкин Александр
# Кринкин Михаил

== Репозиторий ==

https://github.com/Temp1ar/WhereIsMyMoney

== Where is My Builds ==
https://github.com/Temp1ar/WhereIsMyMoney/wiki

== Описание ==

Пишем приложение под Android, которое парсит СМСки от банка, и на основе полученных данных говорит пользователю что-нибудь полезное.

Фичи:

# Предустановленные фильтры для известных банков
# Возможность создавать свои фильтры
# История транзакций по карте
# Визуализация (опциональная фича, построение всяких разных графиков баланса)

Devdays2h2012

2012-11-14T12:33:56Z

Zalim: /* Страницы проектов */

== Страницы проектов ==

* [[Shepherd_Game| Игра "В погоне за овцой" под Android]]
* [[Project_Grothendieck|Project Grothendieck (Визуализатор алгебраических структур)]]
* [[MorseKeyboard|Клавиатура Морзе]]
* [[Cheque recognizer 2.0|Распознавание чеков]]
* [[DontMissStop|Будильник "Не проспи остановку"]]
* [[Машина_Тьюринга|Машина Тьюринга]]
* [[SynchronizedPlayer]]
* [[Билетоловилка]]
* [[ScaLaTeX| ScaLaTeX]]
* [[WhereIsMyMoney|Where is My Money]]
* [[GooglePlay client for PC]]
* [[Hear me please]]

== Разное ==

* [[audd12_ideas| Идеи проектов]]
* [[audday1_initial|Доска с начала мероприятия]]
* [[audday2_promises_and_status| Состояние проектов на 13.11.2012 утро]]
* [[audday2_reality| Состояние проектов на 13.11.2012 вечер]]
* [[audday3_morning| Состояние проектов на 14.11.2012 утро]]

WhereIsMyMoney

2012-11-12T08:43:51Z

Zalim: /* Репозиторий */

== Состав команды (а. 432) ==

# Залим Башоров
# Фофанова Мария
# Коровин Алексей
# Опейкин Александр
# Кринкин Михаил

== Репозиторий ==

https://github.com/Temp1ar/WhereIsMyMoney

== Описание ==

Пишем приложение под Android, которое парсит СМСки от банка, и на основе полученных данных говорит пользователю что-нибудь полезное.

Фичи:

# Предустановленные фильтры для известных банков
# Возможность создавать свои фильтры
# Ручное добавление транзакций
# История транзакций по карте
# Визуализация (опциональная фича, построение всяких разных графиков баланса)

Формальные языки 2012

2012-11-08T17:36:09Z

Zalim:

Лектор - Булычев Д.Ю.

== Лекции ==

== Домашние задания ==

== Список литературы ==

== Полезные ссылки ==

Сетевые технологии

2012-10-26T18:32:25Z

Zalim: /* Домашние задания */

Лектор - Кузнецов Антон Михайлович

== Лекции ==
[http://mit.spbau.ru/sewiki/images/0/07/Network_Sockets_20110930.pdf Презентация по сокетам]

== Домашние задания ==
# Есть два IP адреса и маска. Написать программу, которая отвечает на вопрос: лежат ли эти IP адреса в одной подсети
# Разобраться с tcpdump (написать команду и вывод команды в письме)
## Увидеть как пингуют мой компьютер
## Разобраться с ICMP type 3 запросами:
### Что приходит при отправке пакета на несуществующий узел
### Что приходит при отправке пакета и обрыве сети
### Что приходит при отправке пакета и кончается TTL
# Д/З к 19.10.12
## Посмотреть route, iptables
## Раньше А и Б выходили в инет через одну точку.
### Сделать так чтобы А выходил в инет через Б
### Теперь настроить на Б SNAT и показать, что при обращении к какому то урлу source подменяется
## Написать проверялку endian на компе (Big | Little - endian)
## Hello-Server Передаем: <имя> <время отправки> в ответ возвращается: Hello, <имя> <время отправики с сервера>
### Продемонстрировать, что ответ может прийти не сразу (много клиентов)
### tcp
### udp
### Сравнить количество обслуженных клиентов
# Chat (сервер, клиент) -- [http://mit.spbau.ru/sewiki/images/1/11/Network2012_chat_task_board.jpg фото доски]

== Список литературы ==

== Полезные ссылки ==

Файл:Network2012 chat task board.jpg

2012-10-26T18:29:01Z

Zalim:

Разработка интерактивных интерфейсов 2012

2012-10-22T19:34:01Z

Zalim: /* Проекты */

Лектор - Кринкин Кирилл Владимирович

== Проекты ==
1. Кринкин М., Башоров З. 
[https://github.com/bashor/RemoteControl Remote Control]

2. Кононенко, Сорокин, Казенюк

3. Опейкин, Коровин

4. Шеставин, Певзнер

5. Савельев, Фофанова

6. Краско, Иванов

7. Лазарев

8. Великий

== Лекции ==

== Домашние задания ==

== Список литературы ==

== Полезные ссылки ==

Сетевые технологии

2012-10-18T18:21:33Z

Zalim: /* Домашние задания */

Лектор - Кузнецов Антон Михайлович

== Лекции ==
[http://mit.spbau.ru/sewiki/images/0/07/Network_Sockets_20110930.pdf Презентация по сокетам]

== Домашние задания ==
# Есть два IP адреса и маска. Написать программу, которая отвечает на вопрос: лежат ли эти IP адреса в одной подсети
# Разобраться с tcpdump (написать команду и вывод команды в письме)
## Увидеть как пингуют мой компьютер
## Разобраться с ICMP type 3 запросами:
### Что приходит при отправке пакета на несуществующий узел
### Что приходит при отправке пакета и обрыве сети
### Что приходит при отправке пакета и кончается TTL
# Д/З к 19.10.12
## Посмотреть route, iptables
## Раньше А и Б выходили в инет через одну точку.
### Сделать так чтобы А выходил в инет через Б
### Теперь настроить на Б SNAT и показать, что при обращении к какому то урлу source подменяется
## Написать проверялку endian на компе (Big | Little - endian)
## Hello-Server Передаем: <имя> <время отправки> в ответ возвращается: Hello, <имя> <время отправики с сервера>
### Продемонстрировать, что ответ может прийти не сразу (много клиентов)
### tcp
### udp
### Сравнить количество обслуженных клиентов

В следующий раз к/р (19.10.12).

== Список литературы ==

== Полезные ссылки ==

Компьютерная графика 2012

2012-10-07T20:41:45Z

Zalim:

Лекторы - Алексей Романов и Евгений Жидков

[https://sites.google.com/site/cgcourseau2012autumn/ страница курса]

== Лекции ==

== Домашние задания ==

== Список литературы ==

== Полезные ссылки ==

UML 2012

2012-10-07T20:38:00Z

Zalim:

Лектор - Новиков А.

*[http://uml3.ru http://uml3.ru]
*[http://blog.modelware.ru/ http://blog.modelware.ru/]

SE Wiki

2012-10-02T19:55:56Z

Zalim: Добавил ссылки на расписание

== Учебная информация ==
[http://mit.spbau.ru/ru/scheduleSE Расписание]

5 курс:
* [[Базы_данных_2012|Базы данных]]
* [[Алгебраические_структуры_2012|Алгебраические структуры]]
* [[Алгоритмы_и_структуры_данных_2012|Алгоритмы и структуры данных]]
* [[Операционные_системы_2012|Операционные системы]]
* [[Основы_программной_инженерии_2012|Основы программной инженерии]]
* [[Теория_графов_2012|Теория графов]]
* [[Комбинаторика_2012|Комбинаторика]]
* [[Мат_логика_2012|Мат. логика]]
* [[Unix_и_Скриптовые_языки_2012|Unix и скриптовые языки]]
* [[C___2012|С++]]
* [[Технологический_семинар_2012|Технологический семинар]]
* [[НИР_2012|НИР]]

6 курс: 
[http://www.google.com/calendar/embed?mode=WEEK&src=9f7hm9olebmkjnkglq6ussvd7s%40group.calendar.google.com&color=%23060D5E&src=e0hc0uakdjbknh05tcr5fomct8%40group.calendar.google.com&color=%232F6309&src=notnpt47cf0g3cufakpqpcecp5nt1505%40import.calendar.google.com&color=%235A6986&ctz=Europe%2FMoscow Расписание в гугл календаре (html)] [http://www.google.com/calendar/ical/9f7hm9olebmkjnkglq6ussvd7s%40group.calendar.google.com/public/basic.ics (ical)]
 
* [[Виртуальные_машины_2012|Виртуальные машины]]
* [[Машинное_обучение_2012|Машинное обучение]]
* [[UML_2012|UML]]
* [[Компьютерная_графика_2012|Компьютерная графика]]
* [[Параллельные_и_распределенные_вычисления_2012|Параллельные и распределенные вычисления]]
* [[Программирование_в_ядре_Windows_2012|Программирование в ядре Windows]]
* [[Тестирование_ПО_2012|Тестирование ПО]]
* [[Анализ_данных_2012| Анализ данных]]
* [[Формальные_языки_2012|Формальные языки]]
* [[Методы_формальной_верификации_программ_2012|Методы формальной верификации программ]]
* [[Разработка_интерактивных_интерфейсов_2012|Разработка интерактивных интерфейсов]]
* [[SCALA_2012|Scala]]
* [[Сетевые технологии]]
* [[Обобщенное и генеративное программирование]]

== Архив за прошлые семестры ==
* [[Весна_2012|Весенний семестр 2012]]
* [[Осень_2011|Осенний семестр 2011]]

== Практики ==
* [[НИР 5SE осень 2012|Темы практик, осень 2012-го года]]
* [https://docs.google.com/spreadsheet/pub?key=0Aif17q2hwUt4dG9CRFdGa2tLeV9ab1l1QWlkOFp3bFE&output=html Темы практик, лето 2012-го года]
* [[Темы практик, 5SE, осень 2011-го года | Темы практик, осень 2011-го года]]
* [[Темы практик |Темы практик, весна 2011-го года]]

== Студенты ==
* [[2010|Набор 2010-го года]]
* [[2011|Набор 2011-го года]]
* [[2012|Набор 2012-го года]]

== Важные ссылки ==
Для 5-го курса:
* [http://code.google.com/p/spbau-cpp-2011/ cpp] - репозиторий для лабораторных по С++.
* [http://code.google.com/p/aptu-os/source/checkout aptu-os] - репозиторий для лабораторных по операционным системам.

Для 6-го курса:
* [http://code.google.com/p/hpcource/ hpcource] - репозиторий для лабораторных по параллельному программированию.
* [http://code.google.com/p/mathvm/ mathvm] - репозиторий для лабораторных по виртуальным машинам.
* [http://code.google.com/p/spbau-network-2011/source/checkout spbau-network-2011] - репозиторий для лабораторных по сетевым технологиям.

== Дополнительно ==
* [[Q&A]]
* [[Мероприятия]]

SCALA 2012

2012-10-02T17:19:07Z

Zalim:

Лектор - Подхалюзин А., Исакова С.

* [https:/docs.google.com/spreadsheet/ccc?key=0Am1c1yb3OpowdE1Eb3RNUHZNM3h3YzBqNHAxMnRCRlE&pli=1#gid=0| Результаты домашних и контрольных работ]

== Лекции ==
* [https://github.com/Alefas/game-task/blob/master/presentation.pdf?raw=true 01 (pdf)]
* [https://github.com/svtk/lecture2 02 (src)]
* [https://github.com/Alefas/complex-task/blob/master/presentation.pdf?raw=true 03 (pdf]
* [https://github.com/svtk/lecture4 04 (src)]
== Домашние задания ==
# [https://github.com/Alefas/game-task Four Score]
# [https://github.com/Alefas/complex-task Сase class Complex]
# [https://github.com/svtk/lecture4/blob/master/README.md Implement normalization of a lambda term]

== Список литературы ==

== Полезные ссылки ==

Виртуальные машины 2012

2012-10-02T17:02:01Z

Zalim:

Лектор - Иготти Н. А.

[http://code.google.com/p/mathvm репозиторий]

== Домашние задания ==
# Конвертер AST-дерева в код

Виртуальные машины 2012

2012-10-02T16:53:53Z

Zalim: /* Домашние задания */

Лектор - Иготти Н. А.

== Лекции ==

== Домашние задания ==
[http://code.google.com/p/mathvm/ wiki && code]

== Список литературы ==

== Полезные ссылки ==

Программирование в ядре Windows 2012

2012-09-14T20:43:55Z

Zalim: Добавление ссылки на первое Д/З

Лектор - Кринкин Кирилл Владимирович

== Лекции ==

== Домашние задания ==
#[http://code.google.com/p/windows-kernel-course/wiki/PR_ProcessExplorer Написать консольный ProcessViewer]

== Список литературы ==

== Полезные ссылки ==
*[http://code.google.com/p/windows-kernel-course Проект на googlecode]
*[http://groups.google.com/group/nt-kernel-course Рассылка для обсуждений]

Программирование в ядре Windows 2012

2012-09-14T20:42:11Z

Zalim: Добавление ресурсов

Лектор - Кринкин Кирилл Владимирович

== Лекции ==

== Домашние задания ==

== Список литературы ==

== Полезные ссылки ==
*[http://code.google.com/p/windows-kernel-course Проект на googlecode]
*[http://groups.google.com/group/nt-kernel-course Рассылка для обсуждений]

SE Wiki

2012-09-14T20:37:19Z

Zalim: /* Учебная информация */

== Учебная информация ==
5 курс:
* [[Базы_данных_2012|Базы данных]]
* [[Алгебраические_структуры_2012|Алгебраические структуры]]
* [[Алгоритмы_и_структуры_данных_2012|Алгоритмы и структуры данных]]
* [[Операционные_системы_2012|Операционные системы]]
* [[Основы_программной_инженерии_2012|Основы программной инженерии]]
* [[Теория_графов_2012|Теория графов]]
* [[Комбинаторика_2012|Комбинаторика]]
* [[Мат_логика_2012|Мат. логика]]
* [[Unix_и_Скриптовые_языки_2012|Unix и скриптовые языки]]
* [[C___2012|С++]]
* [[Технологический_семинар_2012|Технологический семинар]]
* [[НИР_2012|НИР]]

6 курс:
* [[Виртуальные_машины_2012|Виртуальные машины]]
* [[Машинное_обучение_2012|Машинное обучение]]
* [[UML_2012|UML]]
* [[Компьютерная_графика_2012|Компьютерная графика]]
* [[Параллельные_и_распределенные_вычисления_2012|Параллельные и распределенные вычисления]]
* [[Программирование_в_ядре_Windows_2012|Программирование в ядре Windows]]
* [[Тестирование_ПО_2012|Тестирование ПО]]
* [[Анализ_данных_2012| Анализ данных]]
* [[Формальные_языки_2012|Формальные языки]]
* [[Методы_формальной_верификации_программ_2012|Методы формальной верификации программ]]
* [[Разработка_интерактивных_интерфейсов_2012|Разработка интерактивных интерфейсов]]
* [[SCALA_2012|Scala]]
* [[Сетевые технологии]]
* [[Обобщенное и генеративное программирование]]

== Архив за прошлые семестры ==
* [[Весна_2012|Весенний семестр 2012]]
* [[Осень_2011|Осенний семестр 2011]]

== Практики ==
* [https://docs.google.com/spreadsheet/pub?key=0Aif17q2hwUt4dG9CRFdGa2tLeV9ab1l1QWlkOFp3bFE&output=html Темы практик, лето 2012-го года]
* [[Темы практик, 5SE, осень 2011-го года | Темы практик, осень 2011-го года]]
* [[Темы практик |Темы практик, весна 2011-го года]]

== Студенты ==
* [[2010|Набор 2010-го года]]
* [[2011|Набор 2011-го года]]
* [[2012|Набор 2012-го года]]

== Важные ссылки ==
Для 5-го курса:
* [http://code.google.com/p/spbau-cpp-2011/ cpp] - репозиторий для лабораторных по С++.
* [http://code.google.com/p/aptu-os/source/checkout aptu-os] - репозиторий для лабораторных по операционным системам.

Для 6-го курса:
* [http://code.google.com/p/hpcource/ hpcource] - репозиторий для лабораторных по параллельному программированию.
* [http://code.google.com/p/mathvm/ mathvm] - репозиторий для лабораторных по виртуальным машинам.
* [http://code.google.com/p/spbau-network-2011/source/checkout spbau-network-2011] - репозиторий для лабораторных по сетевым технологиям.

== Дополнительно ==
* [[Q&A]]
* [[Мероприятия]]

SE Wiki

2012-09-13T15:14:22Z

Zalim: /* Учебная информация */

== Учебная информация ==
5 курс:
* [[Unix_и_Скриптовые_языки_2012|Unix и скриптовые языки]]

6 курс:
* [[Методы_формальной_верификации_программ_2012|Методы формальной верификации программ]]

== Архив за прошлые семестры ==
* [[Весна_2012|Весенний семестр 2012]]
* [[Осень_2011|Осенний семестр 2011]]

== Практики ==
* [https://docs.google.com/spreadsheet/pub?key=0Aif17q2hwUt4dG9CRFdGa2tLeV9ab1l1QWlkOFp3bFE&output=html Темы практик, лето 2012-го года]
* [[Темы практик, 5SE, осень 2011-го года | Темы практик, осень 2011-го года]]
* [[Темы практик |Темы практик, весна 2011-го года]]

== Студенты ==
* [[2010|Набор 2010-го года]]
* [[2011|Набор 2011-го года]]
* [[2012|Набор 2012-го года]]

== Важные ссылки ==
Для 5-го курса:
* [http://code.google.com/p/spbau-cpp-2011/ cpp] - репозиторий для лабораторных по С++.
* [http://code.google.com/p/aptu-os/source/checkout aptu-os] - репозиторий для лабораторных по операционным системам.

Для 6-го курса:
* [http://code.google.com/p/hpcource/ hpcource] - репозиторий для лабораторных по параллельному программированию.
* [http://code.google.com/p/mathvm/ mathvm] - репозиторий для лабораторных по виртуальным машинам.
* [http://code.google.com/p/spbau-network-2011/source/checkout spbau-network-2011] - репозиторий для лабораторных по сетевым технологиям.

== Дополнительно ==
* [[Q&A]]
* [[Мероприятия]]

SE Wiki

2012-09-12T15:43:46Z

Zalim: /* Важные ссылки */

== Учебная информация ==

[[Unix_и_Скриптовые_языки_2012|Unix и скриптовые языки]]

== Архив за прошлые семестры ==
* [[Весна_2012|Весенний семестр 2012]]
* [[Осень_2011|Осенний семестр 2011]]

== Практики ==
* [https://docs.google.com/spreadsheet/pub?key=0Aif17q2hwUt4dG9CRFdGa2tLeV9ab1l1QWlkOFp3bFE&output=html Темы практик, лето 2012-го года]
* [[Темы практик, 5SE, осень 2011-го года | Темы практик, осень 2011-го года]]
* [[Темы практик |Темы практик, весна 2011-го года]]

== Студенты ==
* [[2010|Набор 2010-го года]]
* [[2011|Набор 2011-го года]]
* [[2012|Набор 2012-го года]]

== Важные ссылки ==
Для 5-го курса:
* [http://code.google.com/p/spbau-cpp-2011/ cpp] - репозиторий для лабораторных по С++.
* [http://code.google.com/p/aptu-os/source/checkout aptu-os] - репозиторий для лабораторных по операционным системам.

Для 6-го курса:
* [http://code.google.com/p/hpcource/ hpcource] - репозиторий для лабораторных по параллельному программированию.
* [http://code.google.com/p/mathvm/ mathvm] - репозиторий для лабораторных по виртуальным машинам.
* [http://code.google.com/p/spbau-network-2011/source/checkout spbau-network-2011] - репозиторий для лабораторных по сетевым технологиям.

== Дополнительно ==
* [[Q&A]]
* [[Мероприятия]]

Приведение типов. RTTI

2012-06-11T07:33:55Z

Zalim: /* dynamic_cast */

==Приведение типов==
Приведение типов делится на C style cast и C++ style cast
===Приведение в стиле C===
Синтаксис приведения:
* (тип_к_которому_приводим) переменная
* тип_к_которому_приводим (переменная)

Примеры:
<source lang="cpp">
int i = 10;
double d = (double) i;
float f = float(i);
char const* ch = "hello";
string str = (string) ch;
</source>

===Приведение в стиле С++===
В С++ для приведения типов используются следующие функции:
* const_cast
* reinterpret_cast
* static_cast
* dynamic_cast
Во всех случаях синтаксис приведения будет выглядеть следующим образом:
..._cast <тип_к_которому_приводим> (переменная)

Рассмотрим первые три более подробно (dynamic_cast рассматривается в разделе RTTI).
====const_cast====
Добавляет/убирает у объекта квалификаторы const и volatile. Если убрать константность у объекта, который был объявлен как константный, то при записи может возникнуть undefined behavior (в зависимости от типа объекта).

Рассмотрим ситуацию, когда нам может пригодиться const_cast.
Предположим у нас класс A, в котором хранятся элементы типа Т. Пусть требуется реализовать метод get (константный и не константный), который по индексу i будет возвращать i-ый элемент. Можно описать реализацию только одного метода (константного), а второй реализовать через вызов первого при помощи const_cast:
<source lang="cpp">
T const& get (int i) const;
T& get (int i) {
return const_cast<T&> (const_cast<A const*> (this).get(i) );
}
</source>
====reinterpret_cast====
Приводит любой указатель к любому указателю.

Пример:
<source lang="cpp">
struct Point3 {
double x;
double y;
double z;
};
...
Point3* p = ...;
double* p_x = reinterpret_cast<double*> (p);
</source>
Замечание: приведенный пример отработает корректно в случае если структура Point3 плотно упакована в памяти (см. опции компилятора).
====static_cast====
Используется для приведения
* числовых типов (аналогично C-style cast)
* указателей и ссылок для классов связанных наследованием
* пользовательских преобразований
Преобразование выполняется в момент компиляции и run-time проверки (как это есть в dynamic_cast) приведения типов нет, поэтому сложные приведения типов следует делать очень аккуратно.

Пример:
<source lang="cpp">
struct A {};
struct B : A {};
...
B* b;
A* a = static_cast<A*> (b);
b = static_cast<B*> (a);
</source>

Замечание: static_cast меняет указатель в зависимости от того какое у классов наследование (в отличии от reinterpret_cast), поэтому если будет forward declaration, то static_cast выдаст ошибку (на этапе компиляции):
<source lang="cpp">
struct A;
struct B;
B* b;
A* a = static_cast<A*>(b); // ошибка!
</source>

===Общее замечание по разделу Приведение типов===
При программировании на С++ рекомендуется использовать только C++-style cast (а еще лучше -- не пользоваться приведением типов) 
<s>При программировании на С++ рекомендуется использовать C-style cast только в случаях приведения элементарных типов друг к другу.</s>

==RTTI==
RTTI расшифровывается как Run-time type information. Это механизм, позволяющий определять тип объекта в момент выполнения программы. В С++ данный механизм реализуется при помощи следующих элементов:
* оператор dynamic_cast (используется для преобразования полиморфных типов)
* оператор typeid (для точного определения типа объекта)
* класс type_info (для хранения информации, возвращаемой оператором typeid)

Рассмотрим применение и синтаксис typeid и type_info на примере:
<source lang="cpp">
#include <typeinfo>
...
A* a;
type_info& ti = typeid(a);
std::cout << ti.name() << std::endl;
</source>
Более сложный пример:

<source lang="cpp">
#include <typeinfo>
struct A {};
struct B : A {};
...
A* a = new B();
typeid(a); // A*
typeid(*a); // B
</source>

У класса type_info помимо метода name (возвращающего строку - char*, характеризующую тип объекта) и операторов равенства/неравенства есть еще метод before, который позволяет упорядочивать экземпляры type_info и хранить их, например, в map.

===dynamic_cast===
Позволяет приводить указатель или объект одного типа к указателю или ссылке на другой класс (связанный с первым через наследование).
В отличии от static_cast выполняется в run-time.
При ошибке приведения к указателю на тип dynamic_cast возвращает нулевой указатель, при ошибке приведения к ссылке на тип выбрасывается исключение bad_cast.

Пример использования:
<source lang="cpp">
struct A {
virtual void f() {}
};
struct B : A {
virtual void f() {}
};

...
A* pa = new B;
A* pa2 = new A;

B* pb = dynamic_cast<B*>(pa); // pb указывает на B
B* pb2 = dynamic_cast<B*>(pa2); // pb2 указывает на А, а не на В! pb2 == NULL

pb->f();
pb2->f(); // ошибка на этапе исполнения! pb2 == NULL
</source>

Замечание: При приведении к указателю на void возвращается указатель на начало блока.

=== Общие замечания по разделу RTTI ===
* почти всегда можно обойтись без RTTI и чаще всего использование этого механизма говорит об ошибке проектирования
* на этапе отладки применение RTTI бывает полезно.

Приведение типов. RTTI

2012-06-11T07:28:33Z

Zalim: /* Общее замечание по разделу Приведение типов */

==Приведение типов==
Приведение типов делится на C style cast и C++ style cast
===Приведение в стиле C===
Синтаксис приведения:
* (тип_к_которому_приводим) переменная
* тип_к_которому_приводим (переменная)

Примеры:
<source lang="cpp">
int i = 10;
double d = (double) i;
float f = float(i);
char const* ch = "hello";
string str = (string) ch;
</source>

===Приведение в стиле С++===
В С++ для приведения типов используются следующие функции:
* const_cast
* reinterpret_cast
* static_cast
* dynamic_cast
Во всех случаях синтаксис приведения будет выглядеть следующим образом:
..._cast <тип_к_которому_приводим> (переменная)

Рассмотрим первые три более подробно (dynamic_cast рассматривается в разделе RTTI).
====const_cast====
Добавляет/убирает у объекта квалификаторы const и volatile. Если убрать константность у объекта, который был объявлен как константный, то при записи может возникнуть undefined behavior (в зависимости от типа объекта).

Рассмотрим ситуацию, когда нам может пригодиться const_cast.
Предположим у нас класс A, в котором хранятся элементы типа Т. Пусть требуется реализовать метод get (константный и не константный), который по индексу i будет возвращать i-ый элемент. Можно описать реализацию только одного метода (константного), а второй реализовать через вызов первого при помощи const_cast:
<source lang="cpp">
T const& get (int i) const;
T& get (int i) {
return const_cast<T&> (const_cast<A const*> (this).get(i) );
}
</source>
====reinterpret_cast====
Приводит любой указатель к любому указателю.

Пример:
<source lang="cpp">
struct Point3 {
double x;
double y;
double z;
};
...
Point3* p = ...;
double* p_x = reinterpret_cast<double*> (p);
</source>
Замечание: приведенный пример отработает корректно в случае если структура Point3 плотно упакована в памяти (см. опции компилятора).
====static_cast====
Используется для приведения
* числовых типов (аналогично C-style cast)
* указателей и ссылок для классов связанных наследованием
* пользовательских преобразований
Преобразование выполняется в момент компиляции и run-time проверки (как это есть в dynamic_cast) приведения типов нет, поэтому сложные приведения типов следует делать очень аккуратно.

Пример:
<source lang="cpp">
struct A {};
struct B : A {};
...
B* b;
A* a = static_cast<A*> (b);
b = static_cast<B*> (a);
</source>

Замечание: static_cast меняет указатель в зависимости от того какое у классов наследование (в отличии от reinterpret_cast), поэтому если будет forward declaration, то static_cast выдаст ошибку (на этапе компиляции):
<source lang="cpp">
struct A;
struct B;
B* b;
A* a = static_cast<A*>(b); // ошибка!
</source>

===Общее замечание по разделу Приведение типов===
При программировании на С++ рекомендуется использовать только C++-style cast (а еще лучше -- не пользоваться приведением типов) 
<s>При программировании на С++ рекомендуется использовать C-style cast только в случаях приведения элементарных типов друг к другу.</s>

==RTTI==
RTTI расшифровывается как Run-time type information. Это механизм, позволяющий определять тип объекта в момент выполнения программы. В С++ данный механизм реализуется при помощи следующих элементов:
* оператор dynamic_cast (используется для преобразования полиморфных типов)
* оператор typeid (для точного определения типа объекта)
* класс type_info (для хранения информации, возвращаемой оператором typeid)

Рассмотрим применение и синтаксис typeid и type_info на примере:
<source lang="cpp">
#include <typeinfo>
...
A* a;
type_info& ti = typeid(a);
std::cout << ti.name() << std::endl;
</source>
Более сложный пример:

<source lang="cpp">
#include <typeinfo>
struct A {};
struct B : A {};
...
A* a = new B();
typeid(a); // A*
typeid(*a); // B
</source>

У класса type_info помимо метода name (возвращающего строку - char*, характеризующую тип объекта) и операторов равенства/неравенства есть еще метод before, который позволяет упорядочивать экземпляры type_info и хранить их, например, в map.

===dynamic_cast===
Позволяет приводить указатель или объект одного типа к указателю или ссылке на другой класс (связанный с первым через наследование).
В отличии от static_cast выполняется в run-time.
При ошибке приведения к указателю на тип dynamic_cast возвращает нулевой указатель, при ошибке приведения к ссылке на тип выбрасывается исключение bad_cast.

Пример использования:
<source lang="cpp">
struct A {
virtual void f() {}
};
struct B : A {
virtual void f() {}
};

...
A* pa = new B;
A* pa2 = new A;

B* pb = dynamic_cast<B*>(pa); // pb указывает на B
B* pb2 = dynamic_cast<B*>(pa2); // pb2 указывает на А, а не на В!

pb->f();
pb2->f(); // ошибка на этапе исполнения!
</source>

Замечание: При приведении к указателю на void возвращается указатель на начало блока.

=== Общие замечания по разделу RTTI ===
* почти всегда можно обойтись без RTTI и чаще всего использование этого механизма говорит об ошибке проектирования
* на этапе отладки применение RTTI бывает полезно.

Приведение типов. RTTI

2012-06-11T07:00:03Z

Zalim:

==Приведение типов==
Приведение типов делится на C style cast и C++ style cast
===Приведение в стиле C===
Синтаксис приведения:
* (тип_к_которому_приводим) переменная
* тип_к_которому_приводим (переменная)

Примеры:
<source lang="cpp">
int i = 10;
double d = (double) i;
float f = float(i);
char const* ch = "hello";
string str = (string) ch;
</source>

===Приведение в стиле С++===
В С++ для приведения типов используются следующие функции:
* const_cast
* reinterpret_cast
* static_cast
* dynamic_cast
Во всех случаях синтаксис приведения будет выглядеть следующим образом:
..._cast <тип_к_которому_приводим> (переменная)

Рассмотрим первые три более подробно (dynamic_cast рассматривается в разделе RTTI).
====const_cast====
Добавляет/убирает у объекта квалификаторы const и volatile. Если убрать константность у объекта, который был объявлен как константный, то при записи может возникнуть undefined behavior (в зависимости от типа объекта).

Рассмотрим ситуацию, когда нам может пригодиться const_cast.
Предположим у нас класс A, в котором хранятся элементы типа Т. Пусть требуется реализовать метод get (константный и не константный), который по индексу i будет возвращать i-ый элемент. Можно описать реализацию только одного метода (константного), а второй реализовать через вызов первого при помощи const_cast:
<source lang="cpp">
T const& get (int i) const;
T& get (int i) {
return const_cast<T&> (const_cast<A const*> (this).get(i) );
}
</source>
====reinterpret_cast====
Приводит любой указатель к любому указателю.

Пример:
<source lang="cpp">
struct Point3 {
double x;
double y;
double z;
};
...
Point3* p = ...;
double* p_x = reinterpret_cast<double*> (p);
</source>
Замечание: приведенный пример отработает корректно в случае если структура Point3 плотно упакована в памяти (см. опции компилятора).
====static_cast====
Используется для приведения
* числовых типов (аналогично C-style cast)
* указателей и ссылок для классов связанных наследованием
* пользовательских преобразований
Преобразование выполняется в момент компиляции и run-time проверки (как это есть в dynamic_cast) приведения типов нет, поэтому сложные приведения типов следует делать очень аккуратно.

Пример:
<source lang="cpp">
struct A {};
struct B : A {};
...
B* b;
A* a = static_cast<A*> (b);
b = static_cast<B*> (a);
</source>

Замечание: static_cast меняет указатель в зависимости от того какое у классов наследование (в отличии от reinterpret_cast), поэтому если будет forward declaration, то static_cast выдаст ошибку (на этапе компиляции):
<source lang="cpp">
struct A;
struct B;
B* b;
A* a = static_cast<A*>(b); // ошибка!
</source>

===Общее замечание по разделу Приведение типов===
При программировании на С++ рекомендуется использовать C-style cast только в случаях приведения элементарных типов друг к другу.

==RTTI==
RTTI расшифровывается как Run-time type information. Это механизм, позволяющий определять тип объекта в момент выполнения программы. В С++ данный механизм реализуется при помощи следующих элементов:
* оператор dynamic_cast (используется для преобразования полиморфных типов)
* оператор typeid (для точного определения типа объекта)
* класс type_info (для хранения информации, возвращаемой оператором typeid)

Рассмотрим применение и синтаксис typeid и type_info на примере:
<source lang="cpp">
#include <typeinfo>
...
A* a;
type_info& ti = typeid(a);
std::cout << ti.name() << std::endl;
</source>
Более сложный пример:

<source lang="cpp">
#include <typeinfo>
struct A {};
struct B : A {};
...
A* a = new B();
typeid(a); // A*
typeid(*a); // B
</source>

У класса type_info помимо метода name (возвращающего строку - char*, характеризующую тип объекта) и операторов равенства/неравенства есть еще метод before, который позволяет упорядочивать экземпляры type_info и хранить их, например, в map.

===dynamic_cast===
Позволяет приводить указатель или объект одного типа к указателю или ссылке на другой класс (связанный с первым через наследование).
В отличии от static_cast выполняется в run-time.
При ошибке приведения к указателю на тип dynamic_cast возвращает нулевой указатель, при ошибке приведения к ссылке на тип выбрасывается исключение bad_cast.

Пример использования:
<source lang="cpp">
struct A {
virtual void f() {}
};
struct B : A {
virtual void f() {}
};

...
A* pa = new B;
A* pa2 = new A;

B* pb = dynamic_cast<B*>(pa); // pb указывает на B
B* pb2 = dynamic_cast<B*>(pa2); // pb2 указывает на А, а не на В!

pb->f();
pb2->f(); // ошибка на этапе исполнения!
</source>

Замечание: При приведении к указателю на void возвращается указатель на начало блока.

=== Общие замечания по разделу RTTI ===
* почти всегда можно обойтись без RTTI и чаще всего использование этого механизма говорит об ошибке проектирования
* на этапе отладки применение RTTI бывает полезно.

STL. Последовательные контейнеры

2012-06-11T06:42:53Z

Zalim:

'''Внимание!''' В лекции могут содержаться ошибки и неточности. Прошу исправлять по мере обнаружения.
== Введение в STL ==
STL - Standart Template Library. Она стандартизированна. Существует несколько реализаций, в том числе:
* GCC
* MS
* STL Port
В неё входят:
* Контейнеры
* Итераторы
* Алгоритмы

== Последовательные контейнеры ==
Ко всем последовательным контейнерам предъявляются общие требования:
* Copy-constructable (т.е. публичный конструктор копирования).
* Assignable (т.е. публичный оператор присваивания).
* Стандартная семантика.

=== Разновидности ===
* <code>vector</code> - массив подряд идущих элементов.
* <code>list</code> - список взаимосвязанных элеметов.
* <code>deque</code> - совокупность связанных в список массивов фиксированной длины + индексная таблица.
* <code>string/wstring</code> - строка.
Для использования этих контейнеров необходимо перед названием типов писать <code>std::</code>.

=== <code>vector</code> ===
<source lang="cpp">
#include <vector>
using std::vector;
std::vector<int> v;
</source>
У шаблона есть и второй параметр - аллокатор. Он отвечает за стратегию распределения памяти. Его использовать не надо!

Основные методы вектора представлены ниже:
<source lang="cpp">
v.push_back(13); //добавить элемент к вектору
v.empty(); //вектор пуст?
v.size(); //количество элементов в векторе
v[i]; //обращение к i-му элементу вектора
v.at(i); //то же самое, только в случае выхода за пределы вектора кидается исключение out_of_range
v.erase(it); //удаление элемента по итератору (о них будет рассказано далее)
</source>
Пример хранения структуры графа:
<source lang="cpp">
vector<vector<int> > g;
</source>

=== deque ===
<source lang="cpp">
#include <deque>
std::deque<int> d;
d.push_back(10);
d.push_front(7);
// + методы, присущие vector
</source>

=== Итераторы ===
При работе с непрерывными массивами мы использовали указатели с операциями <code>*p</code> и <code>++p</code>. У контейнеров для таких целей применяются итераторы.
<source lang="cpp">
vector<int> v(100, 0);
vector<int>::iterator it = v.begin();
for (; it != v.end(); ++it)
*it = 5;
</source>
Если заменить вектор на другой контейнер, последний цикл будет работать по-прежнему (с учётом того, что такой конструктор есть тольео у вектора).

'''Замечание:''' В условии цикла разумно использовать именно оператор !=, а не <, поскольку последний определён не для всех итераторов.

=== list ===
<source lang="cpp">
#incude <list>
std::list<int> l;
l.push_back(7);
//и другие аналогичные методы
</source>

=== Использование итераторов ===
Вставка в список производится по итераторам:
<source lang="cpp">
v.insert(v.begin() + 5, 10); //вставить 10 на 5-ю позицию
v.end(); //указывает на элемент после последнего!
</source>
Рассмотрим простой пример:

|1|2|3|4|5|6|7|8|9|

<code>v.begin() + 5</code> указывает на 6. Если от него получить итератор, который бежит в обратном направлении, он будет указывать на 5. Поэтому итератор удобнее рассматривать как указывающий на промежуток, а не на конкретный элемент.

=== Различные замечания ===
* <code>l.size()</code> в большинстве реализаций работает за О(1).
* В <code>deque</code> удаление и добавление в начало и конец работают за О(1).
* <code>vector</code> не умеет уменьшаться, он только растёт.
<source lang="cpp">
v.clear(); //v.erase(v.begin(), v.end());
//чтобы действительно очистить буфер, надо:
vector<int>().swap(v);
//чтобы заменить, немного иначе:
vector<int>(v).swap(v);
</source>
* При расширении массивов могут возникнуть проблемы, а именно, инвалидация итераторов. Можно использовать:
<source lang="cpp">
v.reserve(100); //зарезервировать размер буфера, равный 100
v.reserve(v.size() + 100);
v.capacity; //размер буфера
</source>
* Инвалидация может так же произойти и при удалении элементов (итератор будет указывать не на тот элемент, который ожидается). Ниже приведены два примера правильной работы с итераторами:
<source lang="cpp">
//удаляем все элементы, кратные 2
for (it = v.begin(); it != v.end(); ) {
if (*it % 2)
v.erase(it);
else
++it;
}
//вставим перед элементами, кратными 2, новые элементы, равные 0
for (it = v.begin(); it != v.end(); ++it) {
if (*it % 2) {
it = v.insert(it, 0);
++it;
}
}
</source>

=== string ===
<source lang="cpp">
typedef basic_string<char> string;
typedef basic_string<wchar> wstring;
</source>
Стратегия cow (copy on write) позволяет выиграть при копировании.

Для <code>const</code> объектов есть <code>const_iterator</code>.

Строки на самом деле имеют три параметра в конструкторе. Один из них - аллокатор, отвечает за распределение памяти, и другой - chartrait, определяет механизм сравнения строк.

=== Код в стиле С ===
* <code>s.c_str();</code> возвращает строку в стиле С.
* <code>string(str);</code> конструирует строку в стиле С++ от строки в стиле С.
* <code>&v[0]; v.size();</code> возвращают указатель на начало массива и его длину.
* <code>vector|list|deque<int>(p, p+size);</code> конструируют вектор, список или деку соответственно от массива.

НИР

2012-04-24T07:31:45Z

Zalim: /* 09.03.2012 */

== Карта дорог ==
Руководитель: Лесин 
Ссылка на проект: 
Команда:
* Иванов Антон
* Сорокин Артем
* Кононенко Василий
Отчёт:
* 6.03.2012 - Первая встреча.
** Задачи на неделю:
** Кононенко: подготовить результаты прошлого семестра для коллективного проекта.
** Сорокин, Иванов: разобраться с базовыми алгоритмами поиска кратчайших путей.
* 20.03.2012 - Третья встреча.
** Обсудили структуру проекта. Определили "первые шаги" реализации.
** Задачи на неделю:
** Кононенко: Презентация (reaches), организация проекта, загрузка OSM формата, reaches preprocessing.
** Сорокин: создать wiki, github, разобраться с визуализатором и написать алг. Дейкстры, презентация?
** Иванов: web интерфейс (client-side), работающий сервер обрабатывающий запросы поиска евклидова расстояния между 2мя точками
** ?- допишите на какую тему презентации плиз.
* 27.03.2012
** Была проведена презентация Артема Сорокина по алгоритмам на графах (? уточни плз. название алгоритмов)
** Задачи на неделю:
** Иванов: закончить предыдущее задание. (ServerSide договорились делать на python'e, клиент уже почти написан на javascript'e с использованием openLayers api)
* 13.04.2012
** Задачи на неделю:
** Кононенко: реализация препроцессинга с Penalties и Shortcuts.
** Сорокин: Transit points (?)
** Иванов: Веб-сервер (?)

== MyFit ==
Руководитель: EMC 
Ссылка на проект:
* [http://osll.spb.ru/projects/myfit/ трекер]
* [http://code.google.com/p/myfit/ репозиторий]
Команда:
* Опейкин Александр
* Певзнер Алина
* Башоров Залим

==== 09.03.2012 ====
Выполнено 2 тестовых задания на Java и на GWT. 
Получены следующие задачи:
* [http://redmine.osll.spb.ru/issues/3155 Опейкин] (Готово)
* [http://redmine.osll.spb.ru/issues/3156 Певзнер] (Готово)
* [http://redmine.osll.spb.ru/issues/3157 Башоров] (Готово)

==== 12.03.2012 ====
Получены следующие задачи:
* [http://redmine.osll.spb.ru/issues/3175 Башоров] (Готово)
* [http://redmine.osll.spb.ru/issues/3177 Опейкин] (Готово)
* [http://redmine.osll.spb.ru/issues/3176 Певзнер] (Готово)

==== 27.03.2012 ====
Митинг в EMC -- обсудили текущие задачи и тестовые задания. 
Закоммитили рабочие версии кода по задачам, ожидаем ревью. 
(задачи: [http://redmine.osll.spb.ru/issues/3175 Башоров], [http://redmine.osll.spb.ru/issues/3177 Опейкин], [http://redmine.osll.spb.ru/issues/3176 Певзнер])

=== 09.03.2012 ===
Певзнер: обсудила замечания по результатам ревью по старой задаче, получила новую задачу переноса тегов для suite в button панель. 
Башоров: сделать главную страницу для Test Suites. 
Опейкин: реализация фильтрации на стороне сервера. 

=== 13.03.2012 ===
Unit testing seminar

=== 19.03.2012 ===
Митинг в EMC -- обсудили текущие задачи и тестовые задания. 
Башоров: получил новую задачу. 
Опейкин: 
Певзнер: обсудила некоторые вопросы по новой задаче. 

== GPU ==
Руководитель: Рубен Артурович Гиргидов 
Ссылка на проект: 
Команда:
* Коровин Алексей
* Лазарев Сергей
* Кормишин Сергей
Отчёт: 
*1я встреча нам были выданы вводные задачи:
** Разобраться с CUDA, установить и настроить окружение. Написать простенький алгоритм. (Коровин А.)
** Вспомнить "всё" о регулярных выражениях: какие бывают, как пишутся (Лазарев С.)
** Найти обработчики регулярных выражений (Matcher'ы), разобраться в их строении и принципе работы. (Кормишин С.)
*2я встреча:
** Обсудили наши предыдущие задания, расписали план выполнения проекта, цели и др.
** Выданы следующие задачи:
**# Реализовать обработчик РВ на Cuda для одной и n строк (Коровин А.)
**# Найти обработчики РВ на CPU на C++ и адаптировать его для n строк (Кормишин С.)
**# Реализовать обработчик РВ нa cuBLAS (Лазарев С.)
*3я встреча:
** Обсудили наши успехи, искали нужное представление автомата в виде матрицы для задачи реализации РВ на cuBLAS
** Решили какие паттерны РВ будут в бенчмарках
** По CUDA на неделю нужно было реализовать простейшую схему распараллеливания существующих реализаций регулярных выражений(Regexp9, Cuda paper code) и посмотреть на производительность.
*4я встреча:
** Портированная библиотека работать не хочет и разобраться без отладчика - очень трудно. Попытались настроить удалённую отладку на CUDA. Всё настроилось, но софт (Nsight) очень сырой, происходят непонятные ошибки и они нигде не журналируются и не объясняются. (Коровин А.)
*5я встреча:
** Реализован поиск с помощью регулярных выражений на основе матричных вычислений с использованием библиотеки cuBLAS. Пока сделан поиск в одной строке. Дальше надо распараллелить на несколько строк. (Лазарев С.)
** Портированная библиотека после длительной отладки начала матчить строку с регулярным выражением. Задача 1 выражение - 1 строка решена. Следующая задача задействовать все ядра видеокарты и научиться матчить N строк на одно регулярное выражение. (Коровин А.)
** Реализовн поиск с помощью re2 одной строки на одном ядре. Теперь нужно сделать для n строк на к ядрах.
*6я встреча:
** Был реализован матчинг N строк на 1 регулярное выражение на CUDA. К следующей встрече нужно попробовать оптимизировать программу. (Коровин А.)

== Syrop ==
Руководитель: Смаль Александр Владимирович 
Ссылка на проект: [https://github.com/avsmal/Syrop Syrop] 
Wiki проекта: [https://github.com/avsmal/Syrop/wiki Github] 
Команда:
* Кринкин Михаил
* Мартынов Семён
* Крашенинникова Ксения
* Великий Алексей
Отчёт:
* 27/feb/2011 - Первая встреча. Обсуждение цели проекта, способов реализации и внутри командного взаимодействия. Разделение задач. Создан репозиторий проекта на GitHub. Открытый вопрос - применение методологий разработки в проекте.
* 01/mar/2011 - Сode review.
* 05/mar/2011 - Введение договоренностей о code style, оформлении документации, спецификация на интерфейсы. Показ первого GUI, уточнение новых задач.
* 12/mar/2011 - Всё хорошо.
* 19/mar/2011 - Снова всё хорошо - работаем.
* 26/mar/2011 - Семен у нас большой шутник, см. список задач на трекере

== Дублирующий код ==
Руководитель: Иваницкий 
Ссылка на проект: http://code.google.com/p/aptu-practice-code-duplication/ 
Команда:
* Бандурин Дима (Project manager)
* Лепенькин Ярослав (Поиск дублирующего кода в C++)
* Фофанова Маша (Поиск дублирующего кода в Java)

Отчёт:

===28.02.2012 - Вводная встреча===
* Распределение ролей в команде
:Бандурин Дима (Project manager)
:Лепенькин Ярослав. Изучение специфики C++ для поиска дублирующего кода
:Фофанова Маша. Изучение специфики Java для поиск дублирующего кода.
* Уточнение функционала
* Организационные вопросы

===06.03.2012 - Контрольная встреча===
* Изучение существующих решений
** Michael Wise's Greedy String Tiling algorithm
** Преобразование Барроуза-Уиллера
** Алгоритм Рабина-Карпа
** Механизм использующийся в IntelliJ IDEA
[[Файл:Solutions.pdf|краткое описание]]

===15.03.2012===
В рамках НИР необходимо ответить на три вопроса.
* Научная новизна
** Список существующих решений для нашей задачи.(Ярослав)
** Способы оценки существующих решений.(Маша)
** Библиотеки, для проведения испытания (исследуемая выборка) (Дмитрий)
* Рабочий прототип. Решено делать плагин на базе IntelliJ IDEA. Функциональность плагина будет выяснена дальше.
* Этапы разработки
Решено разбить разработку на три этапа.
# Определение требований к разрабатываемой программе.(3 недели)
# Создание прототипа (2 недели)
# Разработка плагина (4 недели)
## Основная функциональность (2 недели)
## Тестирование и доведение (2 неделя)
## Документирование и создание презентационных материалов (1 неделя параллельно со вторым пунктом.)
Итого 9 недель. Предположительный срок завершения проекта : 21 мая

===21.03.2012===
*Возможные метрики для сравнения алгоритмов поиска дубликатов
** Время работы, используемая память, CPU
** Число правильно найденных дубликатов
*** Необходимо учитывать длину каждого дубликата, чтобы учитывать возможную вложенность. Длина дубликата определяется числом символов в нем.
** Число неправильно найденных дубликатов
*Метрики для алгоритмов замены дубликатов
** Объем кода, получающегося после замены найденных дубликатов на вызовы соответствующих методов
** Релевантность участка кода. Код считается иррелевантным, если его замена на предлагающийся код слишком трудоемка и не имеет смысла.
*Стоит также определить, на каких констукциях дубликатов алгоритмы работают лучше, а на каких хуже.

===6.04.2012===
*Исследованы IdeaCodeDuplicatePlugin, Digger, Simian и получены следующие метрики:
**Весовой коэффициент. Каждой строке присваивается вес, который соответствует числу программ, сказавших, что эта строка что-то дублирует.
***idea 23310
***digger 34839
***simian 26050
**Коэффициент по пересечению. Если строка встретилась в результате несколько раз, она учитывается несколько раз.
***idea 0.94
***digger 0.92
***simian 0.94
**Коэффициент по объединению. Если строка встретилась в результате несколько раз, она учитывается несколько раз.
***idea 0.86
***digger 0.12
***simian 0.18
*Попарные сравнения алгоритмов по тем же параметрам:
**digger | 1.12 | 0.55 | 29589
**simian | 1.03 | 0.76 | 21863

**idea | 1.0 | 0.93 |19123
**digger | 1.0 | 0.15 | 28710

**idea | 1.0 | 0.89 | 18060
**simian | 1.0 | 0.19 | 19921
* Решено использовать алгоритм из Simian.

===11.04.2012===
: Пишется прототип, в основе которого лежит Simian. Прототип будет представлять собой плагин к IntelliJ IDEA. Для отображения найденных дублирующих строк будет использоваться механизм Inspections. В качестве возможных исправлений пользователю будет предложено заменить строки на вызов соответствующего метода. Эквивалентность найденных дублирующих строк будет дополнительно проверяться с помощью соответствующих синтаксических деревьев.

===16.04.2012===
: Написан плагин для замены дублирующего кода вызовами соответствующих методов. В основе лежит поиск дубликатов IntelliJ Idea, так как при первом рассмотрении данный алгоритм находит гораздо более сложные дубликаты нежели Simian. В плагине используется механизм Inspections из IntelliJ Idea. При запуске анализатора кода находятся все public static методы, после чего каждый класс из предлагаемого скоупа анализируется на предмет наличия кода дублирующего найденные методы. Затем пользователю предлагается заменить дублирующий код на вызов соответствующих методов.

== Конфигуратор контейнеров AndroidVM ==
Руководитель: Кринкин К.В.

Команда:
* Владислав Савельев
* Дмитрий Шеставин
* Сергей Казенюк ([[AVMConf_Kazenyuk|отчёты]])

Отчёт:

13 марта. Встреча с разработчиками проекта. Поставлены задачи.
: Владислав: Послушал лекцию Кирилла Владимировича про QT. Подумал об интерфейсе конфигуратора. Написал очень черновой вариант, создающий и запускающий контейнеры. Начал смотреть видео лекций Кирилла Владимировича про QT и шаблон MVC, а также читать про QML.

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

10 апреля.
: Владислав: Переписал интерфейс с использованием «модели — представления — модели представления». Нарисовал иконок и спроектировал внешний вид приложения в перспективе для презентации Жени Баталова на предзащите.
: Добавил в программный интерфейс конфигуратора возможность для получения от устройства информации о списке контейнеров.

== Поиск дублирующих сообщений об ошибках ==

Команда:
* Ждан Анна
* Краско Евгений
* Кудинкин Алексей

Отчет 03.03 - 11.03
* Настроено окружение: проект в MPS, проект в IDEA
* Описана модель данных на языке dnq
* Написан rest api для админки и для добавления в базу новых сообщений об ошибках
* Написан парсер сообщений об ошибках
* Написана первая версия алгоритма сравнения сообщений об ошибках
* Написаны базовые классы для запуска тестов (различные заглушки для методов сервлет-контейнера, создание контекста для бинов и тп)
* Написаны тесты на парсер и алгоритм сравнения
* Частично написаны тесты на rest api (jmeter)

Отчет 11.03 - 18.03
* Улучшена первая версия алгоритма сравнения сообщений об ошибках
* Реализован альтернативный алгоритм сравнения сообщений об ошибках.
* Написаны тесты на оба алгоритма
* Реализован парсер сообщений об ошибках для языка C#. Парсер рассчитан на формат, принятый в Решарпере
* Написаны тесты на парсер
* В язык для рестовых тестов добавлена возможность проверять хереды респонса
* Добавлен ui для администрирования приложение
* Начата реализация JobProcessor'a, обрабатывающего сообщения об ошибках на предмет поиска дубликатов.

Отчет 19.03 - 25.03
* Написан классификатор, разбивающий сообщения об ошибках на кластеры.
* Добавлены новые возможности web-интерфейса для администрирования приложения.

Отчет 25.03 - 7.04
* Написан JobProcessor, разбивающий сообщения об ошибках на кластеры.
* Написаны тесты на JobProcessor
* Начата реализация интеграции приложения с Ютрэком
* Осуществлен переход на более новую версию библиотеки jersey

НИР

2012-04-24T07:31:04Z

Zalim: /* 13.03.2012 */

== Карта дорог ==
Руководитель: Лесин 
Ссылка на проект: 
Команда:
* Иванов Антон
* Сорокин Артем
* Кононенко Василий
Отчёт:
* 6.03.2012 - Первая встреча.
** Задачи на неделю:
** Кононенко: подготовить результаты прошлого семестра для коллективного проекта.
** Сорокин, Иванов: разобраться с базовыми алгоритмами поиска кратчайших путей.
* 20.03.2012 - Третья встреча.
** Обсудили структуру проекта. Определили "первые шаги" реализации.
** Задачи на неделю:
** Кононенко: Презентация (reaches), организация проекта, загрузка OSM формата, reaches preprocessing.
** Сорокин: создать wiki, github, разобраться с визуализатором и написать алг. Дейкстры, презентация?
** Иванов: web интерфейс (client-side), работающий сервер обрабатывающий запросы поиска евклидова расстояния между 2мя точками
** ?- допишите на какую тему презентации плиз.
* 27.03.2012
** Была проведена презентация Артема Сорокина по алгоритмам на графах (? уточни плз. название алгоритмов)
** Задачи на неделю:
** Иванов: закончить предыдущее задание. (ServerSide договорились делать на python'e, клиент уже почти написан на javascript'e с использованием openLayers api)
* 13.04.2012
** Задачи на неделю:
** Кононенко: реализация препроцессинга с Penalties и Shortcuts.
** Сорокин: Transit points (?)
** Иванов: Веб-сервер (?)

== MyFit ==
Руководитель: EMC 
Ссылка на проект:
* [http://osll.spb.ru/projects/myfit/ трекер]
* [http://code.google.com/p/myfit/ репозиторий]
Команда:
* Опейкин Александр
* Певзнер Алина
* Башоров Залим

==== 09.03.2012 ====
Выполнено 2 тестовых задания на Java и на GWT. 
Получены следующие задачи:
* [http://redmine.osll.spb.ru/issues/3155 Опейкин] (Готово)
* [http://redmine.osll.spb.ru/issues/3156 Певзнер] (Готово)
* [http://redmine.osll.spb.ru/issues/3157 Башоров] (Готово)

==== 12.03.2012 ====
Получены следующие задачи:
* [http://redmine.osll.spb.ru/issues/3175 Башоров] (Готово)
* [http://redmine.osll.spb.ru/issues/3177 Опейкин] (Готово)
* [http://redmine.osll.spb.ru/issues/3176 Певзнер] (Готово)

==== 27.03.2012 ====
Митинг в EMC -- обсудили текущие задачи и тестовые задания. 
Закоммитили рабочие версии кода по задачам, ожидаем ревью. 
(задачи: [http://redmine.osll.spb.ru/issues/3175 Башоров], [http://redmine.osll.spb.ru/issues/3177 Опейкин], [http://redmine.osll.spb.ru/issues/3176 Певзнер])

=== 09.03.2012 ===
Певзнер: обсудила замечания по результатам ревью по старой задаче, получила новую задачу переноса тегов для suite в button панель
Башоров: сделать главную страницу для Test Suites
Опейкин: реализация фильтрации на стороне сервера.
=== 13.03.2012 ===
Unit testing seminar

=== 19.03.2012 ===
Митинг в EMC -- обсудили текущие задачи и тестовые задания. 
Башоров: получил новую задачу. 
Опейкин: 
Певзнер: обсудила некоторые вопросы по новой задаче. 

== GPU ==
Руководитель: Рубен Артурович Гиргидов 
Ссылка на проект: 
Команда:
* Коровин Алексей
* Лазарев Сергей
* Кормишин Сергей
Отчёт: 
*1я встреча нам были выданы вводные задачи:
** Разобраться с CUDA, установить и настроить окружение. Написать простенький алгоритм. (Коровин А.)
** Вспомнить "всё" о регулярных выражениях: какие бывают, как пишутся (Лазарев С.)
** Найти обработчики регулярных выражений (Matcher'ы), разобраться в их строении и принципе работы. (Кормишин С.)
*2я встреча:
** Обсудили наши предыдущие задания, расписали план выполнения проекта, цели и др.
** Выданы следующие задачи:
**# Реализовать обработчик РВ на Cuda для одной и n строк (Коровин А.)
**# Найти обработчики РВ на CPU на C++ и адаптировать его для n строк (Кормишин С.)
**# Реализовать обработчик РВ нa cuBLAS (Лазарев С.)
*3я встреча:
** Обсудили наши успехи, искали нужное представление автомата в виде матрицы для задачи реализации РВ на cuBLAS
** Решили какие паттерны РВ будут в бенчмарках
** По CUDA на неделю нужно было реализовать простейшую схему распараллеливания существующих реализаций регулярных выражений(Regexp9, Cuda paper code) и посмотреть на производительность.
*4я встреча:
** Портированная библиотека работать не хочет и разобраться без отладчика - очень трудно. Попытались настроить удалённую отладку на CUDA. Всё настроилось, но софт (Nsight) очень сырой, происходят непонятные ошибки и они нигде не журналируются и не объясняются. (Коровин А.)
*5я встреча:
** Реализован поиск с помощью регулярных выражений на основе матричных вычислений с использованием библиотеки cuBLAS. Пока сделан поиск в одной строке. Дальше надо распараллелить на несколько строк. (Лазарев С.)
** Портированная библиотека после длительной отладки начала матчить строку с регулярным выражением. Задача 1 выражение - 1 строка решена. Следующая задача задействовать все ядра видеокарты и научиться матчить N строк на одно регулярное выражение. (Коровин А.)
** Реализовн поиск с помощью re2 одной строки на одном ядре. Теперь нужно сделать для n строк на к ядрах.
*6я встреча:
** Был реализован матчинг N строк на 1 регулярное выражение на CUDA. К следующей встрече нужно попробовать оптимизировать программу. (Коровин А.)

== Syrop ==
Руководитель: Смаль Александр Владимирович 
Ссылка на проект: [https://github.com/avsmal/Syrop Syrop] 
Wiki проекта: [https://github.com/avsmal/Syrop/wiki Github] 
Команда:
* Кринкин Михаил
* Мартынов Семён
* Крашенинникова Ксения
* Великий Алексей
Отчёт:
* 27/feb/2011 - Первая встреча. Обсуждение цели проекта, способов реализации и внутри командного взаимодействия. Разделение задач. Создан репозиторий проекта на GitHub. Открытый вопрос - применение методологий разработки в проекте.
* 01/mar/2011 - Сode review.
* 05/mar/2011 - Введение договоренностей о code style, оформлении документации, спецификация на интерфейсы. Показ первого GUI, уточнение новых задач.
* 12/mar/2011 - Всё хорошо.
* 19/mar/2011 - Снова всё хорошо - работаем.
* 26/mar/2011 - Семен у нас большой шутник, см. список задач на трекере

== Дублирующий код ==
Руководитель: Иваницкий 
Ссылка на проект: http://code.google.com/p/aptu-practice-code-duplication/ 
Команда:
* Бандурин Дима (Project manager)
* Лепенькин Ярослав (Поиск дублирующего кода в C++)
* Фофанова Маша (Поиск дублирующего кода в Java)

Отчёт:

===28.02.2012 - Вводная встреча===
* Распределение ролей в команде
:Бандурин Дима (Project manager)
:Лепенькин Ярослав. Изучение специфики C++ для поиска дублирующего кода
:Фофанова Маша. Изучение специфики Java для поиск дублирующего кода.
* Уточнение функционала
* Организационные вопросы

===06.03.2012 - Контрольная встреча===
* Изучение существующих решений
** Michael Wise's Greedy String Tiling algorithm
** Преобразование Барроуза-Уиллера
** Алгоритм Рабина-Карпа
** Механизм использующийся в IntelliJ IDEA
[[Файл:Solutions.pdf|краткое описание]]

===15.03.2012===
В рамках НИР необходимо ответить на три вопроса.
* Научная новизна
** Список существующих решений для нашей задачи.(Ярослав)
** Способы оценки существующих решений.(Маша)
** Библиотеки, для проведения испытания (исследуемая выборка) (Дмитрий)
* Рабочий прототип. Решено делать плагин на базе IntelliJ IDEA. Функциональность плагина будет выяснена дальше.
* Этапы разработки
Решено разбить разработку на три этапа.
# Определение требований к разрабатываемой программе.(3 недели)
# Создание прототипа (2 недели)
# Разработка плагина (4 недели)
## Основная функциональность (2 недели)
## Тестирование и доведение (2 неделя)
## Документирование и создание презентационных материалов (1 неделя параллельно со вторым пунктом.)
Итого 9 недель. Предположительный срок завершения проекта : 21 мая

===21.03.2012===
*Возможные метрики для сравнения алгоритмов поиска дубликатов
** Время работы, используемая память, CPU
** Число правильно найденных дубликатов
*** Необходимо учитывать длину каждого дубликата, чтобы учитывать возможную вложенность. Длина дубликата определяется числом символов в нем.
** Число неправильно найденных дубликатов
*Метрики для алгоритмов замены дубликатов
** Объем кода, получающегося после замены найденных дубликатов на вызовы соответствующих методов
** Релевантность участка кода. Код считается иррелевантным, если его замена на предлагающийся код слишком трудоемка и не имеет смысла.
*Стоит также определить, на каких констукциях дубликатов алгоритмы работают лучше, а на каких хуже.

===6.04.2012===
*Исследованы IdeaCodeDuplicatePlugin, Digger, Simian и получены следующие метрики:
**Весовой коэффициент. Каждой строке присваивается вес, который соответствует числу программ, сказавших, что эта строка что-то дублирует.
***idea 23310
***digger 34839
***simian 26050
**Коэффициент по пересечению. Если строка встретилась в результате несколько раз, она учитывается несколько раз.
***idea 0.94
***digger 0.92
***simian 0.94
**Коэффициент по объединению. Если строка встретилась в результате несколько раз, она учитывается несколько раз.
***idea 0.86
***digger 0.12
***simian 0.18
*Попарные сравнения алгоритмов по тем же параметрам:
**digger | 1.12 | 0.55 | 29589
**simian | 1.03 | 0.76 | 21863

**idea | 1.0 | 0.93 |19123
**digger | 1.0 | 0.15 | 28710

**idea | 1.0 | 0.89 | 18060
**simian | 1.0 | 0.19 | 19921
* Решено использовать алгоритм из Simian.

===11.04.2012===
: Пишется прототип, в основе которого лежит Simian. Прототип будет представлять собой плагин к IntelliJ IDEA. Для отображения найденных дублирующих строк будет использоваться механизм Inspections. В качестве возможных исправлений пользователю будет предложено заменить строки на вызов соответствующего метода. Эквивалентность найденных дублирующих строк будет дополнительно проверяться с помощью соответствующих синтаксических деревьев.

===16.04.2012===
: Написан плагин для замены дублирующего кода вызовами соответствующих методов. В основе лежит поиск дубликатов IntelliJ Idea, так как при первом рассмотрении данный алгоритм находит гораздо более сложные дубликаты нежели Simian. В плагине используется механизм Inspections из IntelliJ Idea. При запуске анализатора кода находятся все public static методы, после чего каждый класс из предлагаемого скоупа анализируется на предмет наличия кода дублирующего найденные методы. Затем пользователю предлагается заменить дублирующий код на вызов соответствующих методов.

== Конфигуратор контейнеров AndroidVM ==
Руководитель: Кринкин К.В.

Команда:
* Владислав Савельев
* Дмитрий Шеставин
* Сергей Казенюк ([[AVMConf_Kazenyuk|отчёты]])

Отчёт:

13 марта. Встреча с разработчиками проекта. Поставлены задачи.
: Владислав: Послушал лекцию Кирилла Владимировича про QT. Подумал об интерфейсе конфигуратора. Написал очень черновой вариант, создающий и запускающий контейнеры. Начал смотреть видео лекций Кирилла Владимировича про QT и шаблон MVC, а также читать про QML.

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

10 апреля.
: Владислав: Переписал интерфейс с использованием «модели — представления — модели представления». Нарисовал иконок и спроектировал внешний вид приложения в перспективе для презентации Жени Баталова на предзащите.
: Добавил в программный интерфейс конфигуратора возможность для получения от устройства информации о списке контейнеров.

== Поиск дублирующих сообщений об ошибках ==

Команда:
* Ждан Анна
* Краско Евгений
* Кудинкин Алексей

Отчет 03.03 - 11.03
* Настроено окружение: проект в MPS, проект в IDEA
* Описана модель данных на языке dnq
* Написан rest api для админки и для добавления в базу новых сообщений об ошибках
* Написан парсер сообщений об ошибках
* Написана первая версия алгоритма сравнения сообщений об ошибках
* Написаны базовые классы для запуска тестов (различные заглушки для методов сервлет-контейнера, создание контекста для бинов и тп)
* Написаны тесты на парсер и алгоритм сравнения
* Частично написаны тесты на rest api (jmeter)

Отчет 11.03 - 18.03
* Улучшена первая версия алгоритма сравнения сообщений об ошибках
* Реализован альтернативный алгоритм сравнения сообщений об ошибках.
* Написаны тесты на оба алгоритма
* Реализован парсер сообщений об ошибках для языка C#. Парсер рассчитан на формат, принятый в Решарпере
* Написаны тесты на парсер
* В язык для рестовых тестов добавлена возможность проверять хереды респонса
* Добавлен ui для администрирования приложение
* Начата реализация JobProcessor'a, обрабатывающего сообщения об ошибках на предмет поиска дубликатов.

Отчет 19.03 - 25.03
* Написан классификатор, разбивающий сообщения об ошибках на кластеры.
* Добавлены новые возможности web-интерфейса для администрирования приложения.

Отчет 25.03 - 7.04
* Написан JobProcessor, разбивающий сообщения об ошибках на кластеры.
* Написаны тесты на JobProcessor
* Начата реализация интеграции приложения с Ютрэком
* Осуществлен переход на более новую версию библиотеки jersey

НИР

2012-04-24T07:19:43Z

Zalim: /* 19.03.2012 */

== Карта дорог ==
Руководитель: Лесин 
Ссылка на проект: 
Команда:
* Иванов Антон
* Сорокин Артем
* Кононенко Василий
Отчёт:
* 6.03.2012 - Первая встреча.
** Задачи на неделю:
** Кононенко: подготовить результаты прошлого семестра для коллективного проекта.
** Сорокин, Иванов: разобраться с базовыми алгоритмами поиска кратчайших путей.
* 20.03.2012 - Третья встреча.
** Обсудили структуру проекта. Определили "первые шаги" реализации.
** Задачи на неделю:
** Кононенко: Презентация (reaches), организация проекта, загрузка OSM формата, reaches preprocessing.
** Сорокин: создать wiki, github, разобраться с визуализатором и написать алг. Дейкстры, презентация?
** Иванов: web интерфейс (client-side), работающий сервер обрабатывающий запросы поиска евклидова расстояния между 2мя точками
** ?- допишите на какую тему презентации плиз.
* 27.03.2012
** Была проведена презентация Артема Сорокина по алгоритмам на графах (? уточни плз. название алгоритмов)
** Задачи на неделю:
** Иванов: закончить предыдущее задание. (ServerSide договорились делать на python'e, клиент уже почти написан на javascript'e с использованием openLayers api)
* 13.04.2012
** Задачи на неделю:
** Кононенко: реализация препроцессинга с Penalties и Shortcuts.
** Сорокин: Transit points (?)
** Иванов: Веб-сервер (?)

== MyFit ==
Руководитель: EMC 
Ссылка на проект:
* [http://osll.spb.ru/projects/myfit/ трекер]
* [http://code.google.com/p/myfit/ репозиторий]
Команда:
* Опейкин Александр
* Певзнер Алина
* Башоров Залим

==== 09.03.2012 ====
Выполнено 2 тестовых задания на Java и на GWT. 
Получены следующие задачи:
* [http://redmine.osll.spb.ru/issues/3155 Опейкин] (Готово)
* [http://redmine.osll.spb.ru/issues/3156 Певзнер] (Готово)
* [http://redmine.osll.spb.ru/issues/3157 Башоров] (Готово)

==== 12.03.2012 ====
Получены следующие задачи:
* [http://redmine.osll.spb.ru/issues/3175 Башоров] (Готово)
* [http://redmine.osll.spb.ru/issues/3177 Опейкин] (Готово)
* [http://redmine.osll.spb.ru/issues/3176 Певзнер] (Готово)

==== 27.03.2012 ====
Митинг в EMC -- обсудили текущие задачи и тестовые задания. 
Закоммитили рабочие версии кода по задачам, ожидаем ревью. 
(задачи: [http://redmine.osll.spb.ru/issues/3175 Башоров], [http://redmine.osll.spb.ru/issues/3177 Опейкин], [http://redmine.osll.spb.ru/issues/3176 Певзнер])

=== 13.03.2012 ===
Unit testing seminar

=== 19.03.2012 ===
Митинг в EMC -- обсудили текущие задачи и тестовые задания. 
Башоров: получил новую задачу. 
Опейкин: 
Певзнер: обсудила некоторые вопросы по новой задаче. 

== GPU ==
Руководитель: Рубен Артурович Гиргидов 
Ссылка на проект: 
Команда:
* Коровин Алексей
* Лазарев Сергей
* Кормишин Сергей
Отчёт: 
*1я встреча нам были выданы вводные задачи:
** Разобраться с CUDA, установить и настроить окружение. Написать простенький алгоритм. (Коровин А.)
** Вспомнить "всё" о регулярных выражениях: какие бывают, как пишутся (Лазарев С.)
** Найти обработчики регулярных выражений (Matcher'ы), разобраться в их строении и принципе работы. (Кормишин С.)
*2я встреча:
** Обсудили наши предыдущие задания, расписали план выполнения проекта, цели и др.
** Выданы следующие задачи:
**# Реализовать обработчик РВ на Cuda для одной и n строк (Коровин А.)
**# Найти обработчики РВ на CPU на C++ и адаптировать его для n строк (Кормишин С.)
**# Реализовать обработчик РВ нa cuBLAS (Лазарев С.)
*3я встреча:
** Обсудили наши успехи, искали нужное представление автомата в виде матрицы для задачи реализации РВ на cuBLAS
** Решили какие паттерны РВ будут в бенчмарках
** По CUDA на неделю нужно было реализовать простейшую схему распараллеливания существующих реализаций регулярных выражений(Regexp9, Cuda paper code) и посмотреть на производительность.
*4я встреча:
** Портированная библиотека работать не хочет и разобраться без отладчика - очень трудно. Попытались настроить удалённую отладку на CUDA. Всё настроилось, но софт (Nsight) очень сырой, происходят непонятные ошибки и они нигде не журналируются и не объясняются. (Коровин А.)
*5я встреча:
** Реализован поиск с помощью регулярных выражений на основе матричных вычислений с использованием библиотеки cuBLAS. Пока сделан поиск в одной строке. Дальше надо распараллелить на несколько строк. (Лазарев С.)
** Портированная библиотека после длительной отладки начала матчить строку с регулярным выражением. Задача 1 выражение - 1 строка решена. Следующая задача задействовать все ядра видеокарты и научиться матчить N строк на одно регулярное выражение. (Коровин А.)
** Реализовн поиск с помощью re2 одной строки на одном ядре. Теперь нужно сделать для n строк на к ядрах.
*6я встреча:
** Был реализован матчинг N строк на 1 регулярное выражение на CUDA. К следующей встрече нужно попробовать оптимизировать программу. (Коровин А.)

== Syrop ==
Руководитель: Смаль Александр Владимирович 
Ссылка на проект: [https://github.com/avsmal/Syrop Syrop] 
Wiki проекта: [https://github.com/avsmal/Syrop/wiki Github] 
Команда:
* Кринкин Михаил
* Мартынов Семён
* Крашенинникова Ксения
* Великий Алексей
Отчёт:
* 27/feb/2011 - Первая встреча. Обсуждение цели проекта, способов реализации и внутри командного взаимодействия. Разделение задач. Создан репозиторий проекта на GitHub. Открытый вопрос - применение методологий разработки в проекте.
* 01/mar/2011 - Сode review.
* 05/mar/2011 - Введение договоренностей о code style, оформлении документации, спецификация на интерфейсы. Показ первого GUI, уточнение новых задач.
* 12/mar/2011 - Всё хорошо.
* 19/mar/2011 - Снова всё хорошо - работаем.
* 26/mar/2011 - Семен у нас большой шутник, см. список задач на трекере

== Дублирующий код ==
Руководитель: Иваницкий 
Ссылка на проект: http://code.google.com/p/aptu-practice-code-duplication/ 
Команда:
* Бандурин Дима (Project manager)
* Лепенькин Ярослав (Поиск дублирующего кода в C++)
* Фофанова Маша (Поиск дублирующего кода в Java)

Отчёт:

===28.02.2012 - Вводная встреча===
* Распределение ролей в команде
:Бандурин Дима (Project manager)
:Лепенькин Ярослав. Изучение специфики C++ для поиска дублирующего кода
:Фофанова Маша. Изучение специфики Java для поиск дублирующего кода.
* Уточнение функционала
* Организационные вопросы

===06.03.2012 - Контрольная встреча===
* Изучение существующих решений
** Michael Wise's Greedy String Tiling algorithm
** Преобразование Барроуза-Уиллера
** Алгоритм Рабина-Карпа
** Механизм использующийся в IntelliJ IDEA
[[Файл:Solutions.pdf|краткое описание]]

===15.03.2012===
В рамках НИР необходимо ответить на три вопроса.
* Научная новизна
** Список существующих решений для нашей задачи.(Ярослав)
** Способы оценки существующих решений.(Маша)
** Библиотеки, для проведения испытания (исследуемая выборка) (Дмитрий)
* Рабочий прототип. Решено делать плагин на базе IntelliJ IDEA. Функциональность плагина будет выяснена дальше.
* Этапы разработки
Решено разбить разработку на три этапа.
# Определение требований к разрабатываемой программе.(3 недели)
# Создание прототипа (2 недели)
# Разработка плагина (4 недели)
## Основная функциональность (2 недели)
## Тестирование и доведение (2 неделя)
## Документирование и создание презентационных материалов (1 неделя параллельно со вторым пунктом.)
Итого 9 недель. Предположительный срок завершения проекта : 21 мая

===21.03.2012===
*Возможные метрики для сравнения алгоритмов поиска дубликатов
** Время работы, используемая память, CPU
** Число правильно найденных дубликатов
*** Необходимо учитывать длину каждого дубликата, чтобы учитывать возможную вложенность. Длина дубликата определяется числом символов в нем.
** Число неправильно найденных дубликатов
*Метрики для алгоритмов замены дубликатов
** Объем кода, получающегося после замены найденных дубликатов на вызовы соответствующих методов
** Релевантность участка кода. Код считается иррелевантным, если его замена на предлагающийся код слишком трудоемка и не имеет смысла.
*Стоит также определить, на каких констукциях дубликатов алгоритмы работают лучше, а на каких хуже.

===6.04.2012===
*Исследованы IdeaCodeDuplicatePlugin, Digger, Simian и получены следующие метрики:
**Весовой коэффициент. Каждой строке присваивается вес, который соответствует числу программ, сказавших, что эта строка что-то дублирует.
***idea 23310
***digger 34839
***simian 26050
**Коэффициент по пересечению. Если строка встретилась в результате несколько раз, она учитывается несколько раз.
***idea 0.94
***digger 0.92
***simian 0.94
**Коэффициент по объединению. Если строка встретилась в результате несколько раз, она учитывается несколько раз.
***idea 0.86
***digger 0.12
***simian 0.18
*Попарные сравнения алгоритмов по тем же параметрам:
**digger | 1.12 | 0.55 | 29589
**simian | 1.03 | 0.76 | 21863

**idea | 1.0 | 0.93 |19123
**digger | 1.0 | 0.15 | 28710

**idea | 1.0 | 0.89 | 18060
**simian | 1.0 | 0.19 | 19921
* Решено использовать алгоритм из Simian.

===11.04.2012===
: Пишется прототип, в основе которого лежит Simian. Прототип будет представлять собой плагин к IntelliJ IDEA. Для отображения найденных дублирующих строк будет использоваться механизм Inspections. В качестве возможных исправлений пользователю будет предложено заменить строки на вызов соответствующего метода. Эквивалентность найденных дублирующих строк будет дополнительно проверяться с помощью соответствующих синтаксических деревьев.

===16.04.2012===
: Написан плагин для замены дублирующего кода вызовами соответствующих методов. В основе лежит поиск дубликатов IntelliJ Idea, так как при первом рассмотрении данный алгоритм находит гораздо более сложные дубликаты нежели Simian. В плагине используется механизм Inspections из IntelliJ Idea. При запуске анализатора кода находятся все public static методы, после чего каждый класс из предлагаемого скоупа анализируется на предмет наличия кода дублирующего найденные методы. Затем пользователю предлагается заменить дублирующий код на вызов соответствующих методов.

== Конфигуратор контейнеров AndroidVM ==
Руководитель: Кринкин К.В.

Команда:
* Владислав Савельев
* Дмитрий Шеставин
* Сергей Казенюк ([[AVMConf_Kazenyuk|отчёты]])

Отчёт:

13 марта. Встреча с разработчиками проекта. Поставлены задачи.
: Владислав: Послушал лекцию Кирилла Владимировича про QT. Подумал об интерфейсе конфигуратора. Написал очень черновой вариант, создающий и запускающий контейнеры. Начал смотреть видео лекций Кирилла Владимировича про QT и шаблон MVC, а также читать про QML.

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

10 апреля.
: Владислав: Переписал интерфейс с использованием «модели — представления — модели представления». Нарисовал иконок и спроектировал внешний вид приложения в перспективе для презентации Жени Баталова на предзащите.
: Добавил в программный интерфейс конфигуратора возможность для получения от устройства информации о списке контейнеров.

== Поиск дублирующих сообщений об ошибках ==

Команда:
* Ждан Анна
* Краско Евгений
* Кудинкин Алексей

Отчет 03.03 - 11.03
* Настроено окружение: проект в MPS, проект в IDEA
* Описана модель данных на языке dnq
* Написан rest api для админки и для добавления в базу новых сообщений об ошибках
* Написан парсер сообщений об ошибках
* Написана первая версия алгоритма сравнения сообщений об ошибках
* Написаны базовые классы для запуска тестов (различные заглушки для методов сервлет-контейнера, создание контекста для бинов и тп)
* Написаны тесты на парсер и алгоритм сравнения
* Частично написаны тесты на rest api (jmeter)

Отчет 11.03 - 18.03
* Улучшена первая версия алгоритма сравнения сообщений об ошибках
* Реализован альтернативный алгоритм сравнения сообщений об ошибках.
* Написаны тесты на оба алгоритма
* Реализован парсер сообщений об ошибках для языка C#. Парсер рассчитан на формат, принятый в Решарпере
* Написаны тесты на парсер
* В язык для рестовых тестов добавлена возможность проверять хереды респонса
* Добавлен ui для администрирования приложение
* Начата реализация JobProcessor'a, обрабатывающего сообщения об ошибках на предмет поиска дубликатов.

Отчет 19.03 - 25.03
* Написан классификатор, разбивающий сообщения об ошибках на кластеры.
* Добавлены новые возможности web-интерфейса для администрирования приложения.

Отчет 25.03 - 7.04
* Написан JobProcessor, разбивающий сообщения об ошибках на кластеры.
* Написаны тесты на JobProcessor
* Начата реализация интеграции приложения с Ютрэком
* Осуществлен переход на более новую версию библиотеки jersey

НИР

2012-04-24T07:19:02Z

Zalim: /* MyFit */

== Карта дорог ==
Руководитель: Лесин 
Ссылка на проект: 
Команда:
* Иванов Антон
* Сорокин Артем
* Кононенко Василий
Отчёт:
* 6.03.2012 - Первая встреча.
** Задачи на неделю:
** Кононенко: подготовить результаты прошлого семестра для коллективного проекта.
** Сорокин, Иванов: разобраться с базовыми алгоритмами поиска кратчайших путей.
* 20.03.2012 - Третья встреча.
** Обсудили структуру проекта. Определили "первые шаги" реализации.
** Задачи на неделю:
** Кононенко: Презентация (reaches), организация проекта, загрузка OSM формата, reaches preprocessing.
** Сорокин: создать wiki, github, разобраться с визуализатором и написать алг. Дейкстры, презентация?
** Иванов: web интерфейс (client-side), работающий сервер обрабатывающий запросы поиска евклидова расстояния между 2мя точками
** ?- допишите на какую тему презентации плиз.
* 27.03.2012
** Была проведена презентация Артема Сорокина по алгоритмам на графах (? уточни плз. название алгоритмов)
** Задачи на неделю:
** Иванов: закончить предыдущее задание. (ServerSide договорились делать на python'e, клиент уже почти написан на javascript'e с использованием openLayers api)
* 13.04.2012
** Задачи на неделю:
** Кононенко: реализация препроцессинга с Penalties и Shortcuts.
** Сорокин: Transit points (?)
** Иванов: Веб-сервер (?)

== MyFit ==
Руководитель: EMC 
Ссылка на проект:
* [http://osll.spb.ru/projects/myfit/ трекер]
* [http://code.google.com/p/myfit/ репозиторий]
Команда:
* Опейкин Александр
* Певзнер Алина
* Башоров Залим

==== 09.03.2012 ====
Выполнено 2 тестовых задания на Java и на GWT. 
Получены следующие задачи:
* [http://redmine.osll.spb.ru/issues/3155 Опейкин] (Готово)
* [http://redmine.osll.spb.ru/issues/3156 Певзнер] (Готово)
* [http://redmine.osll.spb.ru/issues/3157 Башоров] (Готово)

==== 12.03.2012 ====
Получены следующие задачи:
* [http://redmine.osll.spb.ru/issues/3175 Башоров] (Готово)
* [http://redmine.osll.spb.ru/issues/3177 Опейкин] (Готово)
* [http://redmine.osll.spb.ru/issues/3176 Певзнер] (Готово)

==== 27.03.2012 ====
Митинг в EMC -- обсудили текущие задачи и тестовые задания. 
Закоммитили рабочие версии кода по задачам, ожидаем ревью. 
(задачи: [http://redmine.osll.spb.ru/issues/3175 Башоров], [http://redmine.osll.spb.ru/issues/3177 Опейкин], [http://redmine.osll.spb.ru/issues/3176 Певзнер])

=== 13.03.2012 ===
Unit testing seminar

=== 19.03.2012 ===
Митинг в EMC -- обсудили текущие задачи и тестовые задания. 
Башоров: получил новую задачу.
Опейкин:
Певзнер: обсудила некоторые вопросы по новой задаче.

== GPU ==
Руководитель: Рубен Артурович Гиргидов 
Ссылка на проект: 
Команда:
* Коровин Алексей
* Лазарев Сергей
* Кормишин Сергей
Отчёт: 
*1я встреча нам были выданы вводные задачи:
** Разобраться с CUDA, установить и настроить окружение. Написать простенький алгоритм. (Коровин А.)
** Вспомнить "всё" о регулярных выражениях: какие бывают, как пишутся (Лазарев С.)
** Найти обработчики регулярных выражений (Matcher'ы), разобраться в их строении и принципе работы. (Кормишин С.)
*2я встреча:
** Обсудили наши предыдущие задания, расписали план выполнения проекта, цели и др.
** Выданы следующие задачи:
**# Реализовать обработчик РВ на Cuda для одной и n строк (Коровин А.)
**# Найти обработчики РВ на CPU на C++ и адаптировать его для n строк (Кормишин С.)
**# Реализовать обработчик РВ нa cuBLAS (Лазарев С.)
*3я встреча:
** Обсудили наши успехи, искали нужное представление автомата в виде матрицы для задачи реализации РВ на cuBLAS
** Решили какие паттерны РВ будут в бенчмарках
** По CUDA на неделю нужно было реализовать простейшую схему распараллеливания существующих реализаций регулярных выражений(Regexp9, Cuda paper code) и посмотреть на производительность.
*4я встреча:
** Портированная библиотека работать не хочет и разобраться без отладчика - очень трудно. Попытались настроить удалённую отладку на CUDA. Всё настроилось, но софт (Nsight) очень сырой, происходят непонятные ошибки и они нигде не журналируются и не объясняются. (Коровин А.)
*5я встреча:
** Реализован поиск с помощью регулярных выражений на основе матричных вычислений с использованием библиотеки cuBLAS. Пока сделан поиск в одной строке. Дальше надо распараллелить на несколько строк. (Лазарев С.)
** Портированная библиотека после длительной отладки начала матчить строку с регулярным выражением. Задача 1 выражение - 1 строка решена. Следующая задача задействовать все ядра видеокарты и научиться матчить N строк на одно регулярное выражение. (Коровин А.)
** Реализовн поиск с помощью re2 одной строки на одном ядре. Теперь нужно сделать для n строк на к ядрах.
*6я встреча:
** Был реализован матчинг N строк на 1 регулярное выражение на CUDA. К следующей встрече нужно попробовать оптимизировать программу. (Коровин А.)

== Syrop ==
Руководитель: Смаль Александр Владимирович 
Ссылка на проект: [https://github.com/avsmal/Syrop Syrop] 
Wiki проекта: [https://github.com/avsmal/Syrop/wiki Github] 
Команда:
* Кринкин Михаил
* Мартынов Семён
* Крашенинникова Ксения
* Великий Алексей
Отчёт:
* 27/feb/2011 - Первая встреча. Обсуждение цели проекта, способов реализации и внутри командного взаимодействия. Разделение задач. Создан репозиторий проекта на GitHub. Открытый вопрос - применение методологий разработки в проекте.
* 01/mar/2011 - Сode review.
* 05/mar/2011 - Введение договоренностей о code style, оформлении документации, спецификация на интерфейсы. Показ первого GUI, уточнение новых задач.
* 12/mar/2011 - Всё хорошо.
* 19/mar/2011 - Снова всё хорошо - работаем.
* 26/mar/2011 - Семен у нас большой шутник, см. список задач на трекере

== Дублирующий код ==
Руководитель: Иваницкий 
Ссылка на проект: http://code.google.com/p/aptu-practice-code-duplication/ 
Команда:
* Бандурин Дима (Project manager)
* Лепенькин Ярослав (Поиск дублирующего кода в C++)
* Фофанова Маша (Поиск дублирующего кода в Java)

Отчёт:

===28.02.2012 - Вводная встреча===
* Распределение ролей в команде
:Бандурин Дима (Project manager)
:Лепенькин Ярослав. Изучение специфики C++ для поиска дублирующего кода
:Фофанова Маша. Изучение специфики Java для поиск дублирующего кода.
* Уточнение функционала
* Организационные вопросы

===06.03.2012 - Контрольная встреча===
* Изучение существующих решений
** Michael Wise's Greedy String Tiling algorithm
** Преобразование Барроуза-Уиллера
** Алгоритм Рабина-Карпа
** Механизм использующийся в IntelliJ IDEA
[[Файл:Solutions.pdf|краткое описание]]

===15.03.2012===
В рамках НИР необходимо ответить на три вопроса.
* Научная новизна
** Список существующих решений для нашей задачи.(Ярослав)
** Способы оценки существующих решений.(Маша)
** Библиотеки, для проведения испытания (исследуемая выборка) (Дмитрий)
* Рабочий прототип. Решено делать плагин на базе IntelliJ IDEA. Функциональность плагина будет выяснена дальше.
* Этапы разработки
Решено разбить разработку на три этапа.
# Определение требований к разрабатываемой программе.(3 недели)
# Создание прототипа (2 недели)
# Разработка плагина (4 недели)
## Основная функциональность (2 недели)
## Тестирование и доведение (2 неделя)
## Документирование и создание презентационных материалов (1 неделя параллельно со вторым пунктом.)
Итого 9 недель. Предположительный срок завершения проекта : 21 мая

===21.03.2012===
*Возможные метрики для сравнения алгоритмов поиска дубликатов
** Время работы, используемая память, CPU
** Число правильно найденных дубликатов
*** Необходимо учитывать длину каждого дубликата, чтобы учитывать возможную вложенность. Длина дубликата определяется числом символов в нем.
** Число неправильно найденных дубликатов
*Метрики для алгоритмов замены дубликатов
** Объем кода, получающегося после замены найденных дубликатов на вызовы соответствующих методов
** Релевантность участка кода. Код считается иррелевантным, если его замена на предлагающийся код слишком трудоемка и не имеет смысла.
*Стоит также определить, на каких констукциях дубликатов алгоритмы работают лучше, а на каких хуже.

===6.04.2012===
*Исследованы IdeaCodeDuplicatePlugin, Digger, Simian и получены следующие метрики:
**Весовой коэффициент. Каждой строке присваивается вес, который соответствует числу программ, сказавших, что эта строка что-то дублирует.
***idea 23310
***digger 34839
***simian 26050
**Коэффициент по пересечению. Если строка встретилась в результате несколько раз, она учитывается несколько раз.
***idea 0.94
***digger 0.92
***simian 0.94
**Коэффициент по объединению. Если строка встретилась в результате несколько раз, она учитывается несколько раз.
***idea 0.86
***digger 0.12
***simian 0.18
*Попарные сравнения алгоритмов по тем же параметрам:
**digger | 1.12 | 0.55 | 29589
**simian | 1.03 | 0.76 | 21863

**idea | 1.0 | 0.93 |19123
**digger | 1.0 | 0.15 | 28710

**idea | 1.0 | 0.89 | 18060
**simian | 1.0 | 0.19 | 19921
* Решено использовать алгоритм из Simian.

===11.04.2012===
: Пишется прототип, в основе которого лежит Simian. Прототип будет представлять собой плагин к IntelliJ IDEA. Для отображения найденных дублирующих строк будет использоваться механизм Inspections. В качестве возможных исправлений пользователю будет предложено заменить строки на вызов соответствующего метода. Эквивалентность найденных дублирующих строк будет дополнительно проверяться с помощью соответствующих синтаксических деревьев.

===16.04.2012===
: Написан плагин для замены дублирующего кода вызовами соответствующих методов. В основе лежит поиск дубликатов IntelliJ Idea, так как при первом рассмотрении данный алгоритм находит гораздо более сложные дубликаты нежели Simian. В плагине используется механизм Inspections из IntelliJ Idea. При запуске анализатора кода находятся все public static методы, после чего каждый класс из предлагаемого скоупа анализируется на предмет наличия кода дублирующего найденные методы. Затем пользователю предлагается заменить дублирующий код на вызов соответствующих методов.

== Конфигуратор контейнеров AndroidVM ==
Руководитель: Кринкин К.В.

Команда:
* Владислав Савельев
* Дмитрий Шеставин
* Сергей Казенюк ([[AVMConf_Kazenyuk|отчёты]])

Отчёт:

13 марта. Встреча с разработчиками проекта. Поставлены задачи.
: Владислав: Послушал лекцию Кирилла Владимировича про QT. Подумал об интерфейсе конфигуратора. Написал очень черновой вариант, создающий и запускающий контейнеры. Начал смотреть видео лекций Кирилла Владимировича про QT и шаблон MVC, а также читать про QML.

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

10 апреля.
: Владислав: Переписал интерфейс с использованием «модели — представления — модели представления». Нарисовал иконок и спроектировал внешний вид приложения в перспективе для презентации Жени Баталова на предзащите.
: Добавил в программный интерфейс конфигуратора возможность для получения от устройства информации о списке контейнеров.

== Поиск дублирующих сообщений об ошибках ==

Команда:
* Ждан Анна
* Краско Евгений
* Кудинкин Алексей

Отчет 03.03 - 11.03
* Настроено окружение: проект в MPS, проект в IDEA
* Описана модель данных на языке dnq
* Написан rest api для админки и для добавления в базу новых сообщений об ошибках
* Написан парсер сообщений об ошибках
* Написана первая версия алгоритма сравнения сообщений об ошибках
* Написаны базовые классы для запуска тестов (различные заглушки для методов сервлет-контейнера, создание контекста для бинов и тп)
* Написаны тесты на парсер и алгоритм сравнения
* Частично написаны тесты на rest api (jmeter)

Отчет 11.03 - 18.03
* Улучшена первая версия алгоритма сравнения сообщений об ошибках
* Реализован альтернативный алгоритм сравнения сообщений об ошибках.
* Написаны тесты на оба алгоритма
* Реализован парсер сообщений об ошибках для языка C#. Парсер рассчитан на формат, принятый в Решарпере
* Написаны тесты на парсер
* В язык для рестовых тестов добавлена возможность проверять хереды респонса
* Добавлен ui для администрирования приложение
* Начата реализация JobProcessor'a, обрабатывающего сообщения об ошибках на предмет поиска дубликатов.

Отчет 19.03 - 25.03
* Написан классификатор, разбивающий сообщения об ошибках на кластеры.
* Добавлены новые возможности web-интерфейса для администрирования приложения.

Отчет 25.03 - 7.04
* Написан JobProcessor, разбивающий сообщения об ошибках на кластеры.
* Написаны тесты на JobProcessor
* Начата реализация интеграции приложения с Ютрэком
* Осуществлен переход на более новую версию библиотеки jersey

НИР

2012-04-24T07:04:12Z

Zalim: /* 12.03.2012 */

== Карта дорог ==
Руководитель: Лесин 
Ссылка на проект: 
Команда:
* Иванов Антон
* Сорокин Артем
* Кононенко Василий
Отчёт:
* 6.03.2012 - Первая встреча.
** Задачи на неделю:
** Кононенко: подготовить результаты прошлого семестра для коллективного проекта.
** Сорокин, Иванов: разобраться с базовыми алгоритмами поиска кратчайших путей.
* 20.03.2012 - Третья встреча.
** Обсудили структуру проекта. Определили "первые шаги" реализации.
** Задачи на неделю:
** Кононенко: Презентация (reaches), организация проекта, загрузка OSM формата, reaches preprocessing.
** Сорокин: создать wiki, github, разобраться с визуализатором и написать алг. Дейкстры, презентация?
** Иванов: web интерфейс (client-side), работающий сервер обрабатывающий запросы поиска евклидова расстояния между 2мя точками
** ?- допишите на какую тему презентации плиз.
* 27.03.2012
** Была проведена презентация Артема Сорокина по алгоритмам на графах (? уточни плз. название алгоритмов)
** Задачи на неделю:
** Иванов: закончить предыдущее задание. (ServerSide договорились делать на python'e, клиент уже почти написан на javascript'e с использованием openLayers api)
* 13.04.2012
** Задачи на неделю:
** Кононенко: реализация препроцессинга с Penalties и Shortcuts.
** Сорокин: Transit points (?)
** Иванов: Веб-сервер (?)

== MyFit ==
Руководитель: EMC 
Ссылка на проект:
* [http://osll.spb.ru/projects/myfit/ трекер]
* [http://code.google.com/p/myfit/ репозиторий]
Команда:
* Опейкин Александр
* Певзнер Алина
* Башоров Залим

==== 09.03.2012 ====
Выполнено 2 тестовых задания на Java и на GWT. 
Получены следующие задачи:
* [http://redmine.osll.spb.ru/issues/3155 Опейкин] (Готово)
* [http://redmine.osll.spb.ru/issues/3156 Певзнер] (Готово)
* [http://redmine.osll.spb.ru/issues/3157 Башоров] (Готово)

==== 12.03.2012 ====
Получены следующие задачи:
* [http://redmine.osll.spb.ru/issues/3175 Башоров] (Готово)
* [http://redmine.osll.spb.ru/issues/3177 Опейкин]
* [http://redmine.osll.spb.ru/issues/3176 Певзнер]

==== 27.03.2012 ====
Митинг в EMC -- обсудили текущие задачи и тестовые задания. 
Закоммитили рабочие версии кода по задачам, ожидаем ревью. 
(задачи: [http://redmine.osll.spb.ru/issues/3175 Башоров], [http://redmine.osll.spb.ru/issues/3177 Опейкин], [http://redmine.osll.spb.ru/issues/3176 Певзнер])

== GPU ==
Руководитель: Рубен Артурович Гиргидов 
Ссылка на проект: 
Команда:
* Коровин Алексей
* Лазарев Сергей
* Кормишин Сергей
Отчёт: 
*1я встреча нам были выданы вводные задачи:
** Разобраться с CUDA, установить и настроить окружение. Написать простенький алгоритм. (Коровин А.)
** Вспомнить "всё" о регулярных выражениях: какие бывают, как пишутся (Лазарев С.)
** Найти обработчики регулярных выражений (Matcher'ы), разобраться в их строении и принципе работы. (Кормишин С.)
*2я встреча:
** Обсудили наши предыдущие задания, расписали план выполнения проекта, цели и др.
** Выданы следующие задачи:
**# Реализовать обработчик РВ на Cuda для одной и n строк (Коровин А.)
**# Найти обработчики РВ на CPU на C++ и адаптировать его для n строк (Кормишин С.)
**# Реализовать обработчик РВ нa cuBLAS (Лазарев С.)
*3я встреча:
** Обсудили наши успехи, искали нужное представление автомата в виде матрицы для задачи реализации РВ на cuBLAS
** Решили какие паттерны РВ будут в бенчмарках
** По CUDA на неделю нужно было реализовать простейшую схему распараллеливания существующих реализаций регулярных выражений(Regexp9, Cuda paper code) и посмотреть на производительность.
*4я встреча:
** Портированная библиотека работать не хочет и разобраться без отладчика - очень трудно. Попытались настроить удалённую отладку на CUDA. Всё настроилось, но софт (Nsight) очень сырой, происходят непонятные ошибки и они нигде не журналируются и не объясняются. (Коровин А.)
*5я встреча:
** Реализован поиск с помощью регулярных выражений на основе матричных вычислений с использованием библиотеки cuBLAS. Пока сделан поиск в одной строке. Дальше надо распараллелить на несколько строк. (Лазарев С.)
** Портированная библиотека после длительной отладки начала матчить строку с регулярным выражением. Задача 1 выражение - 1 строка решена. Следующая задача задействовать все ядра видеокарты и научиться матчить N строк на одно регулярное выражение. (Коровин А.)
** Реализовн поиск с помощью re2 одной строки на одном ядре. Теперь нужно сделать для n строк на к ядрах.
*6я встреча:
** Был реализован матчинг N строк на 1 регулярное выражение на CUDA. К следующей встрече нужно попробовать оптимизировать программу. (Коровин А.)

== Syrop ==
Руководитель: Смаль Александр Владимирович 
Ссылка на проект: [https://github.com/avsmal/Syrop Syrop] 
Wiki проекта: [https://github.com/avsmal/Syrop/wiki Github] 
Команда:
* Кринкин Михаил
* Мартынов Семён
* Крашенинникова Ксения
* Великий Алексей
Отчёт:
* 27/feb/2011 - Первая встреча. Обсуждение цели проекта, способов реализации и внутри командного взаимодействия. Разделение задач. Создан репозиторий проекта на GitHub. Открытый вопрос - применение методологий разработки в проекте.
* 01/mar/2011 - Сode review.
* 05/mar/2011 - Введение договоренностей о code style, оформлении документации, спецификация на интерфейсы. Показ первого GUI, уточнение новых задач.
* 12/mar/2011 - Всё хорошо.
* 19/mar/2011 - Снова всё хорошо - работаем.
* 26/mar/2011 - Семен у нас большой шутник, см. список задач на трекере

== Дублирующий код ==
Руководитель: Иваницкий 
Ссылка на проект: http://code.google.com/p/aptu-practice-code-duplication/ 
Команда:
* Бандурин Дима (Project manager)
* Лепенькин Ярослав (Поиск дублирующего кода в C++)
* Фофанова Маша (Поиск дублирующего кода в Java)

Отчёт:

===28.02.2012 - Вводная встреча===
* Распределение ролей в команде
:Бандурин Дима (Project manager)
:Лепенькин Ярослав. Изучение специфики C++ для поиска дублирующего кода
:Фофанова Маша. Изучение специфики Java для поиск дублирующего кода.
* Уточнение функционала
* Организационные вопросы

===06.03.2012 - Контрольная встреча===
* Изучение существующих решений
** Michael Wise's Greedy String Tiling algorithm
** Преобразование Барроуза-Уиллера
** Алгоритм Рабина-Карпа
** Механизм использующийся в IntelliJ IDEA
[[Файл:Solutions.pdf|краткое описание]]

===15.03.2012===
В рамках НИР необходимо ответить на три вопроса.
* Научная новизна
** Список существующих решений для нашей задачи.(Ярослав)
** Способы оценки существующих решений.(Маша)
** Библиотеки, для проведения испытания (исследуемая выборка) (Дмитрий)
* Рабочий прототип. Решено делать плагин на базе IntelliJ IDEA. Функциональность плагина будет выяснена дальше.
* Этапы разработки
Решено разбить разработку на три этапа.
# Определение требований к разрабатываемой программе.(3 недели)
# Создание прототипа (2 недели)
# Разработка плагина (4 недели)
## Основная функциональность (2 недели)
## Тестирование и доведение (2 неделя)
## Документирование и создание презентационных материалов (1 неделя параллельно со вторым пунктом.)
Итого 9 недель. Предположительный срок завершения проекта : 21 мая

===21.03.2012===
*Возможные метрики для сравнения алгоритмов поиска дубликатов
** Время работы, используемая память, CPU
** Число правильно найденных дубликатов
*** Необходимо учитывать длину каждого дубликата, чтобы учитывать возможную вложенность. Длина дубликата определяется числом символов в нем.
** Число неправильно найденных дубликатов
*Метрики для алгоритмов замены дубликатов
** Объем кода, получающегося после замены найденных дубликатов на вызовы соответствующих методов
** Релевантность участка кода. Код считается иррелевантным, если его замена на предлагающийся код слишком трудоемка и не имеет смысла.
*Стоит также определить, на каких констукциях дубликатов алгоритмы работают лучше, а на каких хуже.

===6.04.2012===
*Исследованы IdeaCodeDuplicatePlugin, Digger, Simian и получены следующие метрики:
**Весовой коэффициент. Каждой строке присваивается вес, который соответствует числу программ, сказавших, что эта строка что-то дублирует.
***idea 23310
***digger 34839
***simian 26050
**Коэффициент по пересечению. Если строка встретилась в результате несколько раз, она учитывается несколько раз.
***idea 0.94
***digger 0.92
***simian 0.94
**Коэффициент по объединению. Если строка встретилась в результате несколько раз, она учитывается несколько раз.
***idea 0.86
***digger 0.12
***simian 0.18
*Попарные сравнения алгоритмов по тем же параметрам:
**digger | 1.12 | 0.55 | 29589
**simian | 1.03 | 0.76 | 21863

**idea | 1.0 | 0.93 |19123
**digger | 1.0 | 0.15 | 28710

**idea | 1.0 | 0.89 | 18060
**simian | 1.0 | 0.19 | 19921
* Решено использовать алгоритм из Simian.

===11.04.2012===
: Пишется прототип, в основе которого лежит Simian. Прототип будет представлять собой плагин к IntelliJ IDEA. Для отображения найденных дублирующих строк будет использоваться механизм Inspections. В качестве возможных исправлений пользователю будет предложено заменить строки на вызов соответствующего метода. Эквивалентность найденных дублирующих строк будет дополнительно проверяться с помощью соответствующих синтаксических деревьев.

===16.04.2012===
: Написан плагин для замены дублирующего кода вызовами соответствующих методов. В основе лежит поиск дубликатов IntelliJ Idea, так как при первом рассмотрении данный алгоритм находит гораздо более сложные дубликаты нежели Simian. В плагине используется механизм Inspections из IntelliJ Idea. При запуске анализатора кода находятся все public static методы, после чего каждый класс из предлагаемого скоупа анализируется на предмет наличия кода дублирующего найденные методы. Затем пользователю предлагается заменить дублирующий код на вызов соответствующих методов.

== Конфигуратор контейнеров AndroidVM ==
Руководитель: Кринкин К.В.

Команда:
* Владислав Савельев
* Дмитрий Шеставин
* Сергей Казенюк ([[AVMConf_Kazenyuk|отчёты]])

Отчёт:

13 марта. Встреча с разработчиками проекта. Поставлены задачи.
: Владислав: Послушал лекцию Кирилла Владимировича про QT. Подумал об интерфейсе конфигуратора. Написал очень черновой вариант, создающий и запускающий контейнеры. Начал смотреть видео лекций Кирилла Владимировича про QT и шаблон MVC, а также читать про QML.

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

10 апреля.
: Владислав: Переписал интерфейс с использованием «модели — представления — модели представления». Нарисовал иконок и спроектировал внешний вид приложения в перспективе для презентации Жени Баталова на предзащите.
: Добавил в программный интерфейс конфигуратора возможность для получения от устройства информации о списке контейнеров.

== Поиск дублирующих сообщений об ошибках ==

Команда:
* Ждан Анна
* Краско Евгений
* Кудинкин Алексей

Отчет 03.03 - 11.03
* Настроено окружение: проект в MPS, проект в IDEA
* Описана модель данных на языке dnq
* Написан rest api для админки и для добавления в базу новых сообщений об ошибках
* Написан парсер сообщений об ошибках
* Написана первая версия алгоритма сравнения сообщений об ошибках
* Написаны базовые классы для запуска тестов (различные заглушки для методов сервлет-контейнера, создание контекста для бинов и тп)
* Написаны тесты на парсер и алгоритм сравнения
* Частично написаны тесты на rest api (jmeter)

Отчет 11.03 - 18.03
* Улучшена первая версия алгоритма сравнения сообщений об ошибках
* Реализован альтернативный алгоритм сравнения сообщений об ошибках.
* Написаны тесты на оба алгоритма
* Реализован парсер сообщений об ошибках для языка C#. Парсер рассчитан на формат, принятый в Решарпере
* Написаны тесты на парсер
* В язык для рестовых тестов добавлена возможность проверять хереды респонса
* Добавлен ui для администрирования приложение
* Начата реализация JobProcessor'a, обрабатывающего сообщения об ошибках на предмет поиска дубликатов.

Отчет 19.03 - 25.03
* Написан классификатор, разбивающий сообщения об ошибках на кластеры.
* Добавлены новые возможности web-интерфейса для администрирования приложения.

Отчет 25.03 - 7.04
* Написан JobProcessor, разбивающий сообщения об ошибках на кластеры.
* Написаны тесты на JobProcessor
* Начата реализация интеграции приложения с Ютрэком
* Осуществлен переход на более новую версию библиотеки jersey

DevDays

2012-04-19T19:06:42Z

Zalim:

[https://twitter.com/#!/search/realtime/%23audd12%20OR%20%23AUDevDays #audd12 OR #AUDevDays]

==Проекты==
* [[Android_Accelerometer|Акселерометр в Android]]: Мария Фофанова, Алина Певзнер, Василий Кононенко, Дмитрий Бандурин
* [[Cheque_recognizer|Cheque (Receipt) recognizer]]: Дмитрий Шерставин, Залим Башоров, Семен Мартынов, Сергей Казенюк
* [[Android_Notification|Оповещения с Android]]: Михаил Кринкин, Алексей Коровин, Александр Опейкин, Сергей Лазарев, Ксения Крашенинникова
* [[Geo_Time_Tracker|Geo Time Tracker for Android]]: Евгений Краско, Алексей Кудинкин, Анна Ждан, Сорокин Артём, Ярослав Лепенькин
* <del>[[DJVU_Formatter|DJVU форматер под маленькие разрешения экрана]]: Василий Кононенко, Дмитрий Бандурин</del>
* [[GTD_tool|GTD(time managment) tool]]: Иванов Антон, Сергей Кормишин, Владислав Савельев

DevDays

2012-04-17T01:02:17Z

Zalim:

[https://twitter.com/#!/search/%23AUDevDays #AUDevDays]

==Проекты==
*
*
*
*

DevDays

2012-04-17T00:35:45Z

Zalim: Новая страница: «==Проекты== * * * *»

==Проекты==
*
*
*
*

SE Wiki

2012-04-17T00:26:30Z

Zalim: +DevDays

== Учебная информация ==

* [[Java | Java]]
* [[FunctionalProgramming | Функциональное программирование]]
* [[IntroductionToProgrammingLanguages | Теоретические основы языков программирования]]
* [[SoftwareDesign | Software design]]
* [[SE | Основы программной инженерии]]
* [[MachineLearning | Машинное обучение]]
* [[LinuxKernelProgramming | Программирование в ядре Linux]]
* [[NIR | Научно-исследовательская работа]]
* [[Теорема_Пойа | Теорема Пойа]]
* [[C++ | C++]]
* [[Алгоритмы_и_структуры_данных | Алгоритмы и структуры данных]]
* [[DevDays]]

== Архив за прошлые семестры ==
[[Осень_2011|Осенний семестр 2011]]

== Практики ==
* [[ Темы практик |Темы практик, весна 2011-го года]]
* [[Темы практик, 5SE, осень 2011-го года ]]

== Студенты ==
* [[2010|Набор 2010-го года (группа 604)]]
* [[2011|Набор 2011-го года]]
== Важные ссылки ==
Для 5-го курса:
* [http://code.google.com/p/spbau-cpp-2011/ cpp] - репозиторий для лабораторных по С++.
Для 6-го курса:
* [http://code.google.com/p/hpcource/ hpcource] - репозиторий для лабораторных по параллельному программированию.
* [http://code.google.com/p/mathvm/ mathvm] - репозиторий для лабораторных по виртуальным машинам.
* [http://code.google.com/p/spbau-network-2011/source/checkout spbau-network-2011] - репозиторий для лабораторных по сетевым технологиям.
Для всех:
* [http://code.google.com/p/aptu-os/source/checkout aptu-os] - репозиторий для лабораторных по операционным системам.

== Дополнительно ==
* [[Q&A]]
* [[Мероприятия]]

НИР

2012-03-31T15:34:36Z

Zalim: /* MyFit */

LinuxKernelProgramming

2012-03-24T19:06:13Z

Zalim: /* Подготовка к работе */

Лектор - Кринкин Кирилл Владимирович

== Подготовка к работе ==

Все работы рекомендуется проводить в виртуальном окружении, для этого можно использовать [https://www.virtualbox.org/wiki/Downloads VirtualBox].

Для сдачи работ должен использовать git на гуглкоде http://code.google.com/p/linux-kernel-course/

Для этого скачиваем ядро, откатываемся к заранее определённому коммиту (c579bc7e316e7e3f3b56df5e17f623325caa9783)
<source lang="bash">
git clone git://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git
git reset --hard c579bc7e316e7e3f3b56df5e17f623325caa9783
</source>
а в конце отсылаем результаты домашней работы в формате, полученном командой
<source lang="bash">
git format-patch c579bc7e316e7e3f3b56df5e17f623325caa9783
</source>

=== Установка OpenSSH-Server в VirtualBox ===
Для того, чтобы получить возможность пользоваться буфером обмена (вставлять текст в консоль) и не ставить VirtualBox Guest Additions, можно установить в виртуальную машину OpenSSH-Server, и подключаться к нему любым SSH клиентом.
Для этого необходимо добавить новую сетевую карту в виртуальную машину. Это делается в настройках, ДО ВКЛЮЧЕНИЯ виртуальной машины: в настройках нужно перейти на страницу с настройками сети, перейти на вкладку со вторым адаптером (первый адаптер используется виртуальной машиной для доступа к интернет через NAT) и выбрать подключение "Host-only adapter" (смотри пример на картинке).

[[Файл:HostOnlyAdapter.png|Настройка дополнительной сетевой карты в VirtualBox]]

Если VirtualBox выдает ошибку при выборе "Host-only Adapter", то вероятнее всего это связано с тем, что не установлен виртуальный адаптер. Добавить его можно в сетевых настройках VirtualBox (File->Preferences->Networks).

[[Файл:VBoxSettings-Network-2012.png|Добавление виртуального адаптера]]

Теперь необходимо включить на этой сетевой карте возможность получить IP адрес по DHCP. Для этого нужно выполнить следующие две команды (предполагается, что в системе до этого была только одна сетевая карта):
<source lang="bash">
echo 'allow-hotplug eth1' >> /etc/network/interfaces
echo 'iface eth1 inet dhcp' >> /etc/network/interfaces
</source>
и установить OpenSSH-Server
<source lang="bash">
apt-get install openssh-server
</source>
Теперь можно из основной системы произвести подключение к виртуальной. Для этого нужно использовать SSH-клиент, такой как [http://www.chiark.greenend.org.uk/~sgtatham/putty/download.html putty] которому нужно сообщить IP адрес виртуальной машины (его можно узнать командой ifconfig, и, скорее всего, это будет 192.168.56.101).

[[Файл:PuttyConnect.png|Использование Putty для SSH соединения]]

Важно помнить, что по умолчанию SSH не позволяет подключаться, используя учётную запись root. Если необходимы права суперпользователя, в начале подключитесь используя свою учётную запись на виртуальной машине (приняв перед этим сертификат безопасности), а потом используйте su.

Так же рекомендуется в подпункте Translation пункта Window указывать UTF-8 в качестве Character set translation on received data - в частности, это необходимо для правильного отображения Midnight Commander.

=== Сборка ядра 3.3.0-rc2 ===
Сборка ядра 3.3.0-rc2 (в соответствии с рекомендациями readme)
<source lang="bash">
wget https://www.kernel.org/pub/linux/kernel/v3.x/testing/linux-3.3-rc2.tar.bz2
su -c “apt-get install bzip2”
tar -xjf linux-3.3-rc2.tar.bz2
cd linux-3.3-rc2/
mkdir -p ~/build/linux-3.3-rc2
su -c “apt-get install libncurses5-dev”
make 0=~/build/linux-3.3-rc2 nconfig
make 0=~/build/linux-3.3-rc2
su -c “make 0=~/build/linux-3.3-rc2 modules_install install”
su -c “update-initramfs -c -k 3.3.0-rc2”
su -c “update-grub2”
shutdown -r now
</source>

=== Использование patch ===

== Создание модулей для ядра Linux ==

=== Введение ===

Некоторые отличия Ядра от программ, выполняемых в пространстве пользователя:
* Ядро LINUX пишется с расчётом на компилятор GNU C (разработчики ориентируются на стандарт ISO C99). В коде можно использовать ассемблерные вставки (директива ''asm()''), аннотацию ветвления (''likely()'' - более вероятная ветвь, ''unlikely()'' - менее вероятная) и весьма странный [http://www.kernel.org/doc/Documentation/CodingStyle кодстайл].
* Ядро не имеет доступа к стандартным библиотекам языка программирования C. Это сделано из соображений увеличения скорости выполнения и уменьшения объёма кода.
* Отсутствует защита памяти. Если обычная программа предпримет попытку некорректного обращения с памятью, то ядро сможет выгрузить такую программу, но если само ядро предпримет такую же попытку, то его будет некому проконтролировать. Так же важно помнить об отсутствии замещения страниц, т.е. каждому байту, используемому ядром, соответствует байт реальной физической памяти.
* В ядре используются только целочисленные вычисления. Это тоже сделано для ускорения работы, т.к. операции с плавающей точкой значительно более ресурсоёмки (в частности, активнее используются регистры CPU).
* Объём стека фиксирован, и обычно равен двум страницам памяти (8 Кбайт для x86, и 16 Кбайт для x64). По этой причине не рекомендуется использовать рекурсию.
* Важным требованием является переносимость - код должен компилироваться на максимально большом количестве систем.

Загружаемый объект ядра называется '''модулем'''.
Динамическая загрузка и выгрузка модулей по мере необходимости появилась благодаря Питеру Мак-Дональду и впервые была представлена в версии ядра 0.99. 
По своей структуре, модуль похож на обычную прогамму (так же имеется точка входа, и необходима компиляция в бинарный вид) но имеет прямой доступ к структурам и функциям ядра, в то время как обычные программы такой доступ могут получить только через обёртки.

=== Сборка модуля как отдельного объекта (Kernel object) ===

==== Код модуля ====
<source lang="c">
#include <linux/module.h> // Этот файл подключается в любом модуле по соглашению
#include <linux/kernel.h> // Содержит макросы для функции printk()
#include <linux/init.h> // Содержит определения макросов __init и __exit
void printHW(void) // Функция для вывода приветствия
{
printk("Hello, world\n"); // выводит сообщение на экран и в лог messages
}
EXPORT_SYMBOL(printHW); // Экспорт функций ядра - предоставляет доступ к функции другим модулям ядра
static int __init start(void) // Точка входа в модуль
{
printHW(); // Вызов функции
return 0; // в случае успешной загрузки возвращать нулевое значение
}
static void __exit stop(void) // Точка выхода
{
//printk("Module unloaded\n");
}
module_init(start);
module_exit(stop);
MODULE_LICENSE("GPL"); // Указывает на лицензию, под которой распространяется данный модуль
</source>
==== Сборка модуля (make) ====

Файл с кодом модуля (myModule.c) должен находиться в одной папке с make-фалом, в котом должно быть написано
obj-m += myModule.o
Тогда сборку модуля можно запустить командой
<source lang="bash">
make -C ./linux-3.3-rc2 SUBDIRS=$PWD modules
</source>
Внимание, замените путь к исходным кодам ядра на тот, куда вы извлекли содержимое архива linux-3.3-rc2.tar.bz2
В итоге должен получиться файл модуля myModule.ko

==== Загрузка модуля ====

Теперь полученный модуль можно загрузить (эта команда требует прав суперпользователя). Для этого используется команда
<source lang="bash">
insmod <имя модуля>
</source>
Список загруженных модулей хранится в /proc/modules (так что можно просмотреть этот файл cat /proc/modules) либо воспользоваться командой
<source lang="bash">
lsmod
</source>
Выгружать модуль можно командой (также требует прав суперпользователя)
<source lang="bash">
rmmod <имя модуля>
</source>

==== Примечания ====

Результат работы модуля выводится в /var/log/syslog, для его просмотра рекомендуется на отдельной консоли использовать
<source lang="bash">
tail -f /var/log/syslog
</source>

=== Сборка модуля вместе с ядром (Kbuild) ===

Модули для ядра можно собирать при помщи системы Kbuild. инструкции для сборки должны находиться в файле Kconfig.

Что бы подключить наш Kconfig, нужно в файл linux-3.3-rc2/arch/x86/Kconfig.debug добавить строчку (рекомендуется сделать это где-нибудь в начле файла, например 6-й строкой)
source "SPbAU/Kconfig"
Это позволит включать и отключать сборку наших модулей в меню '''Kernel hacking''', что в общем-то логично.

Важно заметить, что если в makefile-файлах относительный путь задавался от места размещения самого файла, то в Kconfig - относительные пути строятся от корневого каталога дерева исходных кодов (в данном случае, от linux-3.3-rc2).

Теперь, в дереве исходных кодов создаём каталог SPbAU, переносим туда (из предыдущего раздела) myModule.c и Makefile, а так же создаём файл Kconfig.

==== Файл Kconfig ====
Файл Kconfig должен содержать следующий код

<source lang="text">
config SPbAU_KERNEL
bool "Modules of students of the St. Petersburg Academic University of the Russian Academy of Sciences"
default y
---help---
SPbAU module list

config SPbAU_KERNEL_PRINTHW
tristate "The first module =)"
depends on SPbAU_KERNEL
default y
---help---
Function prints the text "Hello, world" to the syslog file.
</source>

В первой строке мы объявляем о том, что хотим сделать раздел SPbAU_KERNEL (очень важно следить, что бы имена не перекрывались, по этому рационально использовать свой префикс, типа SPbAU). Потом мы указываем что пункт является bool, т.е. способен принимать значения Y или N (подробнее о значениях будет сказано чуть ниже), и определено имя этого раздела в меню. По умолчанию, раздел отмечен как ИСТИНА. Далее идёт справачная информация, которая может занимать несколько строк (необходимо соблюдать отступ в 1 пробел от основной линии).

Потом мы описываем свой модуль. Ключевое слово ''tristate'' говорит о том, что этот пункт меню будет принимать одно из трёх возможных значения Y/M/N. Строчка depends on SPbAU_KERNEL показывает, что этот модуль не может быть установлен (и даже пункт не будет отображаться в меню), если в прерыщем пункте (SPbAU_KERNEL) стоит значение, отличное от истины. Это позволяет группировать различные элементы меню, уменьшая общую длинну списка.

Возможные значения изначального состояния пунктов меню:
*Y - модуль вкомпилируется в ядро (это произайдёт успешно, если не допускать перекрытия имён точек входа)
*M - модуль компилируется отдельным файлом (kernel object)
*N - модуль не вкомпилируется

Более подробно о языке формирования Kconfig файлов можно прочитать [http://kernel.org/doc/Documentation/kbuild/kconfig-language.txt здесь].

==== Файл Makefile ====

В Makefile необходимо добавить строчку
obj-$(SPbAU_KERNEL_PRINTHW) += SPbAU/

В файле Kconfig для мы указали tristate, т.е. пользователь может выбрать M и собрать отдельно модуль. Тогда команда ''make modules_install'' разместит .ko-файл в указанной директории (SPbAU), которая будет размещена по адресу /lib/modules/3.3.0-rc2/kernel/, т.е. общий путь к модулю будет /lib/modules/3.3.0-rc2/kernel/SPbAU/myModule.ko

==== Сборка ядра с модулем ====
Вернувшись в корень дерева исходных кодов, вызываем меню
<source lang="bash">
make menuconfig
</source>

Это приведёт к выводу на экран графического меню

[[Файл:Menuconfig.png‎|Вывод menuconfig]]

Нас интересует раздел Kernel hacking, куда мы положили свои команды сборки модуля

[[Файл:Menuconfig_Kernel_hacking.png‎|Вывод раздела Kernel hacking]]

Отметка на пункте "Modules of students of the St. Petersburg Academic University of the Russian Academy of Sciences" позволяет скрывать все наши модули (в данном случае модуль всего 1), а отметка на пункте "The first module =)" может принимать как значение, соответствующее сборке отдального модуля, так и сборки внутри ядра.

== Список литературы ==

* Разработка ядра Linux. Роберт Лав (http://www.ozon.ru/context/detail/id/2918313/)
* Ядро Linux. Д. Бовет, М. Чезати (http://www.ozon.ru/context/detail/id/3589107/)
* Linux Device Drivers, Джонатан Корбет, Алесандро Рубини, Грег Кроа-Хартман (http://lwn.net/Kernel/LDD3/) официаль

НИР

2012-03-13T21:01:20Z

Zalim: /* MyFit */

НИР

2012-03-13T06:50:22Z

Zalim: /* MyFit */

НИР

2012-03-13T06:44:32Z

Zalim: /* 9.03.2012 */

LinuxKernelProgramming

2012-03-06T23:29:27Z

Zalim: /* Установка OpenSSH-Server */

Лектор - Кринкин Кирилл Владимирович

== Лекции ==

== Программа курса ==

== Установка OpenSSH-Server ==
Для того, чтобы получить возможность пользоваться буфером обмена (вставлять текст в консоль) и не ставить VirtualBox Guest Additions, можно установить в виртуальную машину OpenSSH-Server, и подключаться к нему любым SSH клиентом.
Для этого необходимо добавить новую сетевую карту в виртуальную машину. Это делается в настройках, ДО ВКЛЮЧЕНИЯ виртуальной машины: в настройках нужно перейти на страницу с настройками сети, перейти на вкладку со вторым адаптером (первый адаптер используется виртуальной машиной для доступа к интернет через NAT) и выбрать подключение "Host-only adapter" (смотри пример на картинке).

[[Файл:HostOnlyAdapter.png|Настройка дополнительной сетевой карты в VirtualBox]]

Если VirtualBox выдает ошибку при выборе "Host-only Adapter", то вероятнее всего это связано с тем, что не установлен виртуальный адаптер. Добавить его можно в сетевых настройках VirtualBox (File->Preferences->Networks).

[[Файл:VBoxSettings-Network-2012.png|Добавление виртуального адаптера]]

Теперь необходимо включить на этой сетевой карте возможность получить IP адрес по DHCP. Для этого нужно выполнить следующие две команды (предполагается, что в системе до этого была только одна сетевая карта):
echo 'allow-hotplug eth1' >> /etc/network/interfaces
echo 'iface eth1 inet dhcp' >> /etc/network/interfaces
и установить OpenSSH-Server
apt-get install openssh-server

Теперь можно из основной системы произвести подключение к виртуальной. Для этого нужно использовать SSH-клиент, такой как [http://www.chiark.greenend.org.uk/~sgtatham/putty/download.html putty] которому нужно сообщить IP адрес виртуальной машины (его можно узнать командой ifconfig, и, скорее всего, это будет 192.168.56.101).

[[Файл:PuttyConnect.png|Использование Putty для SSH соединения]]

Важно помнить, что по умолчанию SSH не позволяет подключаться, используя учётную запись root. Если необходимы права суперпользователя, в начале подключитесь используя свою учётную запись на виртуальной машине (приняв перед этим сертификат безопасности), а потом используйте su.

Так же рекомендуется в подпункте Translation пункта Window указывать UTF-8 в качестве Character set translation on received data - в частности, это необходимо для правильного отображения Midnight Commander.

== Сборка ядра 3.3.0-rc2 ==
Сборка ядра 3.3.0-rc2 (в соответствии с рекомендациями readme)
wget https://www.kernel.org/pub/linux/kernel/v3.x/testing/linux-3.3-rc2.tar.bz2
su -c “apt-get install bzip2”
tar -xjf linux-3.3-rc2.tar.bz2
cd linux-3.3-rc2/
mkdir -p ~/build/linux-3.3-rc2
su -c “apt-get install libncurses5-dev”
make 0=~/build/linux-3.3-rc2 nconfig
make 0=~/build/linux-3.3-rc2
su -c “make 0=~/build/linux-3.3-rc2 modules_install install”
su -c “update-initramfs -c -k 3.3.0-rc2”
su -c “update-grub2”
shutdown -r now

== Написание модулей ==

=== Введение ===

Некоторые отличия Ядра от программ, выполняемых в пространстве пользователя:
* Ядро LINUX пишется с расчётом на компилятор GNU C (разработчики ориентируются на стандарт ISO C99). В коде можно использовать ассемблерные вставки (директива ''asm()''), аннотацию ветвления (''likely()'' - более вероятная ветвь, ''unlikely()'' - менее вероятная) и весьма странный [http://www.kernel.org/doc/Documentation/CodingStyle кодстайл].
* Ядро не имеет доступа к стандартным библиотекам языка программирования C. Это сделано из соображений увеличения скорости выполнения и уменьшения объёма кода.
* Отсутствует защита памяти. Если обычная программа предпримет попытку некорректного обращения с памятью, то ядро сможет выгрузить такую программу, но если само ядро предпримет такую же попытку, то его будет некому проконтролировать. Так же важно помнить об отсутствии замещения страниц, т.е. каждому байту, используемому ядром, соответствует байт реальной физической памяти.
* В ядре используются только целочисленные вычисления. Это тоже сделано для ускорения работы, т.к. операции с плавающей точкой значительно более ресурсоёмки (в частности, активнее используются регистры CPU).
* Объём стека фиксирован, и обычно равен двум страницам памяти (8 Кбайт для x86, и 16 Кбайт для x64). По этой причине не рекомендуется использовать рекурсию.
* Важным требованием является переносимость - код должен компилироваться на максимально большом количестве систем.

Загружаемый объект ядра называется '''модулем'''.
Динамическая загрузка и выгрузка модулей по мере необходимости появилась благодаря Питеру Мак-Дональду и впервые была представлена в версии ядра 0.99. 
По своей структуре, модуль похож на обычную прогамму (так же имеется точка входа, и необходима компиляция в бинарный вид) но имеет прямой доступ к структурам и функциям ядра, в то время как обычные программы такой доступ могут получить только через обёртки.

=== Код модуля ===
<source lang="c">
#include <linux/module.h> // Этот файл подключается в любом модуле по соглашению
#include <linux/kernel.h> // Содержит макросы для функции printk()
#include <linux/init.h> // Содержит определения макросов __init и __exit
void printHW(void) // Функция для вывода приветствия
{
printk("Hello, world\n"); // выводит сообщение на экран и в лог messages
}
EXPORT_SYMBOL(printHW); // Экспорт функций ядра - предоставляет доступ к функции другим модулям ядра
static int __init start(void) // Точка входа в модуль
{
printHW(); // Вызов функции
return 0; // в случае успешной загрузки возвращать нулевое значение
}
static void __exit stop(void) // Точка выхода
{
//printk("Module unloaded\n");
}
module_init(start);
module_exit(stop);
MODULE_LICENSE("GPL"); // Указывает на лицензию, под которой распространяется данный модуль
</source>
=== Сборка модуля ===

Файл с кодом модуля (myModule.c) должен находиться в одной папке с make-фалом, в котом должно быть написано
obj-m += myModule.o
Тогда сборку модуля можно запустить командой
make -C ./linux-3.3-rc2 SUBDIRS=$PWD modules
Внимание, замените путь к исходным кодам ядра на тот, куда вы извлекли содержимое архива linux-3.3-rc2.tar.bz2
В итоге должен получиться файл модуля myModule.ko

=== После сборки модуля ===

Теперь полученный модуль можно загрузить (эта команда требует прав суперпользователя). Для этого используется команда
insmod <имя модуля>
Список загруженных модулей хранится в /proc/modules, так что можно просмотреть этот файл
cat /proc/modules
или воспользоваться командой
lsmod
Выгружать модуль можно командой (также требует прав суперпользователя)
rmmod <имя модуля>

== Программа курса ==

== Список литературы ==

* Разработка ядра Linux. Роберт Лав (http://www.ozon.ru/context/detail/id/2918313/)
* Ядро Linux. Д. Бовет, М. Чезати (http://www.ozon.ru/context/detail/id/3589107/)
* Linux Device Drivers, Джонатан Корбет, Алесандро Рубини, Грег Кроа-Хартман (http://lwn.net/Kernel/LDD3/) официаль

Файл:VBoxSettings-Network-2012.png

2012-03-06T23:22:34Z

Zalim:

IntroductionToProgrammingLanguages

2012-02-27T22:44:01Z

Zalim: /* Задание №3 */

'''Введение в языки программирования'''

Лектор - Дмитрий Юрьевич [http://www.matmex.spb.ru/photoalbum/person_teachers_BulychevDY_1.html Булычев]

[https://docs.google.com/spreadsheet/ccc?key=0ApYxPEC9C_QXdC00UkVJekxYV0pYYVAxTmFXUkt6SVE Учёт посещаемости занятий]

[https://docs.google.com/spreadsheet/ccc?key=0ApYxPEC9C_QXdE05Q09iWlRqRzJ3d1FwTlJRSEkxbFE Учёт сдачи домашних заданий]

== Лекции ==

* [http://code.google.com/p/aptu-tex/source/browse/formallang/les1/les.tex Лекция №1] 10.02.2012
* 17.02.2012
В семантике ошибка: правило для переменной вместо
[x](s)=s(x)
читать как
[x](s)=[s(x)](s).
* 24.02.2012

== Домашние задания ==

=== Задание №1 ===
Cрок сдачи '''17 февраля 2011'''

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

int exp (int x, int n) {
int y = 1;
while (n) {
if (n % 2) y *= x;
n /= 2;
x *= x;
}
return y;
}

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

=== Задание №2 ===
Cрок сдачи '''24 февраля 2011'''

Написать принтер, который по абстрактному синтаксическому дереву программы печатает её представление в конкретном синтаксисе (который мы обсуждали) и интерпретатор (который вычисляет значение выражения в данном состоянии).

Описание конкретного синтаксиса для представления программ на языке L:
# Программа представляется в виде последовательности слов. Разделителем служит перевод строки.
# Пусть E --- выражение, а |E| --- представление этого выражения в данном конкретном синтаксисе. Тогда:
#* переменная v представляется в виде "x" v (то есть символ x (как терминал), и собственно имя переменной на следующей строчке).
#* функция {x -> E} представляется в виде "f" x |E|
#* применение функции F E представляется в виде "a" |E| |F|
#* условное выражение C ? T : E представляется в виде "?" |C| |T| |E|
#* бинарная операция X o Y представляется в виде "@" |X| |Y|
#* константа i представляется в виде "!" i
# Контекст (список определений name1=expr1, name2=expr2 и т.д.) представляется как последовательность name1 |expr1| name2 |expr2| и т.д.
# Программа (то есть выражение E в контексте C) представляется как последовательность |C| ";" |E|.
# Все реализации д.з. №2 должны уметь читать файл, содержащий описание программы в таком синтаксисе (иначе невозможно ничего проверить).

Пример 1. Выражение
{x -> {y -> x + y}} 1 2
в данном конкретном синтаксисе выглядит так:
a
a
f
x
f
y
@
+
x
x
x
y
!
1
!
2

Пример 2. Программа
fact = {n -> n ? n * (fact n-1) : 1};
fact 4
будет представлена как
fact
f
$0
?
x
$0
@
*
x
$0
a
x
fact
@
-
x
$0
!
1
!
1
;
a
x
fact
!
4

[http://narod.ru/disk/42015820001.bfed0d23b277fa721f7e86f27dc45e3d/monoMix.opt.html Программа], которая воспринимает программы в языке L в обычном синтаксисе, и печатает их представление в данной упрощенной форме. Бинарник для x86-linux, -h --- помощь.

=== Задание №3 ===
Желаемый срок сдачи '''26 февраля 2011'''

# Написать порождающую грамматику для языка над алфавитом {a, b, c}, состоящего из всех слов, в которых количество букв a, b и c одинаково.
# Написать порождающую грамматику для языка над алфавитом {0, 1}, состоящего из всех слов, в которых не встречается две единицы подряд.
# Написать порождающую грамматику для языка над алфавитом {0, 1, *}, состоящего из всех слов вида sas, где s --- непустая строка нулей и единиц любой длины, а a --- непустая строка из звездочек любой длины.
# Написать порождающую грамматику для языка над алфавитом {a, b}, состоящего из всех вида a^nb^m, где n <> m.
# Написать порождающую грамматику для языка над алфавитом {a, b}, состоящего из всех слов, в которых количество букв a в два раза больше, чем количество букв b.
# Правда ли, что любой рекурсивный язык контекстно-зависим (обратное, как известно, верно)?
# Написать реализацию построения НКА по регулярной грамматике; написать интерпретатор этого автомата, который проверяет принадлежность заданного слова языку, и принтер, который печатает граф переходов автомата в формате .dot пакета graphviz.
# Написать грамматику для порождения выражений в алфавите {x, +, *, (, )}, где x играет роль операндов, * и + --- левоассоциативные операции (то есть E+F+G означает ((E+F)+G)), операция * связывает операнды сильнее, чем + (то есть E+F*G означает E+(F*G)), причем порождаемые выражения НЕ ДОЛЖНЫ содержать ненужных скобок (а именно, например, выражение x+(x*x) не должно порождаться)
----
[http://bashor.github.com/GrGen/GrGen.html Генератор] Залима для проверки 1-5 пунктов.
Коментарии:
T -- терминальные символы. Пробелы и запятые игнорируются, т.е. abc == a b c == a b, c
Все остальные символы считаются нетерминальными
R -- правила преобразования вида: From : to
пробелы и пустые строки игнорируются.
Кроме того, можно указать свой чекер на JavaScript. Например:
1) return countChar(st, 'a') == countChar(st, 'b') && countChar(st, 'a') == countChar(st, 'c');
2) return st.indexOf("11") == -1;
3) var matches = /^([10]+)[*]+([10]+)$/g.exec(st);
return matches[1] == matches[2] && matches.length == 3;
4) var matches = /^(a*)(b*)$/g.exec(st);
return matches.length == 3 && matches[1].length != matches[2].length;
5) return countChar(st, 'a') == countChar(st, 'b') * 2;
init -- (пере)инициализация
step -- выполнение "одного шага"

== Программа курса ==

# Языки программирования, синтаксис, семантика, прагматика. Когнитивные особенности человеческого мышления и их влияние на развитие языков программирования.
# Языки программирования в ретроспективе. Процедурное, объектно-ориентированное, логическое и функциональное программирование. Предметно-ориентированные языки. Языки вне классификации.
# Абстрактный и конкретный синтаксис. Статическая и динамическая семантика. Компиляция и интерпретация. Проекции Футамуры-Ершова.
# Генеративный и аналитический подходы к описанию синтаксиса. Формальные грамматики, иерархия Хомского.
# Регулярные языки и конечные автоматы. Применение регулярных выражений в народном хозяйстве (grep/sed/awk) и для лексического анализа (lex/flex). Отсутствие бесконтекстной лексики в реальных языках программирования.
# Контекстно-свободные грамматики. Нормальные формы Хомского и Грейбах. Алгоритмы Эрли и Кока-Янгера-Касами. Неконтекстосвободность реальных языков программирования.
# Нисходящий анализ. Возврат и заглядывание вперед. Класс языков LL(k). Рекурсивный спуск, магазинные автоматы, парсер-комбинаторы, PEG, "скаредный" разбор. GLL. Инструменты нисходящего анализа (Parsec, ANTLR и пр.)
# Восходящий анализ, классы LR(k) и LALR(k). GLR. Инструменты восходящего анализа (yacc/bison).
# Двухуровневые и атрибутные грамматики, вопросы применения на практике.
# Идентификация. Область видимости и область действия. Статическое и динамическое, раннее и позднее связывание.
# Энергичность и ленивость. Call-by-name, call-by-value, call-by-reference.
# Строгость, чистота, прозрачность по ссылкам.
# Языки с типами и языки без типов. Статическая и динамическая типизация.
# Номинальная и структурная эквивалентность типов. Простейшие конструкторы.
# Типы с кванторами и что они означают. Универсальные и экзистенциальные типы.
# Subtyping. Структурный и номинальный subtyping.
# Динамическая семантика языков. Операционная семантика большого и малого шага.
# Денотационный подход к описанию семантики.
# Аксиоматическая семантика. Верификация программ. Design by contract.
# Когерентность языков программирования и машинных архитектур. Языково-специфичные архитектуры, виртуальные машины и JIT-компиляция.
#<nowiki>*</nowiki> Структура рабочей программы. Код, данные, библиотеки, поддержка времени исполнения.
#<nowiki>*</nowiki> Задача генерации кода. Генерация кода путем интерпретации.
#<nowiki>*</nowiki> Восходящее переписывание деревьев и динамическое программирование (BURS).
#<nowiki>*</nowiki> Алгоритмы распределения регистров. Распределение регистров и раскраска графов.
#<nowiki>*</nowiki> Параллелизм на уровне инструкций. Планирование инструкций.
#<nowiki>*</nowiki> Анализ потока управления. Глубинное остовное дерево, доминирование, анализ циклической структуры программ. Сводимость. Устранение недостижимого кода, оптимальная линеаризация.
#<nowiki>*</nowiki> Анализ потока данных. Полурешеточная модель. RD, LV, AE, UEU. Устраненние мертвого кода, экономия общих подвыражений, понижение силы операций, чистка циклов.

''<nowiki>* - вопросы будут рассмотрены при наличии времени.</nowiki>''

== Список литературы ==
# S.Muchnik. Advanced Compiler Design & Implementation. Academic Press, Morgan Kaufmann, 1998.
# А.Ахо, Р.Сети, С.Ульман. Компиляторы: принципы, технологии, инструменты. Вильямс, 2003.
# А.Ахо, С.Ульман. Теория синтаксического анализа, перевода и компиляции. Том 1. М., "Мир", 1978.
# F.Nielsen. Principles of Program Analysis. Springer, 2005.
# F.Nielse, H-R.Nielsen. Semantics with Applications. Wiley Professional Computing, 1992.
# B.Pierce. Types and Programming Languages. MIT Press, 2002.
# T.Пратт. Языки программирования: разработка и реализация. 1978.
# Б.К.Мартыненко. Языки и трансляции. Из-во СПбГУ, 2008.

== Список групп для выполнения задач ==

# [Haskell] Мартынов Семён, Башоров Залим, Казенюк Сергей, Витвицкий Александр, Тугарёв Денис.
# Кринкин Михаил, Лазарев Сергей, Фофанова Мария, Бандурин Дмитрий, Ждан Анна
# [JAVA] Сорокин Артём, Коровин Алексей, Опейкин Александр, Шеставин Дмитрий, Владислав Савельев
# [C++] Иванов Антон, Крашенинникова Ксения, Лепенькин Ярослав, Диевский Алексей, Кормишин Сергей
# Певзнер Алина, Князев Сергей
# [JAVA] Великий Алексей.

''<nowiki>* Не более 5 человек в каждой группе; старайтесь выравнивать группы по уровню, и не повторяться в выборе языков.</nowiki>''

== Полезные ссылки ==

* [http://caml.inria.fr/ocaml/release.en.html Latest OCaml release]
* [http://caml.inria.fr/pub/docs/manual-ocaml/index.html Documentation and user’s manual]

IntroductionToProgrammingLanguages

2012-02-27T22:21:50Z

Zalim: /* Задание №3 */

IntroductionToProgrammingLanguages

2012-02-27T21:30:14Z

Zalim: /* Задание №3 */

'''Введение в языки программирования'''

Лектор - Дмитрий Юрьевич [http://www.matmex.spb.ru/photoalbum/person_teachers_BulychevDY_1.html Булычев]

[https://docs.google.com/spreadsheet/ccc?key=0ApYxPEC9C_QXdC00UkVJekxYV0pYYVAxTmFXUkt6SVE Учёт посещаемости занятий]

[https://docs.google.com/spreadsheet/ccc?key=0ApYxPEC9C_QXdE05Q09iWlRqRzJ3d1FwTlJRSEkxbFE Учёт сдачи домашних заданий]

== Лекции ==

* [http://code.google.com/p/aptu-tex/source/browse/formallang/les1/les.tex Лекция №1] 10.02.2012
* 17.02.2012
В семантике ошибка: правило для переменной вместо
[x](s)=s(x)
читать как
[x](s)=[s(x)](s).
* 24.02.2012

== Домашние задания ==

=== Задание №1 ===
Cрок сдачи '''17 февраля 2011'''

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

int exp (int x, int n) {
int y = 1;
while (n) {
if (n % 2) y *= x;
n /= 2;
x *= x;
}
return y;
}

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

=== Задание №2 ===
Cрок сдачи '''24 февраля 2011'''

Написать принтер, который по абстрактному синтаксическому дереву программы печатает её представление в конкретном синтаксисе (который мы обсуждали) и интерпретатор (который вычисляет значение выражения в данном состоянии).

Описание конкретного синтаксиса для представления программ на языке L:
# Программа представляется в виде последовательности слов. Разделителем служит перевод строки.
# Пусть E --- выражение, а |E| --- представление этого выражения в данном конкретном синтаксисе. Тогда:
#* переменная v представляется в виде "x" v (то есть символ x (как терминал), и собственно имя переменной на следующей строчке).
#* функция {x -> E} представляется в виде "f" x |E|
#* применение функции F E представляется в виде "a" |E| |F|
#* условное выражение C ? T : E представляется в виде "?" |C| |T| |E|
#* бинарная операция X o Y представляется в виде "@" |X| |Y|
#* константа i представляется в виде "!" i
# Контекст (список определений name1=expr1, name2=expr2 и т.д.) представляется как последовательность name1 |expr1| name2 |expr2| и т.д.
# Программа (то есть выражение E в контексте C) представляется как последовательность |C| ";" |E|.
# Все реализации д.з. №2 должны уметь читать файл, содержащий описание программы в таком синтаксисе (иначе невозможно ничего проверить).

Пример 1. Выражение
{x -> {y -> x + y}} 1 2
в данном конкретном синтаксисе выглядит так:
a
a
f
x
f
y
@
+
x
x
x
y
!
1
!
2

Пример 2. Программа
fact = {n -> n ? n * (fact n-1) : 1};
fact 4
будет представлена как
fact
f
$0
?
x
$0
@
*
x
$0
a
x
fact
@
-
x
$0
!
1
!
1
;
a
x
fact
!
4

[http://narod.ru/disk/42015820001.bfed0d23b277fa721f7e86f27dc45e3d/monoMix.opt.html Программа], которая воспринимает программы в языке L в обычном синтаксисе, и печатает их представление в данной упрощенной форме. Бинарник для x86-linux, -h --- помощь.

=== Задание №3 ===
Желаемый срок сдачи '''26 февраля 2011'''

# Написать порождающую грамматику для языка над алфавитом {a, b, c}, состоящего из всех слов, в которых количество букв a, b и c одинаково.
# Написать порождающую грамматику для языка над алфавитом {0, 1}, состоящего из всех слов, в которых не встречается две единицы подряд.
# Написать порождающую грамматику для языка над алфавитом {0, 1, *}, состоящего из всех слов вида sas, где s --- непустая строка нулей и единиц любой длины, а a --- непустая строка из звездочек любой длины.
# Написать порождающую грамматику для языка над алфавитом {a, b}, состоящего из всех вида a^nb^m, где n <> m.
# Написать порождающую грамматику для языка над алфавитом {a, b}, состоящего из всех слов, в которых количество букв a в два раза больше, чем количество букв b.
# Правда ли, что любой рекурсивный язык контекстно-зависим (обратное, как известно, верно)?
# Написать реализацию построения НКА по регулярной грамматике; написать интерпретатор этого автомата, который проверяет принадлежность заданного слова языку, и принтер, который печатает граф переходов автомата в формате .dot пакета graphviz.
# Написать грамматику для порождения выражений в алфавите {x, +, *, (, )}, где x играет роль операндов, * и + --- левоассоциативные операции (то есть E+F+G означает ((E+F)+G)), операция * связывает операнды сильнее, чем + (то есть E+F*G означает E+(F*G)), причем порождаемые выражения НЕ ДОЛЖНЫ содержать ненужных скобок (а именно, например, выражение x+(x*x) не должно порождаться)
----
[http://bashor.github.com/GrGen/GrGen.html Генератор] Залима для проверки 1-5 пунктов.
Коментарии:
T -- терминальные символы. Пробелы и запятые игнорируются, т.е. abc == a b c == a b, c
Все остальные символы считаются нетерминальными
R -- правила преобразования вида: From : to
пробелы и пустые строки игнорируются.
Кроме того, можно указать свой чекер на JavaScript. Например:
1) return countChar(st, 'a') == countChar(st, 'b') && countChar(st, 'a') == countChar(st, 'c');
2) return st.indexOf("11") == -1;
3) var matches = /^([10]+)[*]+([10]+)$/g.exec(st);
return matches[1] == matches[2] && matches.length == 3;
4) return countChar(st, 'a') != countChar(st, 'b');
5) return countChar(st, 'a') == countChar(st, 'b') * 2;
init -- (пере)инициализация
step -- выполнение "одного шага"

== Программа курса ==

# Языки программирования, синтаксис, семантика, прагматика. Когнитивные особенности человеческого мышления и их влияние на развитие языков программирования.
# Языки программирования в ретроспективе. Процедурное, объектно-ориентированное, логическое и функциональное программирование. Предметно-ориентированные языки. Языки вне классификации.
# Абстрактный и конкретный синтаксис. Статическая и динамическая семантика. Компиляция и интерпретация. Проекции Футамуры-Ершова.
# Генеративный и аналитический подходы к описанию синтаксиса. Формальные грамматики, иерархия Хомского.
# Регулярные языки и конечные автоматы. Применение регулярных выражений в народном хозяйстве (grep/sed/awk) и для лексического анализа (lex/flex). Отсутствие бесконтекстной лексики в реальных языках программирования.
# Контекстно-свободные грамматики. Нормальные формы Хомского и Грейбах. Алгоритмы Эрли и Кока-Янгера-Касами. Неконтекстосвободность реальных языков программирования.
# Нисходящий анализ. Возврат и заглядывание вперед. Класс языков LL(k). Рекурсивный спуск, магазинные автоматы, парсер-комбинаторы, PEG, "скаредный" разбор. GLL. Инструменты нисходящего анализа (Parsec, ANTLR и пр.)
# Восходящий анализ, классы LR(k) и LALR(k). GLR. Инструменты восходящего анализа (yacc/bison).
# Двухуровневые и атрибутные грамматики, вопросы применения на практике.
# Идентификация. Область видимости и область действия. Статическое и динамическое, раннее и позднее связывание.
# Энергичность и ленивость. Call-by-name, call-by-value, call-by-reference.
# Строгость, чистота, прозрачность по ссылкам.
# Языки с типами и языки без типов. Статическая и динамическая типизация.
# Номинальная и структурная эквивалентность типов. Простейшие конструкторы.
# Типы с кванторами и что они означают. Универсальные и экзистенциальные типы.
# Subtyping. Структурный и номинальный subtyping.
# Динамическая семантика языков. Операционная семантика большого и малого шага.
# Денотационный подход к описанию семантики.
# Аксиоматическая семантика. Верификация программ. Design by contract.
# Когерентность языков программирования и машинных архитектур. Языково-специфичные архитектуры, виртуальные машины и JIT-компиляция.
#<nowiki>*</nowiki> Структура рабочей программы. Код, данные, библиотеки, поддержка времени исполнения.
#<nowiki>*</nowiki> Задача генерации кода. Генерация кода путем интерпретации.
#<nowiki>*</nowiki> Восходящее переписывание деревьев и динамическое программирование (BURS).
#<nowiki>*</nowiki> Алгоритмы распределения регистров. Распределение регистров и раскраска графов.
#<nowiki>*</nowiki> Параллелизм на уровне инструкций. Планирование инструкций.
#<nowiki>*</nowiki> Анализ потока управления. Глубинное остовное дерево, доминирование, анализ циклической структуры программ. Сводимость. Устранение недостижимого кода, оптимальная линеаризация.
#<nowiki>*</nowiki> Анализ потока данных. Полурешеточная модель. RD, LV, AE, UEU. Устраненние мертвого кода, экономия общих подвыражений, понижение силы операций, чистка циклов.

''<nowiki>* - вопросы будут рассмотрены при наличии времени.</nowiki>''

== Список литературы ==
# S.Muchnik. Advanced Compiler Design & Implementation. Academic Press, Morgan Kaufmann, 1998.
# А.Ахо, Р.Сети, С.Ульман. Компиляторы: принципы, технологии, инструменты. Вильямс, 2003.
# А.Ахо, С.Ульман. Теория синтаксического анализа, перевода и компиляции. Том 1. М., "Мир", 1978.
# F.Nielsen. Principles of Program Analysis. Springer, 2005.
# F.Nielse, H-R.Nielsen. Semantics with Applications. Wiley Professional Computing, 1992.
# B.Pierce. Types and Programming Languages. MIT Press, 2002.
# T.Пратт. Языки программирования: разработка и реализация. 1978.
# Б.К.Мартыненко. Языки и трансляции. Из-во СПбГУ, 2008.

== Список групп для выполнения задач ==

# [Haskell] Мартынов Семён, Башоров Залим, Казенюк Сергей, Витвицкий Александр, Тугарёв Денис.
# Кринкин Михаил, Лазарев Сергей, Фофанова Мария, Бандурин Дмитрий, Ждан Анна
# [JAVA] Сорокин Артём, Коровин Алексей, Опейкин Александр, Шеставин Дмитрий, Владислав Савельев
# [C++] Иванов Антон, Крашенинникова Ксения, Лепенькин Ярослав, Диевский Алексей, Кормишин Сергей
# Певзнер Алина, Князев Сергей
# [JAVA] Великий Алексей.

''<nowiki>* Не более 5 человек в каждой группе; старайтесь выравнивать группы по уровню, и не повторяться в выборе языков.</nowiki>''

== Полезные ссылки ==

* [http://caml.inria.fr/ocaml/release.en.html Latest OCaml release]
* [http://caml.inria.fr/pub/docs/manual-ocaml/index.html Documentation and user’s manual]

IntroductionToProgrammingLanguages

2012-02-27T21:04:03Z

Zalim: /* Задание №3 */

'''Введение в языки программирования'''

Лектор - Дмитрий Юрьевич [http://www.matmex.spb.ru/photoalbum/person_teachers_BulychevDY_1.html Булычев]

[https://docs.google.com/spreadsheet/ccc?key=0ApYxPEC9C_QXdC00UkVJekxYV0pYYVAxTmFXUkt6SVE Учёт посещаемости занятий]

[https://docs.google.com/spreadsheet/ccc?key=0ApYxPEC9C_QXdE05Q09iWlRqRzJ3d1FwTlJRSEkxbFE Учёт сдачи домашних заданий]

== Лекции ==

* [http://code.google.com/p/aptu-tex/source/browse/formallang/les1/les.tex Лекция №1] 10.02.2012
* 17.02.2012
В семантике ошибка: правило для переменной вместо
[x](s)=s(x)
читать как
[x](s)=[s(x)](s).
* 24.02.2012

== Домашние задания ==

=== Задание №1 ===
Cрок сдачи '''17 февраля 2011'''

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

int exp (int x, int n) {
int y = 1;
while (n) {
if (n % 2) y *= x;
n /= 2;
x *= x;
}
return y;
}

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

=== Задание №2 ===
Cрок сдачи '''24 февраля 2011'''

Написать принтер, который по абстрактному синтаксическому дереву программы печатает её представление в конкретном синтаксисе (который мы обсуждали) и интерпретатор (который вычисляет значение выражения в данном состоянии).

Описание конкретного синтаксиса для представления программ на языке L:
# Программа представляется в виде последовательности слов. Разделителем служит перевод строки.
# Пусть E --- выражение, а |E| --- представление этого выражения в данном конкретном синтаксисе. Тогда:
#* переменная v представляется в виде "x" v (то есть символ x (как терминал), и собственно имя переменной на следующей строчке).
#* функция {x -> E} представляется в виде "f" x |E|
#* применение функции F E представляется в виде "a" |E| |F|
#* условное выражение C ? T : E представляется в виде "?" |C| |T| |E|
#* бинарная операция X o Y представляется в виде "@" |X| |Y|
#* константа i представляется в виде "!" i
# Контекст (список определений name1=expr1, name2=expr2 и т.д.) представляется как последовательность name1 |expr1| name2 |expr2| и т.д.
# Программа (то есть выражение E в контексте C) представляется как последовательность |C| ";" |E|.
# Все реализации д.з. №2 должны уметь читать файл, содержащий описание программы в таком синтаксисе (иначе невозможно ничего проверить).

Пример 1. Выражение
{x -> {y -> x + y}} 1 2
в данном конкретном синтаксисе выглядит так:
a
a
f
x
f
y
@
+
x
x
x
y
!
1
!
2

Пример 2. Программа
fact = {n -> n ? n * (fact n-1) : 1};
fact 4
будет представлена как
fact
f
$0
?
x
$0
@
*
x
$0
a
x
fact
@
-
x
$0
!
1
!
1
;
a
x
fact
!
4

[http://narod.ru/disk/42015820001.bfed0d23b277fa721f7e86f27dc45e3d/monoMix.opt.html Программа], которая воспринимает программы в языке L в обычном синтаксисе, и печатает их представление в данной упрощенной форме. Бинарник для x86-linux, -h --- помощь.

=== Задание №3 ===
Желаемый срок сдачи '''26 февраля 2011'''

# Написать порождающую грамматику для языка над алфавитом {a, b, c}, состоящего из всех слов, в которых количество букв a, b и c одинаково.
# Написать порождающую грамматику для языка над алфавитом {0, 1}, состоящего из всех слов, в которых не встречается две единицы подряд.
# Написать порождающую грамматику для языка над алфавитом {0, 1, *}, состоящего из всех слов вида sas, где s --- непустая строка нулей и единиц любой длины, а a --- непустая строка из звездочек любой длины.
# Написать порождающую грамматику для языка над алфавитом {a, b}, состоящего из всех вида a^nb^m, где n <> m.
# Написать порождающую грамматику для языка над алфавитом {a, b}, состоящего из всех слов, в которых количество букв a в два раза больше, чем количество букв b.
# Правда ли, что любой рекурсивный язык контекстно-зависим (обратное, как известно, верно)?
# Написать реализацию построения НКА по регулярной грамматике; написать интерпретатор этого автомата, который проверяет принадлежность заданного слова языку, и принтер, который печатает граф переходов автомата в формате .dot пакета graphviz.
# Написать грамматику для порождения выражений в алфавите {x, +, *, (, )}, где x играет роль операндов, * и + --- левоассоциативные операции (то есть E+F+G означает ((E+F)+G)), операция * связывает операнды сильнее, чем + (то есть E+F*G означает E+(F*G)), причем порождаемые выражения НЕ ДОЛЖНЫ содержать ненужных скобок (а именно, например, выражение x+(x*x) не должно порождаться)
----
[http://bashor.github.com/GrGen/GrGen.html Генератор] Залима для проверки 1-5 пунктов.
Коментарии:
T -- терминальные символы. Пробелы и запятые игнорируются, т.е. abc == a b c == a b, c
Все остальные символы считаются нетерминальными
R -- правила преобразования вида: From : to
пробелы и пустые строки игнорируются.
Кроме того, можно указать свой чекер на JavaScript. Например:
1) return countChar(st, 'a') == countChar(st, 'b') && countChar(st, 'a') == countChar(st, 'c');
2) return st.indexOf("11") == -1;
3) var matches = /^([10]+)[*]+([10]+)$/g.exec(st);
return matches[1] == matches[2] && matches.length == 3;
4) return countChar('a') != countChar('b');
5) return countChar(st, 'a') == countChar(st, 'b') * 2;
init -- (пере)инициализация
step -- выполнение "одного шага"

== Программа курса ==

# Языки программирования, синтаксис, семантика, прагматика. Когнитивные особенности человеческого мышления и их влияние на развитие языков программирования.
# Языки программирования в ретроспективе. Процедурное, объектно-ориентированное, логическое и функциональное программирование. Предметно-ориентированные языки. Языки вне классификации.
# Абстрактный и конкретный синтаксис. Статическая и динамическая семантика. Компиляция и интерпретация. Проекции Футамуры-Ершова.
# Генеративный и аналитический подходы к описанию синтаксиса. Формальные грамматики, иерархия Хомского.
# Регулярные языки и конечные автоматы. Применение регулярных выражений в народном хозяйстве (grep/sed/awk) и для лексического анализа (lex/flex). Отсутствие бесконтекстной лексики в реальных языках программирования.
# Контекстно-свободные грамматики. Нормальные формы Хомского и Грейбах. Алгоритмы Эрли и Кока-Янгера-Касами. Неконтекстосвободность реальных языков программирования.
# Нисходящий анализ. Возврат и заглядывание вперед. Класс языков LL(k). Рекурсивный спуск, магазинные автоматы, парсер-комбинаторы, PEG, "скаредный" разбор. GLL. Инструменты нисходящего анализа (Parsec, ANTLR и пр.)
# Восходящий анализ, классы LR(k) и LALR(k). GLR. Инструменты восходящего анализа (yacc/bison).
# Двухуровневые и атрибутные грамматики, вопросы применения на практике.
# Идентификация. Область видимости и область действия. Статическое и динамическое, раннее и позднее связывание.
# Энергичность и ленивость. Call-by-name, call-by-value, call-by-reference.
# Строгость, чистота, прозрачность по ссылкам.
# Языки с типами и языки без типов. Статическая и динамическая типизация.
# Номинальная и структурная эквивалентность типов. Простейшие конструкторы.
# Типы с кванторами и что они означают. Универсальные и экзистенциальные типы.
# Subtyping. Структурный и номинальный subtyping.
# Динамическая семантика языков. Операционная семантика большого и малого шага.
# Денотационный подход к описанию семантики.
# Аксиоматическая семантика. Верификация программ. Design by contract.
# Когерентность языков программирования и машинных архитектур. Языково-специфичные архитектуры, виртуальные машины и JIT-компиляция.
#<nowiki>*</nowiki> Структура рабочей программы. Код, данные, библиотеки, поддержка времени исполнения.
#<nowiki>*</nowiki> Задача генерации кода. Генерация кода путем интерпретации.
#<nowiki>*</nowiki> Восходящее переписывание деревьев и динамическое программирование (BURS).
#<nowiki>*</nowiki> Алгоритмы распределения регистров. Распределение регистров и раскраска графов.
#<nowiki>*</nowiki> Параллелизм на уровне инструкций. Планирование инструкций.
#<nowiki>*</nowiki> Анализ потока управления. Глубинное остовное дерево, доминирование, анализ циклической структуры программ. Сводимость. Устранение недостижимого кода, оптимальная линеаризация.
#<nowiki>*</nowiki> Анализ потока данных. Полурешеточная модель. RD, LV, AE, UEU. Устраненние мертвого кода, экономия общих подвыражений, понижение силы операций, чистка циклов.

''<nowiki>* - вопросы будут рассмотрены при наличии времени.</nowiki>''

== Список литературы ==
# S.Muchnik. Advanced Compiler Design & Implementation. Academic Press, Morgan Kaufmann, 1998.
# А.Ахо, Р.Сети, С.Ульман. Компиляторы: принципы, технологии, инструменты. Вильямс, 2003.
# А.Ахо, С.Ульман. Теория синтаксического анализа, перевода и компиляции. Том 1. М., "Мир", 1978.
# F.Nielsen. Principles of Program Analysis. Springer, 2005.
# F.Nielse, H-R.Nielsen. Semantics with Applications. Wiley Professional Computing, 1992.
# B.Pierce. Types and Programming Languages. MIT Press, 2002.
# T.Пратт. Языки программирования: разработка и реализация. 1978.
# Б.К.Мартыненко. Языки и трансляции. Из-во СПбГУ, 2008.

== Список групп для выполнения задач ==

# [Haskell] Мартынов Семён, Башоров Залим, Казенюк Сергей, Витвицкий Александр, Тугарёв Денис.
# Кринкин Михаил, Лазарев Сергей, Фофанова Мария, Бандурин Дмитрий, Ждан Анна
# [JAVA] Сорокин Артём, Коровин Алексей, Опейкин Александр, Шеставин Дмитрий, Владислав Савельев
# [C++] Иванов Антон, Крашенинникова Ксения, Лепенькин Ярослав, Диевский Алексей, Кормишин Сергей
# Певзнер Алина, Князев Сергей
# [JAVA] Великий Алексей.

''<nowiki>* Не более 5 человек в каждой группе; старайтесь выравнивать группы по уровню, и не повторяться в выборе языков.</nowiki>''

== Полезные ссылки ==

* [http://caml.inria.fr/ocaml/release.en.html Latest OCaml release]
* [http://caml.inria.fr/pub/docs/manual-ocaml/index.html Documentation and user’s manual]

IntroductionToProgrammingLanguages

2012-02-26T23:44:39Z

Zalim: /* Задание №3 */ исправление чекера для 3

'''Введение в языки программирования'''

Лектор - Дмитрий Юрьевич [http://www.matmex.spb.ru/photoalbum/person_teachers_BulychevDY_1.html Булычев]

[https://docs.google.com/spreadsheet/ccc?key=0ApYxPEC9C_QXdC00UkVJekxYV0pYYVAxTmFXUkt6SVE Учёт посещаемости занятий]

[https://docs.google.com/spreadsheet/ccc?key=0ApYxPEC9C_QXdE05Q09iWlRqRzJ3d1FwTlJRSEkxbFE Учёт сдачи домашних заданий]

== Лекции ==

* [http://code.google.com/p/aptu-tex/source/browse/formallang/les1/les.tex Лекция №1] 10.02.2012
* 17.02.2012
В семантике ошибка: правило для переменной вместо
[x](s)=s(x)
читать как
[x](s)=[s(x)](s).
* 24.02.2012

== Домашние задания ==

=== Задание №1 ===
Cрок сдачи '''17 февраля 2011'''

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

int exp (int x, int n) {
int y = 1;
while (n) {
if (n % 2) y *= x;
n /= 2;
x *= x;
}
return y;
}

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

=== Задание №2 ===
Cрок сдачи '''24 февраля 2011'''

Написать принтер, который по абстрактному синтаксическому дереву программы печатает её представление в конкретном синтаксисе (который мы обсуждали) и интерпретатор (который вычисляет значение выражения в данном состоянии).

Описание конкретного синтаксиса для представления программ на языке L:
# Программа представляется в виде последовательности слов. Разделителем служит перевод строки.
# Пусть E --- выражение, а |E| --- представление этого выражения в данном конкретном синтаксисе. Тогда:
#* переменная v представляется в виде "x" v (то есть символ x (как терминал), и собственно имя переменной на следующей строчке).
#* функция {x -> E} представляется в виде "f" x |E|
#* применение функции F E представляется в виде "a" |E| |F|
#* условное выражение C ? T : E представляется в виде "?" |C| |T| |E|
#* бинарная операция X o Y представляется в виде "@" |X| |Y|
#* константа i представляется в виде "!" i
# Контекст (список определений name1=expr1, name2=expr2 и т.д.) представляется как последовательность name1 |expr1| name2 |expr2| и т.д.
# Программа (то есть выражение E в контексте C) представляется как последовательность |C| ";" |E|.
# Все реализации д.з. №2 должны уметь читать файл, содержащий описание программы в таком синтаксисе (иначе невозможно ничего проверить).

Пример 1. Выражение
{x -> {y -> x + y}} 1 2
в данном конкретном синтаксисе выглядит так:
a
a
f
x
f
y
@
+
x
x
x
y
!
1
!
2

Пример 2. Программа
fact = {n -> n ? n * (fact n-1) : 1};
fact 4
будет представлена как
fact
f
$0
?
x
$0
@
*
x
$0
a
x
fact
@
-
x
$0
!
1
!
1
;
a
x
fact
!
4

[http://narod.ru/disk/42015820001.bfed0d23b277fa721f7e86f27dc45e3d/monoMix.opt.html Программа], которая воспринимает программы в языке L в обычном синтаксисе, и печатает их представление в данной упрощенной форме. Бинарник для x86-linux, -h --- помощь.

=== Задание №3 ===
Желаемый срок сдачи '''26 февраля 2011'''

# Написать порождающую грамматику для языка над алфавитом {a, b, c}, состоящего из всех слов, в которых количество букв a, b и c одинаково.
# Написать порождающую грамматику для языка над алфавитом {0, 1}, состоящего из всех слов, в которых не встречается две единицы подряд.
# Написать порождающую грамматику для языка над алфавитом {0, 1, *}, состоящего из всех слов вида sas, где s --- непустая строка нулей и единиц любой длины, а a --- непустая строка из звездочек любой длины.
# Написать порождающую грамматику для языка над алфавитом {a, b}, состоящего из всех вида a^nb^m, где n <> m.
# Написать порождающую грамматику для языка над алфавитом {a, b}, состоящего из всех слов, в которых количество букв a в два раза больше, чем количество букв b.
# Правда ли, что любой рекурсивный язык контекстно-зависим (обратное, как известно, верно)?
# Написать реализацию построения НКА по регулярной грамматике; написать интерпретатор этого автомата, который проверяет принадлежность заданного слова языку, и принтер, который печатает граф переходов автомата в формате .dot пакета graphviz.
# Написать грамматику для порождения выражений в алфавите {x, +, *, (, )}, где x играет роль операндов, * и + --- левоассоциативные операции (то есть E+F+G означает ((E+F)+G)), операция * связывает операнды сильнее, чем + (то есть E+F*G означает E+(F*G)), причем порождаемые выражения НЕ ДОЛЖНЫ содержать ненужных скобок (а именно, например, выражение x+(x*x) не должно порождаться)
----
[http://bashor.github.com/GrGen/GrGen.html Генератор] Залима для проверки 1-5 пунктов.
Коментарии:
T -- терминальные символы. Пробелы и запятые игнорируются, т.е. abc == a b c == a b, c
Все остальные символы считаются нетерминальными
R -- правила преобразования вида: From : to
пробелы и пустые строки игнорируются.
Кроме того, можно указать свой чекер на JavaScript. Например:
1) return countChar(st, 'a') != countChar(st, 'b') && countChar(st, 'a') == countChar(st, 'c');
2) return st.indexOf("11") == -1;
3) var matches = /^([10]+)[*]+([10]+)$/g.exec(st);
return matches[1] == matches[2] && matches.length == 3;
4) return countChar('a') != countChar('b');
5) return countChar(st, 'a') == countChar(st, 'b') * 2;
init -- (пере)инициализация
step -- выполнение "одного шага"

== Программа курса ==

# Языки программирования, синтаксис, семантика, прагматика. Когнитивные особенности человеческого мышления и их влияние на развитие языков программирования.
# Языки программирования в ретроспективе. Процедурное, объектно-ориентированное, логическое и функциональное программирование. Предметно-ориентированные языки. Языки вне классификации.
# Абстрактный и конкретный синтаксис. Статическая и динамическая семантика. Компиляция и интерпретация. Проекции Футамуры-Ершова.
# Генеративный и аналитический подходы к описанию синтаксиса. Формальные грамматики, иерархия Хомского.
# Регулярные языки и конечные автоматы. Применение регулярных выражений в народном хозяйстве (grep/sed/awk) и для лексического анализа (lex/flex). Отсутствие бесконтекстной лексики в реальных языках программирования.
# Контекстно-свободные грамматики. Нормальные формы Хомского и Грейбах. Алгоритмы Эрли и Кока-Янгера-Касами. Неконтекстосвободность реальных языков программирования.
# Нисходящий анализ. Возврат и заглядывание вперед. Класс языков LL(k). Рекурсивный спуск, магазинные автоматы, парсер-комбинаторы, PEG, "скаредный" разбор. GLL. Инструменты нисходящего анализа (Parsec, ANTLR и пр.)
# Восходящий анализ, классы LR(k) и LALR(k). GLR. Инструменты восходящего анализа (yacc/bison).
# Двухуровневые и атрибутные грамматики, вопросы применения на практике.
# Идентификация. Область видимости и область действия. Статическое и динамическое, раннее и позднее связывание.
# Энергичность и ленивость. Call-by-name, call-by-value, call-by-reference.
# Строгость, чистота, прозрачность по ссылкам.
# Языки с типами и языки без типов. Статическая и динамическая типизация.
# Номинальная и структурная эквивалентность типов. Простейшие конструкторы.
# Типы с кванторами и что они означают. Универсальные и экзистенциальные типы.
# Subtyping. Структурный и номинальный subtyping.
# Динамическая семантика языков. Операционная семантика большого и малого шага.
# Денотационный подход к описанию семантики.
# Аксиоматическая семантика. Верификация программ. Design by contract.
# Когерентность языков программирования и машинных архитектур. Языково-специфичные архитектуры, виртуальные машины и JIT-компиляция.
#<nowiki>*</nowiki> Структура рабочей программы. Код, данные, библиотеки, поддержка времени исполнения.
#<nowiki>*</nowiki> Задача генерации кода. Генерация кода путем интерпретации.
#<nowiki>*</nowiki> Восходящее переписывание деревьев и динамическое программирование (BURS).
#<nowiki>*</nowiki> Алгоритмы распределения регистров. Распределение регистров и раскраска графов.
#<nowiki>*</nowiki> Параллелизм на уровне инструкций. Планирование инструкций.
#<nowiki>*</nowiki> Анализ потока управления. Глубинное остовное дерево, доминирование, анализ циклической структуры программ. Сводимость. Устранение недостижимого кода, оптимальная линеаризация.
#<nowiki>*</nowiki> Анализ потока данных. Полурешеточная модель. RD, LV, AE, UEU. Устраненние мертвого кода, экономия общих подвыражений, понижение силы операций, чистка циклов.

''<nowiki>* - вопросы будут рассмотрены при наличии времени.</nowiki>''

== Список литературы ==
# S.Muchnik. Advanced Compiler Design & Implementation. Academic Press, Morgan Kaufmann, 1998.
# А.Ахо, Р.Сети, С.Ульман. Компиляторы: принципы, технологии, инструменты. Вильямс, 2003.
# А.Ахо, С.Ульман. Теория синтаксического анализа, перевода и компиляции. Том 1. М., "Мир", 1978.
# F.Nielsen. Principles of Program Analysis. Springer, 2005.
# F.Nielse, H-R.Nielsen. Semantics with Applications. Wiley Professional Computing, 1992.
# B.Pierce. Types and Programming Languages. MIT Press, 2002.
# T.Пратт. Языки программирования: разработка и реализация. 1978.
# Б.К.Мартыненко. Языки и трансляции. Из-во СПбГУ, 2008.

== Список групп для выполнения задач ==

# [Haskell] Мартынов Семён, Башоров Залим, Казенюк Сергей, Витвицкий Александр, Тугарёв Денис.
# Кринкин Михаил, Лазарев Сергей, Фофанова Мария, Бандурин Дмитрий, Ждан Анна
# [JAVA] Сорокин Артём, Коровин Алексей, Опейкин Александр, Шеставин Дмитрий, Владислав Савельев
# [C++] Иванов Антон, Крашенинникова Ксения, Лепенькин Ярослав, Диевский Алексей, Кормишин Сергей
# Певзнер Алина, Князев Сергей
# [JAVA] Великий Алексей.

''<nowiki>* Не более 5 человек в каждой группе; старайтесь выравнивать группы по уровню, и не повторяться в выборе языков.</nowiki>''

== Полезные ссылки ==

* [http://caml.inria.fr/ocaml/release.en.html Latest OCaml release]
* [http://caml.inria.fr/pub/docs/manual-ocaml/index.html Documentation and user’s manual]

IntroductionToProgrammingLanguages

2012-02-11T13:33:51Z

Zalim: /* Список групп для выполнения задач */

== Лекции ==
* [Лекция №1] 10.02.2012

== Практические задания ==
* [Задание №1]

== Программа курса ==

== Список литературы ==

== Список групп для выполнения задач ==

1. Мартынов Семён, Башоров Залим, Казенюк Сергей, Витвицкий Александр, Тугарёв Денис.

2.

3.

4.

5.

6.

IntroductionToProgrammingLanguages

2012-02-11T13:31:49Z

Zalim: /* Список групп для выполнения задач */

== Лекции ==
* [Лекция №1] 10.02.2012

== Практические задания ==
* [Задание №1]

== Программа курса ==

== Список литературы ==

== Список групп для выполнения задач ==

1. Мартынов Семён, Башоров Залим, Казенюк Сергей, Витвитский Александр, Тугарёв Денис.

2.

3.

4.

5.

6.

Алгоритмы и структуры данных

2012-01-17T02:01:49Z

Zalim: /* Экзамен */

http://www.lektorium.tv/course/?id=22823

==Экзамен==
'''17.01.2012''' 
Начало в '''10.00''' 
1.5 ч. на подготовку 
15 минут на ответ. 
Заходить получать билеты будете, действительно, с интервалом в минут 15, поэтому рекомендую заранее определиться с порядком 

Примерно в 14 прервёмся на час на обед, поэтому последний вопрос до обеда будет выдан в 12-15. 

'''Порядок получения билетов:''' 
10.00 Фофанова М. 
10.15 Краско Е. 
10.30 - 
10.45 Крашенинникова К. 
11.00 - 
11.15 Кринкин М. 
11.30 Кононенко В. 
11.45 Казенюк С. 
12.00 Коровин А. 
12.15 Певзнер А.А. 
15.00 Шеставин Д.В. 
15.15 Опейкин А. 
15.30 Кормишин С. 
15.45 Кузьмин А.В. 
16.00 Мартынов С. 
16.15 Гуменюк С.С. 
16.30 Бандурин Д.В. 
16.45 Лепенькин Я.А. 
17.00 Диевский А.В. 
17.15 Иванов А.К. 
17.30 Великий А.В 
17.45 Ждан А. Д. 
18.00 Сорокин А. Ю 
18.15 Кудинкин А. 
18.30 Башоров З. 
18.45

Алгоритмы и структуры данных

2012-01-15T20:21:18Z

Zalim: