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

АБB
АБB
АБB

Обычная версия сайта

Материалы лабораторных работ по курсу "Алгоритмы и структуры данных", 2 курс 3-4 модули.
Язык программирования: C, C++, C# (другие языки не приветствуются)
Лабораторные работы:
Лабораторная работа № 1 (распознаватель для автоматного языка)
Лабораторная работа № 2 (преобразователь  для автоматного языка)
Лабораторная работа № 3 (анализ цепочек с помощью регулярных выражений)
Памятка по регулярным выражениям
      Библиотеки для работы с регулярными выражениями
        Как подключить бибилиотеки
Лабораторная работа №4.1 (рекурсивный спуск: разбор булевских выражений)
Лабораторная работа №4.2 (рекурсивный спуск: разбор и вычисление булевских выражений)
Лабораторная работа №5 (7.2) (арифметика с цифрами)
Лабораторная работа №6.1 (сканер для булевских выражений без переменных)
Лабораторная работа №6.2 (подключение сканера для вычисления булевских выражений)
Лабораторная работа №7 (7.1, сканер для арифметических выражений)
Лабораторная работа №8 (преобразование в ПОЛИЗ и вычисление выражений без переменных)
Лабораторная работа №9(преобразование выражений в дерево и их вычисление)
Лабораторная работа №10 (ПОЛИЗ: вычисление выражений с переменными)
Лабораторная работа №11 (преобразование в ПОЛИЗ и вычисление операторов)
Домашние задания:
Домашнее задание №1
Домашнее задание №2
Домашнее задание №3
Домашнее задание №4
Домашнее задание №5
Итоговое домашнее задание (ИДЗ)

Раздел ИДЗ:
Итоговое домашнее задание подводит черту изучению раздела курса АиСД по формальным грамматикам.
Не сдавшие ИДЗ автоматически попадают на экзамен. При округлении оценки приоритет имеет качество исполнения(!) ИДЗ.
В его написании могут помочь лабораторные 8-11. Помимо требований в тексте ИДЗ (выше) далее написаны подробные уточнения того, что и по каким критериям будет проверяться.
Сдача ИДЗ проходит в несколько этапов последовательно - чтобы перейти к следующему этапу, необходимо успешно пройти предыдущий.

1) Отчет.
Требования к отчету по ИДЗ:
1. Лексический анализатор - регулярная грамматика для выделения лексем.
Обязательно обоснование детерминированности разбора по данной грамматике.
2. Синтаксический анализатор - КС-грамматика для описания реализуемого модельного языка, включая грамматику выражений.
Обязательно обоснование применимости метода рекурсивного спуска для данной грамматики.
3. Внутреннее представление программы (выражений) - дерево операций (варианты 1-4) или ПОЛИЗ выражений и операторов (для всех вариантов). ПОЛИЗ необходимо предоставить для всех операторов, в том числе, которые не проходились на лекции, и бонусов.
4. Семантический анализатор - описание полноты обработки смысловых ошибок на этапе разбора и интерпретации.
5. Диаграмма программных классов построенного интерпретатора (вычислителя).
6. Набор тестов обоих видов и скриншоты работы.
7. Текст программы-интерпретатора с комментариями.
В дополнение Вы присылаете проект (для запуска под VS 2010 и ниже) или необходимые для запуска *.cpp,*.c и *.h файлы.
Отсутствие любого из указанных пунктов в отчете ведет к его отправке на доработку.

2) Тестовые примеры
Требования к набору тестовых файлов:
1. Положительные тесты должны демонстрировать все реализованные операции языка, как по отдельности, так и в комбинациях.
2. Именно к семантическому анализатору Вы должны приложить BAD_тесты в достаточном количестве.
Отсутствие достаточного количества тестов ведет к отправке на доработку без объяснения причин.
* Много - не значит хорошо. При составлении тестов внимательно смотрите на требования к отчету и программе.

