Обучение на кафедре ПОАС (программная инженерия) 2009-2011 года

Предисловие

Эта статья посвящена специфичным предметам на кафедре ПОАС. Почему не ЭВМ/АСУ/САПР? Я сам с ПОАС, поймаю людей с других кафедр – с удовольствием попытаю их. Ну а пока будут рассмотрены такие предметы как:

Качество и надёжность ПО
Структуры и алгоритмы обработки данных
Экстремальные задачи на графах
Теория языков программирования
Объектно-ориентированное программирование
Системы искусственного интеллекта
Теория вычислительных процессов

Хочу напомнить читателям, что обучение – среда динамичная, если у нас был такой расклад заданий, это не значит, что на следующий год не будет совершенно другого. Цель статьи – сделать наброски того, что изучается на ПОАС – всё же дух предметов не меняется так стремительно, как программа.

Теперь первокурсников-программистов заставляют выбирать специализацию (ПОАС, ЭВМ, АСУ или САПР) при поступлении. В какой-то мере эта статья для них - абитуриентов ВолгГТУ. Но всё же делаю акцент на людей, уже обучающихся на этой кафедре. Мне, например, на 2 курсе было очень интересно, что же изучают на 4. Ведь любопытство – это замечательно :) Всё, всё – переходим к статье.

Качество и надёжность ПО

(2 курс, 2 семестр).

В этом семестре был единственный специализированный предмет - Качество и надёжность программного обеспечения. Содержание этой дисциплины еле уложилось в один семестр, многие остались на пересдачу. Да, было сложно, но в то же время мы получили немерено знаний, касающихся процесса разработки ПО (в будущем пригодилось на 4 курсе в рамках ТРПО).

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

На лабах показывали, что сделали за неделю, документы, код и т.д.

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

Семестровая

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

Как и в случае Программирования на ЯВУ задания на семестровую оценивались с разными коэффициентами - от 0.6 до 1.2.

В качестве 0.6 предлагалось сделать программу для некоторого преобразования текста, а титанам, взявшим 1.2, было необходимо погрузиться в мир синтаксического анализа выражения на С++/RegExp и сделать маленький кусочек семантического анализатора компилятора.

Для выполнения семестровой необходимо подготовить целый пакет документов, начиная от технического задания (ТЗ), пояснительной записки к техническому проекту (ПЗ к ТП) и, заканчивая, руководством программиста к программе.

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

С исходными кодами программы и нормативными документами следует сдать и репозиторий работы (нас просили на Mercurial), дабы преподаватель видел как шла работа в семестре и с каким усердием вы выполняли или не выполняли план.

Также, в итоге, требуется сдать сгенерированную Doxygen’ом документацию к исходникам. Здесь работы немного - просто по-особому прописывать комментарии в исходниках, а баллов дают нормально.

Пример простого задания

Английский текст зашифрован циклическим сдвигом номера каждой буквы (пробел имеет номер 0) вправо на N. N неизвестно, но известно слово, находящееся в тексте. Расшифровать.
Коэффициент сложности: [0.7]
Вход: зашифрованный текст
Выход: расшифрованный текст

Пример сложного задания

Отобразить на экране переменные и части массивов(структур, классов), участвующие в выражении, с выделением цветом входных, выходных и промежуточных данных
Сложность [0.9-1.1]
Вход: дерево разбора выражения данные о типах используемых переменных, функциях, структурах (классах)
Выход: переменные и части массива (на экране и/или в виде картинки)

Примерная тематика лекций

Модели разработки ПО:

спиральная модель,
RUP (Rational Unified Process),
Agile (гибкая модель),
XP(экстремальное программирование),
"водопад (waterfall)”,
Scrum;

