Список вопросов к зачету

Вопросы:

1. Асимптотическая сложность алгоритмов;
2. Алгоритм Кнута-Морриса-Пратта. Префикс функция. Алгоритм нахождения подстроки в строке;
3. Префиксное дерево. Построение, поиск, удаление элементов;
4. Алгоритм Ахо-Корасика: нахождение массива строк в тексте;
5. Алгоритм Рабина-Карпа. Хеширование строк. Алгоритм нахождения подстроки в строке.
6. Графы. Классификация. Способы представления;
7. Обход графа в ширину, в глубину. Нерекурсивные алгоритмы обходов;
8. Топологическая сортировка;
9. Алгоритм Дейкстры. 
10. Алгоритм Форда-Беллмана;
11. Алгоритм Прима;
12. Дерево отрезков для нахождение суммы на интервале. Построение, обновление, поиск суммы;
13. Дерево Фенвика для нахождение суммы на интервале. Построение, обновление, поиск суммы;
14. Система непересекающихся множеств.

Прием долгов по Технологии Программирования (18.06.16)

Последний прием долгов по предмету Технология Программирования в весенний семестр 2016 будет в субботу 18 июня с 10:00 до 12:00 в 7-405.

Прием долгов по Технологии Программирования (15.06.16)

Прием долгов по предмету Технология Программирования будет в среду 15 июня с 18:00 до 20:00 в 7-405.

Вопросы на экзамен 2016

1. Жизненный цикл (ЖЦ) программного обеспечения (ПО). Итерационные модели ЖЦ. Каскадная модель ЖЦ;
2. Стадии ЖЦ; V-образная, XP модель ЖЦ;
3. Объектно-ориентированное программирование (ООП). Принципы ООП;
4. ООП: Отношение между классами;
5. С++: Классы – объявление, конструкторы, деструкторы, работа с памятью;
6. Динамическое и статическое выделения памяти;
7. С++: Наследование;
8. С++: Перегрузка унарных и бинарных операторов;
9. Асимптотическая сложность; 
10. Контейнеры С++: vector;
11. Контейнеры С++: list;
12. Контейнеры С++: deque;
13. Контейнеры С++: set;
14. Контейнеры С++: map;
15. Контейнеры С++: stack;
16. Контейнеры С++: queue;
17. Отладка программ: классификация ошибок, основные приемы локализации ошибок;
18. С++: исключения. Основные исключения STL;
19. Абстрактные классы. C++: чистые виртуальные функции;
20. С++: шаблоны функций и классов;
21. Тестирование: классификации подходов к тестированию (типы тестирования);
22. Паттерны программирования: Одиночка, Наблюдатель;
23. Паттерны программирования: Декоратор, Фабричный метод;
24. Паттерн (принцип) программирования: Получение ресурса – есть инициализация (RAII);
25. Умные указатели: unique_ptr, auto_ptr;
26. Умные указатели: shared_ptr;
27. Умные указатели: weak_ptr.

Расписание занятий и консультаций до экзамена

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

28 мая:
  - с 11:50 до 15:10 в 7-410;
4 июня:
 - с 10:10 до 11:30 в 7-405;
 - с 11:50 до 15:10 в 7-410;
11 июня:
 - с 10:10 до 11:30 в 7-405;
 - с 11:50 до 15:10 в 7-410.

Технология Программирования - Лекции 2016

Лекции.

Пример работы с xml объектами в C++

Установка

В данном разделе приведена инструкция по установке в Microsoft Visual Studio 2012, возможно, для других версий подтребуется дополнительные действия, но общая логика останется прежней. 