3) Программа (проект)
Требования к исходному коду:
1. Программа без комментариев по конкретным особенностям и способам реализации:
Лексический анализ; Синтаксический анализ; Семантический анализ (контроль контекстных условий);Генерация внутреннего представления программы;Интерпретация программы на внутреннем языке;
не рассматривается. Если Вам понятна Ваша программа - сделайте ее понятной для преподавателя.
2. Режим интерпретации программы (выражения) на модельном языке должен обеспечивать ее неоднократную интерпретацию при различных входных данных в рамках одного запуска программы-интерпретатора. Для этого должно сохраняться единожды построенное внутреннее представление интерпретируемой программы (выражения).
* Необходимо один раз преобразовать исходную программу в ПОЛИЗ, чтобы можно было проводить повторные вычисления в цикле при условии новых входных данных с команды read().
Отсутствие любого из указанных пунктов в программе ведет к ее отправке на доработку.
3^*) Бонусы
Бонус - возможность реализовать дополнительный функционал в ИДЗ, подняв свою оценку выше 10 баллов.
Бонусы должны быть согласованы с семинаристом (в тексте ИДЗ приведены примеры, реальные бонусы чуть сложнее) и заявлены на реализацию студентом.
Поскольку Вы получаете возможность увеличить свою оценку выше 10 баллов, то неправильная реализация бонусов будет трактоваться как -1 балл за каждый неправильно реализованный бонус.
Максимальное число бонусов для 1 студента - 3 (в редких случаях, 4).
Примеры:
1. int a; float b; bool c; read(a,b,c); write("b=%2, a=%1\n",a,b);
2. int a=(int)(4/3); float b=(float)(4/3). 2*. char c=(char)"a"; string ch=(string)'a'; + операции над строками.
3. Цикл for + один циклов do while или repeat until.
4. Массив array (!) или список list.
5. Указатели и операции с динамической памятью: *, new, delete.
6. Определение функции внутри программы на модельном языке.
7. ...
% - не бонус на 1 балл!
4) Сдача программы / получение задания
При успешном прохождении предыдущих трех этапов Вы

либо сдадите программу по своим положительным и отрицательным тестовым примерам,

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

Остальные правила остаются:
Нахождение ошибки влияет на оценку по количеству и качеству найденных преподавателем ошибок, сдача ИДЗ (без учета пункта 4) Задание) после сроков ведет к вычитанию 1-2 баллов.

Раздел Контрольная работа:
Псевдокод
Системы программирования - для подготовки ко 2-й к.р.

Раздел Лабораторные:
Сдача лабораторных осуществляется только в рамках занятия в аудитории.
Каждое из заданий дается возможность сдать на 1 балл ровно один раз.
Обработка исключений не предусматривается при вводе букв вместо цифр и т.п..
Все остальные исключения должны обрабатываться.

Раздел Домашние задания:
Проект+ДС+отчет отправляется одним архивом на почту преподавателя.
Недостаточное количество тестовых примеров приводит к переносу сдачи программы на семинар.
Неправильная грамматика или ДС ведут к понижению оценки как минимум вдвое.
Нахождение контрпримера к программе дает возможность поставить оценку 0 за ДЗ или разрешить доделать с понижением балла.
Самостоятельный вариант задания и дополнительные задания согласовываются с семинаристом группы и приветствуются только для итогового задания.
В итоговом задании должен быть использован ПОЛИЗ для операторов и выражений. Требвоания к итоговому заданию уточняются у семинариста.

Возможные проблемы и способы их решения:
0. Обязательно поставьте последний Service Pack на Visual Studio.
Старайтесь использовать версию 2010 и более ранние.
Перед сдачей программы ставьте по умолчанию язык ввода - английский.
1. Если не находится модуль, дополнительная библиотека и т.п.
Решение: Пропишите полный путь, в некоторых случаях замените одинарный \ на двойной \\.
Старайтесь не сохранять проекты в рабочих директориях "Мои документы", "Загрузки", названиями папок с русскими буквами и пробелами, системных папках, которые могут блокироваться антивирусом.
2. Переключайте в свойствах проекта "Использовать многобайтовую кодировку" вместо "Юникода" для запуска MFC программ с сообщениями на русском языке.
3. В ДЗ№3 при прописывании дополнительных зависимостей иногда также требуется прописать полный путь к библиотеке.
4.. В свойствах проекта, если Вы работаете под 11(XX) студией, вставьте
Project--> Property--> Configureation ..--> General --> PlatformToolset : v100 (у Вас 110)
чтобы можно было запустить на версии 2010.

Архив 2012/2013: не для студентов
Домашнее задание №1
Домашнее задание №2
Домашнее задание №3
Домашнее задание №4
Домашнее задание №5
Итоговое домашнее задание

Материалы лабораторных и ДЗ подготовлены Е.И. Большаковой, доцентом кафедры анализа данных и искусственного интеллекта,а также А.А.Носковым, бывшим преподавателем этой кафедры.
Материалы сайта подготовлены старшим преподавателем кафедры анализа данных и искусственного интеллекта Макаровым И.А.

*б туцб вудуеую
6ю Определение функции внутри программы