составление ТЗ(техническое задание по ГОСТ 19.201-78), ТП и ПЗ(технический проект и пояснительная записка к нему по ГОСТ 19.201-78), РП(рабочий проект), руководство пользователя, руководство системного программиста;
знакомство с ГОСТ34, ГОСТ19, IEEE 830;
знакомство с видами UML-диаграмм - Class Diagram, UseCase diagram и т.д.;
автодокументирование кода (Doxygen) (http://www.stack.nl/~dimitri/doxygen/index.html);
хранение и обработка деревьев. XML и постфиксная запись выражения;
модульное, юнит-тестирование (JUnit, VisualAssert и т.д.); По теме:

Несколько философская статья о модульном тестировании http://www.rsdn.ru/article/testing/UnitTesting.xml

Системы контроля версий(SCM) (CVS, SVN, HG, Bazaar, GIT) - что это и как ими пользоваться. По теме:

http://lib.custis.ru/DVCS_YAC - сравнение популярных DVCS — Mercurial, Git и Bazaar;
Ресурсы: Hg, SVN, Git; причём версии с приставкой Tortoise - это не чистые SCM, а интеграторы в оконную систему для более удобной работы. PDF-подсказки по консолям Hg, SVN, Git

Метрики эффективности работы программиста (инструмент RSM);
Статический анализ кода (инструмент CppCheck), динамический анализ кода (инструмент Valgrind). По теме - List of tools for static code analysis, http://cppcheck.sourceforge.net/, http://valgrind.org/
профилировка приложений (инструмент VerySleepy (http://sleepy.sourceforge.net/, http://www.codersnotes.com/sleepy - для 64-битного процессора - для Windows; консольный Gprof, графический kprof под nix)

язык DOT, инструмент GraphViz

Материалы по Doxygen

Справка по командам на официальном сайте: http://www.stack.nl/~dimitri/doxygen/commands.html
Jafar Al-Kofahi - Doxygen Tutorial - небольшой сишный тутор: http://homel.vsb.cz/~chu074/DoxygenTutorial.pdf
PDF на 2 листа с основными тегами: http://www.digilife.be/quickreferences/QRC/Doxygen%20Quick%20Reference.pdf

Структуры и алгоритмы обработки данных

(1 и 2 семестр 3 курса)

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

Расскажу лишь, что было у нас.

Суть предмета

Вы когда-нибудь задумывались зачем в библиотеках, подобных Qt столько всяких контейнеров? И тебе QSet и QList и QLinkedList, QMap, QHash, QXXXArray, QStack… !!

На этом предмете приподнимут завесу тайны. Объяснят свойства контейнеров, скорость работы в различных условиях, количество требуемой памяти; познакомят с алгоритмами, которым действительно надо посвящать целые вечера, но зато это окупится увеличением производительности программы в разы; да много чего ещё :)

Если не лениться, то можно получить огромный багаж знаний по алгоритмам. Причем, здесь я говорю «алгоритм» в широком смысле, так как бОльший упор делается на теорию, нежели на практику. Нет, это не физика, кода придётся пописать достаточно, но теория играет важную роль. Ах да, приучили к LaTeX на этом предмете, за что большое спасибо! Кстати, здесь отличный бесплатный учебник в pdf.

Лабораторные 1 семестра

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

Лабораторные 2 семестра

наибольшая общая подпоследовательность;
задача 2-SAT;
реализация графового алгоритма;
рефакторинг кода;
что-то связанное с хэшированием;
создание более сложного контейнера;

Семестровая

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

А вот такие были темы:

Массивы и множества
Списки, очередь, стэк
Динамическое программирование
Теория чисел
Графовые алгоритмы
Хэширование
Строковые алгоритмы
Вычислительная геометрия
Алгебра, линейнай алгебра

Экстремальные задачи на графах

(2 семестр 3 курса)

Да, многие тоже, глядя в расписание, представили этот предмет как программирование на крыше небоскреба, бегая по битому стеклу :)

Но вся экстремальность заключалось в другом значении этого слова – экстремум, предмет можно назвать "Решение задач, методами программирования в ограничениях”, "Constrait programming in graph algorithms”.

Суть предмета

Здесь учили различным алгоритмам на графах и их применению к реальным задачам.

Простой пример: алгоритм "волны” и его применение к проектированию печатных плат. (http://ru.wikipedia.org/wiki/Алгоритм_Ли)

Дисциплина была разделена на 6 лабораторных, семестровую, лекции и практики.

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

составление задачи линейной оптимизации;
свойства графов, матрицы инцедентности, смежности;
алгоритм Форда-Фалькерсона;
ещё одно составление задачи линейной оптимизации;
алгоритм Форда;
алгоритм дефекта;

Инструменты

QSopt Linear Programming Solver
LINGO TRIAL
как ни странно - MS Excel, OO Calc;
расширение "Free EuroOffice Solver” для OO Calc.

Статьи

Программирование в ограничениях
К LINDO есть прекрасный встроенный мануал.
Максимальный поток минимальной стоимости

Книги

Э.Майника «Алгоритмы оптимизации на сетях и графах»
Д.Филлипс, А.Гарсиа-Диас «Методы анализа сетей»
Хемди А. Таха «Введение в исследование операций»

Теория языков программирования

(1 семестр 4 курса)

И вот настало время, когда понимаешь, на какой кафедре ты учишься. Это был наверное самый сложный из предметов за все годы. Вроде бы всё просто - 4 лабы + семестровая. Но не тут-то было. Смысл семестровой - написать транслятор ограниченного подмножества языка программирования в байт-код JAVA-машины. Языки были самые разные:

Smalltalk;
Ruby;
VisualBasic;
Eiffel;
КУМИР;
PHP;
COOL (учебный язык);
Python;
и другие.

Работать можно в команде (2-3 человека), можно одному.

Нам выдали "карточку семестровой работы”, куда надо было записать какие возможности языка кто реализует. Реализованные возможности выливались в баллы. Один человек сумел реализовать практически всю карточку :) и к экзамену у него было достаточно баллов, чтобы его не сдавать.

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

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

регулярные выражения;
разработка лексического анализатора для выбранного языка;
разработка синтаксического анализатора для выбранного языка;
разработка семантического анализатора для выбранного языка;
разработка генератора кода для JAVA-машины;

Экзамен

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

Примеры вопросов с экзамена

4. Генератор лексических анализаторов flex. Стартовые условия. Виды и объявление стартовых условий. Описание условий в регулярных выражениях. Начальное условие. Смена текущего стартового условия. Описание регулярного выражения, срабатывающего при любом стартовом условии.
6. LL(K)-грамматики, LL(0) – разбор, LL(1) – разбор.
11. Стадия семантического анализа. Проверка семантических ограничений по абстрактному синтаксическому дереву. Атрибутирование синтаксического дерева. Виды таблиц, используемые при трансляции.
12. Генерация кода. Регистровые и стековые машины. Виртуальные машины. Организация виртуальной машины Java. Таблица констант, виды констант. Дескрипторы.

Инструменты

RegexBuilder - проверка правильности регулярного выражения;
Flex - генератор лексических анализаторов (в nix обычно уже есть или есть в виде lex)
Bison - генератор синтаксических анализаторов(в nix должен быть, в крайнем случае - в виде yacc)
Java ByteCode Editor (JBE) - просмотрщик .class файлов для отладки генерации кода
GraphViz - для построения визуального дерева разбора программы

Стоит заметить, что flex и bison - это GNUшная адаптация lex и yacc - UNIX-инструментов, со схожим синтаксисом.

Плюсы

изучены основы и даже не совсем основы трансляции, что было упущено на 2 курсе, так как у ПОАС вместо Основ трансляции был КачНПО.
языки программирования больше не кажутся чем-то сверхестесственным;
разобрались в работе Java-машины;

Минусы

несколько досадных опечаток в методичке сводили с ума в 4 утра о_О
пришлось совершать много рутинной работы на этапе построения синтаксического анализатора, из-за чего многие не могли её сдать даже к декабрю. Хотелось бы IDE какое-нибудь, на деле же сидели с тремя окнами Notepad’a и переписывали практически одно и то же из файла в файл;
если не заставить себя подключить С-файл выхода bison к С++ проекту можно поймать много нехороших вещей: отсутствие прелестей ООП в Си делает невозможным, либо слишком сложным, решение некоторых задач. Отсюда огромные Switch-Case на несколько сотен строк и т.д.
Рецепты, касающиеся данного предмета можно почерпнуть из блога Романа Ермолова
Некоторые инструменты зазеркалированы на нашем сайте в разделе Теория языков программирования.

Объектно-ориентированное программирование

(1 семестр 4 курса)

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

Мой друг рассказал мне, как на дополнительных курсах по C# преподаватель спросил аудиторию – «Кто знает ООП?» 1-2-3 курс тут же подняли руки. 4-5 призадумались. После нескольких месяцев ООП это было немудрено. Ведь нам доказали, что то, чему нас учили в конце курса ЯВУ не является истиной в последней инстанции и требует уточнений и множества дополнений.

Действительно – как бы не было смешно, но ни один из нас не умел программировать в стиле ООП к 4 курсу. Конечно можно сказать, что, мол «я знаю, что такое полиморфизм-наследование-инкапсуляция», и считать себя мастером этой методологии. Но это будет глупо.

Учили именно применять эти техники на практике. А также был большой багаж по теоретическим знаниям – одних видов полиморфизма было столько, что им была посвящена отдельная лекция. А также впервые за все годы коснулись разработки с использованием шаблонов проектирования (http://design-pattern.ru/ , http://ru.wikipedia.org/wiki/Шаблон_проектирования).

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

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

знакомство с языком Java, языком OCL (http://fengnet.com/book/UML/umlnut2-APP-B-SECT-1.html)
создание собственного класса, используя правила ООП;
создание собственного виджета, на основе одного из имеющихся в Java Swing;
эффективное использование полиморфизма, проектирования класса небольшой игры.

Семестровая

Семестровая являет собой продолжение последней лабы, а именно, реализацию полноценной игры, либо специфического задания (например, визуализация объектов в массиве). Под словом «игра» подразумевается не нечто, отличающееся графикой и интеллектом противников. Да, желательно было сделать некое подобие осмысленных действий у оппонентов (компьютерных игроков). Но главное внимание по-прежнему было устремлено на структуру классов, качество кода, если хотите - на «красоту» реализованных классов. К коду требовалось оформить диаграммы последовательностей и классов UML.

Плюсы

Познакомились с Java – интересный язык, расширяет ООП-мышление после С++.
Увидели наконец-то эту триаду «полиморфизм-инкапсуляция-наследование» в действии
Изучили некоторые паттерны проектирования

Минусы

Вкупе с ТЯПом, ИИ и ТРПО (Технологии разработки ПО) было очень тесно. Лабы сдавались в конце семестра, с семестровой и вовсе затор был.
Не сразу смекнули, что оценивается не сам код, а его качество, а следовательно некоторые были не в восторге от долгих бесед с преподавателем по поводу его представлений об идеальном коде.

Книги

Брюс Эккель «Философия Java» (Bruce Eckel "Thinking in Java”)
Иван Портянкин «Swing. Эффективные пользовательские интерфейсы»
Дэвид Флэнаган «Java в примерах» (David Flanagan "Java examples in a nutshell”)

Другое

Документация по Java 6,7 CHM-формат – очень пригодилась.

Системы искусственного интеллекта

(1 и 2 семестр 4 курса)

Это был наверное самый необычный предмет с начала обучения, но не по сложности, а по трудности понимания «с чего начать?». Была куча непонятных теоретических выкладок, их надо было как-то связать с реализацией и замыслом языка Prolog. Но кто имел смелость поработать с этим языком неделю-две, не жалуясь и не отвлекаясь, обычно достигали цели.

Предмет введён не только для ПОАС – с нами занимались и АСУ (ну и несостоявшийся САПР по идее должен был, который 2 года назад принял всего 3 человека, а на 2012 год и вовсе не существует).

Поскольку предмет не шёл у ЭВМ, решил его включить сюда.

Лабораторные работы 1 семестра

знакомство с Прологом, средой VisualProlog;
работа с базой фактов в Прологе, рекурсия;
реализация списков на Прологе;
GUI на VisualProlog;

Семестровая 1 семестра

Необходимо написать игру на Прологе, с применением методов ИИ.

Тематика самая разнообразная:

Головоломка «Судоку»
Головоломка «Японский кроссворд»
Игра «Поддавки»
Игра «Морской бой»
Игра «Пятнашки»
Карточная игра «Паук»
Карточная игра «Рэндзю»
Карточная игра «Червы»
И даже нахождение устойчивых состояний в игре «Жизнь»

Лабораторные работы 2 семестра

деревья принятия решений (decision trees)
экспертные системы
фреймовые онтологии
OWL-онтологии

Семестровая 2 семестра

Создание системы рассуждений по прецедентам. (Protege OWL + jColibri) (методичка по семестровой здесь)

Книги

Иван Братко «Язык PROLOG (Пролог): алгоритмы искусственного интеллекта»

Следует сказать, что люди в основном учились по всяческим статьям:

Prolog — удивительный язык программирования
Пролог, введение
Японская версия головоломки «Волк, коза и капуста» на Прологе
Справочник по SWI-Prolog
Связка SWI-Prolog и Java/Swing
Про связку SWI-Prolog и C++/Qt
Книга рецептов для Visual Prolog
ИНТУИТ, довольно хороший и понятный курс

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

Справочник по терминам СИИ [En]

Теория вычислительных процессов

(1 семестр 4 курса)

Данный предмет представляет собой ещё одно погружение в дисциплину ОргЭВМ с 3 курса. Если честно, не знаю зачем его нам поставили – считал, что параллельные вычисления – это удел кафедры ЭВМ.

Суть предмета

Разобраться в преимуществах и отличиях разных методов организации параллелизма на примере распространённого алгоритма (у нас была сортировка).

Предмет прошел довольно-таки незаметно. Лабы сдавались с небольшими усилиями. Семестровая по сложности значительно уступает лабам.

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

реализация алгоритма с использованием OpenMP
реализация алгоритма с использованием MPI
использование средств Intel Parallel Studio для анализа параллельных программ

Семестровая

Красиво оформленные лабы + титульник + выводы

Это простой вариант. Был ещё сложный, но за неимением времени его никто не захотел делать.

Послесловие

Ну вот и пролетели 3 года на ПОАСе. Всего, конечно, не расскажешь. Да и не в этом цель. Надеюсь, помог кому-нибудь с выбором кафедры/поиском инструмента, статьи или книги.

До новых встреч, ваши мысли и пожелания - в комментарии!


Имя *:
Email *:

Код *:

Логин:
Пароль:

запомнить
Забыл пароль · Регистрация Войдите, чтобы не видеть рекламу