1. Скачать библиотеку pugixml. На странице проекта нужно нажать на кнопку "Download ZIP";
2. Распаковать скаченный zip архив;
3. В распакованном проекте открыть проект MVS в каталоге "pugixml-1.7\scripts". Открывать желательно проект той версии MVS, которая у вас установлена. В моем случаи MVS 2012 не было, поэтому был открыт "pugixml_vs2015.vcxproj".
4. Открытый проект необходимо собрать и в результате будет надпись вида:1>------ Rebuild All started: Project: pugixml_vs2015, Configuration: Debug Win32 ------1>Project file contains ToolsVersion="14.0". This toolset is unknown or missing. You may be able to resolve this by installing the appropriate .NET Framework for this toolset. Treating the project as if it had ToolsVersion="4.0".1>  pugixml.cpp1>  pugixml_vs2015.vcxproj -> C:\Users\rdo\Downloads\pugixml-1.7\pugixml-1.7\scripts\vs2015\Win32_Debug\pugixml.lib========== Rebuild All: 1 succeeded, 0 failed, 0 skipped ==========
5. При сборке может дополнительно потребоваться изменить настроки компилятора, например, для MVS 2012 необходимо изменить версию "Platform Toolset" (Project -> Properties -> General -> Platform Toolset) с "v140" на "Visual Studio 2012 (v110)";
6. Создать новый проект в MVS, если он еще не был создан.
7. Из распакованного архива в новый проект скопировать файлы "pugixml.hpp" и "pugiconfig.hpp" из каталога "pugixml-1.7\src";
8. Открыть проект, в заголовочные файлы проекта добавить скопированные файлы.
9. В настройках проекта изменить следующие настроки:
1. Project -> Properties -> Linker -> General: В поле "Additional libraries directories" прописать путь до каталога, в котором лежит скопилированная библиотека pugixml.lib (см. п4.). Например: "C:\Users\rdo\Downloads\pugixml-1.7\pugixml-1.7\scripts\vs2015\Win32_Debug";
2. Project -> Properties -> Linker -> Input: В поле "Additional dependencies" указать сборщику, что нужно в проекте использовать дополнительную библиотеку "pugixml.lib". В итоге в поле должно быть запись вида "pugixml.lib;%(AdditionalDependencies)";
10. Библиотека добавлена. 

Примеры работы с библиотекой

Полный список примеров можно посмотреть на еще одном сайте проекта.

Считывание с файла/строки

#include <iostream>

#include <iostream>

#include "pugixml.hpp"

std::string XML_CONTENT = "<xml>"

  "<element1>value1</element1>"

  "<element2>value2</element2>"

  "<element3>value3</element3>"

  "<element4>"

    "<element5 attr=\"attribute-value\">5</element5>"

    "<element6/>"

  "</element4>"

  "</xml>";

int main() {

  std::cout << "Example 1: loading from string/file" << std::endl;

  pugi::xml_document doc;

  pugi::xml_parse_result result 

                      = doc.load_string(XML_CONTENT.c_str());

  //pugi::xml_parse_result result = doc.load_file("filename.xml");

  std::cout << "Load result:" << result.description() << std::endl;

  return 0;

}

-------

Вывод на консоль:

Example 1: loading from string/file
Load results:No error

Получение значений

std::cout << "Example 2: getting elements value" << std::endl;

std::cout << "xml->element1: " << doc.child("xml")

                                     .child("element1")

                                     .text()

                                     .as_string() << std::endl;

std::cout << "xml->element4->element5: " << doc.child("xml")

                                               .child("element4")

                                               .child("element5")

                                               .text()

                                               .as_int() << std::endl;

std::cout << "xml->element4->element6: " << doc.child("xml")

                                               .child("element4")

                                               .child("element6")

                                               .text()

                                                .as_bool() << std::endl;

std::cout << "xml->element4->element5(attribute): " 

          << doc.child("xml")

                .child("element4")

                .child("element5")

                .attribute("attr")

                .as_string() << std::endl;

-------

Вывод на консоль:

Example 2: getting elements value
xml->element1: value1
xml->element4->element5: 5
xml->element4->element6: 0
xml->element4->element5(attribute): attribute-value

Итерирование

int Count(pugi::xml_node_iterator& begin, pugi::xml_node_iterator& end) {

  int r = -1;

  while (begin != end) {

    ++r; 

    ++begin;

  }

  return r;

}

void IterateNode(pugi::xml_node& root, int offset = 0) {

  for (pugi::xml_node node: root.children()) {

    int i = offset;

    while (i > 0) {

      std::cout << " ";

      --i;

    }

    if (Count(node.begin(), node.end()) > 0) {

      std::cout << "Node: " << node.name() << " :" << std::endl;

      IterateNode(node, offset + 2);

      return;

    }

    std::cout << "Node: " << node.name() << "; value: " << node.text().as_string() << std::endl;

  }

}

//main

std::cout << "Example 3: children iteration" << std::endl;

IterateNode(doc.child("xml"));

-------

Вывод на консоль:

Example 3: children iteration
Node: element1; value: value1
Node: element2; value: value2
Node: element3; value: value3
Node: element4 :
  Node: element5; value: 5
  Node: element6; value:

