Практикум (4 курс, весенний семестр) — различия между версиями

Версия 19:13, 31 октября 2013

Общая информация

Семинар проходит по понедельникам с 12:15 до 13:45. Практические занятия и самостоятельные работы проходят в аудитории 604.

Семинары ведет Шуплецов Михаил Сергеевич.

Второе домашнее задание

Необходимо спроектировать и реализовать при помощи СУБД Postgres базу данных для информационной поддержки учебного процесса.

Текстовое описание базы данных.

Задание разбито на несколько этапов:

• создание первичной структуры базы данных;
• написание типовых запросов;
• оптимизация базы данных;
• нормализация базы данных;
• написание правил и других проверок для поддержания целостности базы данных.

Каждый этап оценивается отдельно.

Первое домашнее задание

Необходимо спроектировать и реализовать при помощи СУБД Postgres базу данных для хранения инфомации о сложности булевых функций небольшого числа переменных, а также об известных минимальных и близких к ним контактных схемах (и схемах из функциональных элементов --- за дополнительные баллы ). База данных должна содержать все необходимые индексы, первичные и внешние ключи, а также минимальный набор проверок целостности и корректности ввода данных в таблицы.

База данных должна быть заполнена с использованием следующей информации:

• Таблица сложностей функций и минкодов

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

• Таблица контактных схем

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

Опишем формат представления контактной схемы. Пусть задана контактная схема, содержащая $n, n>1$, вершин и $k$, $k \ge 0$, контактов. Считается, что все вершины схемы пронумерованы начиная с $0$ до $(n-1)$. Переменной $x_i$, $1 \leqslant i \leqslant 5$, присвоен номер $i$. Каждый контакт описывается четверкой чисел, где первые два числа являются номерами смежных с контактом вершин схемы, третье число характеризует номер переменной, приписанной контакту, а четвертое число~--- степень этой переменной ($0$~--- переменная входит с отрицанием, $1$~--- переменная входит без отрицания). Для описания контактной схемы используется следующее представление (в расширенной форме Бекуса---Наура; как обычно, фигурные скобки означают возможность пропуска либо повторения произвольное число раз):

             <номер вершины> ::= '0' | ... | 'n-1'
             <номер переменной> ::= '1' | ... | '5'
             <степень переменной> ::= '0' | '1'
             <контакт> ::= <номер вершины> ' ' <номер вершины> ' ' <номер переменной>
             ' ' <степень переменной>
             <контактная схема> ::= <номер вершины> ' ' <номер вершины> { ' ' <контакт> }

Примечание. Лексема \tech{<контакт>} входит ровно $k$ раз. Первые два вхождения лексемы \tech{<номер вершины>} характеризуют входной и выходной полюс схемы соответственно.

Опишем формат представления схемы из функциональных элементов. Формулы Бекуса---Науэра для строк, описывающих СФЭ, имеют следующий вид:

                      <код ФЭ> ::= '0' | '1' | '2' | '3'
                      <номер вершины> ::= <НЕОТРИЦАТЕЛЬНОЕ ЦЕЛОЕ>
                      <список дочерних вершин> ::= <номер вершины> { ' ' <номер вершины> }
                      <описание вершины> ::= <номер вершины> ',' <код ФЭ> ','
                      <список дочерних вершин>
                      <список вершин> ::= <описание вершины> { ';' <описание вершины> }
                      <описание СФЭ> ::= <список вершин> '.'

Считается, что любая СФЭ всегда содержит шесть специальных вершин, которые служат вспомогательным целям и не учитываются при подсчёте её сложности~--- это специальная выходная вершина и одна вершина на каждую из входных переменных. Выходная вершина является стоком; в нее ведет единственная дуга, которая исходит из вершины, являющейся выходом СФЭ. Остальным специальным вершинам взаимно однозначно сопоставлены символы входных переменных $x_1$, $x_2$, $x_3$, $x_4$, $x_5$; они является истоками.

Для описания СФЭ в списке \tech{<список вершин>} перечисляются (в произвольном порядке) те и только те вершины СФЭ, из которых исходит хотя бы одна дуга. Каждая вершина СФЭ получает в описании уникальный номер \tech{<номер вершины>}. Номер выходной вершины равен нулю. Вершина, которой приписана переменная~$x_i$, $1 \leqslant i \leqslant 5$, имеет номер~$i$. Остальные вершины получают номера, строго большие $5$. Кодами функциональных элементов, реализующих конъюнкцию, дизъюнкцию, отрицание являются соответственно числа 1, 2, 3. Для вспомогательных вершин СФЭ \tech{<код ФЭ>} равен 0, для остальных вершин \tech{<код ФЭ>} принимает значение, равное коду функционального элемента, приписанного данной вершине. Список \tech{<список дочерних вершин>} перечисляет номера тех и только тех вершин, в которые из описываемой вершины исходят дуги.

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

• описание структуры спроектированной базы данных в виде .sql скрипта, позволяющего создать эту базу данных в системе Postgres;
• описание запросов к спроектированной базе и результатов их выполнения.

В отчете должны содержаться следующие запросы:

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

Дополнительные баллы начисляются за реализацию в базе данных проверки корректности ввода схемы (ее представления).