Алгоритмы и реализация свертки описаний множеств в индексированные конструкции для системы фрагментированного программирования LuNA Пушкова Е.А., 2к маг. ММФ НГУ Руководитель: Перепелкин В.А. 2013

2 Постановка задачи Алгоритм в ФП - это потенциально-бесконечный граф операций и переменных. Пси-операция – множество операций. В текущем представлении - подграф. Конечное представление Простота с точки зрения обслуживания Исполнительной Системой Снижение недетерминизма Легкость извлечения способа реализации

3 Постановка задачи Разработать и реализовать внутренне представление прикладного алгоритма для автоматического преобразования исходного представления алгоритма в множество пси-операций.

4 n e x0x0 x1x1 xixi x i+1 y0y0 y1y1 yiyi y i+1 b1b1 aiai a0a0 b0b0 b i+1 bibi i i + 1 i i + 1 n e y xa b Идея решения

5 Идея алгоритма Обходом графа помечаем вершины некоторыми метками Множество вершин с одинаковыми метками образуют потенциальную пси-операцию В результате получим некоторое покрытие графа – множество способов формирования пси-операций в алгоритме

6 Способ хранения данных Граф – таблица смежности Допустимо, так как размерность графа мала Запись таблицы - дуга Индексное выражение

7 Представление данных class GraphFA { private: EdgeLabel **m_pAdjTable; std::vector mNodeList; std::vector mReadyCFs; std::vector mCalculatedDFs; void setAdjTableSize(int vertexCount); void addNode(NodeType type, std::string name); void addEdgeLabel(std::string from, std::string to, bool par, int constant); const int getId(std::string nodeName); const std::string getName(int id); public: GraphFA(); ~GraphFA(); bool getData(std::istream &in); void traversal(); };

8 Заключение Разработано внутреннее представление данных со следующими ограничениями: Нет учета наличия диапазона индексов Дальнейшие планы: Снятие текущих ограничений Реализация алгоритма построения пси-операций с использованием текущего представления

9 Q&A