Файл проекта

Файл проекта с примерами.

Изменение в варианте №9 курсовой работы

В варианте №9 использование библиотеки wxWidgets необязательно.

Пример работы с json объектами в C++

Введение

К сожалению, в стандартной библиотеке С++ (STL) нет инструментов для работы с json объектами. Но существует достаточно много реализаций библиотек для всех языков программирования, в том числе и для С++. 

В данной статье приведен пример работы с json объектами с помощью библиотеки rapidjson. Все примеры из статьи есть в проекте (см. ниже).

Установка

В данном разделе приведена инструкция по установке в Microsoft Visual Studio 2012, но, почти со 100% вероятностью, она подойдет для любой версии MVS. 

1. Если проект в MVS еще не создан, но необходимо его создать;
2. Скачать библиотеку rapidjson. На странице проекта нужно нажать на кнопку "Download ZIP";
3. Распаковать скаченный zip архив;
4. Из распакованного архива в проект скопировать каталог "rapidjson-master\include\rapidjson" в каталог "rapidjson" в проекте;
5. Открыть проект, в заголовочные файлы проекта добавить содержимое скопированного каталога.
6. Библиотека добавлена. 

Примеры работы с библиотекой

Полный список примеров можно посмотреть на еще одном сайте проекта.

Модификация и вывод на экран

#include "rapidjson/document.h"

#include "rapidjson/writer.h"

#include "rapidjson/stringbuffer.h"

#include <iostream>

#include <string>

using namespace rapidjson;

int main() {

  std::string json = "{\"type\":\"test\",\"number\":1}";

  Document document;

  document.Parse(json.c_str());

  // Example 1: Json modification, writing Json to console

  Value& s = document["number"];

  s.SetInt(s.GetInt() + 1);

  StringBuffer buffer;

  Writer<StringBuffer> writer(buffer);

  document.Accept(writer);

  std::cout << buffer.GetString() << std::endl;

  return 0;

}

-------

Вывод на консоль:

{"type":"test","number":2}

Начинается этот пример с создания основного объекта "Document document" и парсинга json документа (в данном примере он получен из строки, но также можно либо предварительно считать данные из файла в строку, либо создать входной поток (см. следующий пример)). Далее создается ссылка на значение элемента number, которой меняется значение: "Value& s = document["number"]; s.SetInt(s.GetInt() + 1);". Пример заканчивается выводом содержимого измененного json объекта на консоль при помощи объектов классов StringBuffer и Writer<StringBuffer>.

Считывание с файла

  //Example 2: Getting json from a file

  std::ifstream ifs("test-json-file.json");

  IStreamWrapper isw(ifs);

  Document documentFromFile;

  documentFromFile.ParseStream(isw);

В данном примере создается поток ifs, затем он передается в объект-обвертки isw. Созданный объект входного потока isw передается в метод ParseStream, с помощью которого считывается json файл и инициализируется объект documentFromFile.

Итерирование по json объекту

Содержимое файла "test-json-file.json".

{

  "string": "test",

  "number": 1,

  "array": [1,2,3,4,5],

  "object": {

    "element1": 1,

    "element2": 2,

    "element3": 3

  }

}

std::string GetElementValue(const Value& val) 

{

  if (val.GetType() == Type::kNumberType)

    return std::to_string(val.GetInt());

  else if (val.GetType() == Type::kStringType)

    return val.GetString();

  else if (val.GetType() == Type::kArrayType)

    return "Array";

  else if (val.GetType() == Type::kObjectType)

    return "Object";

  return "Unknown";

}

  // Example 3: Iterating over elements

  Value::ConstMemberIterator iter = documentFromFile.MemberBegin();

  for (;iter != documentFromFile.MemberEnd(); ++iter) {

    std::cout << "Element name:" 

              <<  iter->name.GetString() 

              << "; element value: " 

              << GetElementValue(iter->value) 

              << std::endl;

  }

-------

Вывод на консоль:

Element name:string; element value: test

Element name:number; element value: 1

Element name:array; element value: Array

Element name:object; element value: Object

В данном примере создается итератор iter по объекту documentFromFile и на консоль выводятся названия json элементов и их значения.

Файл проекта

Файл проекта с примерами.

Изменение почтового адреса

romannikov at corp.nstu.ru - новый адрес, по которому можно со мной связаться по рабочим вопросам.