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

Инфиксная, префиксная и постфиксная формы записи выражений

Инфиксная нотация — это форма записи математических и логических формул, в которой операторы записаны в инфиксном стиле между операндами, на которые они воздействуют. Эта запись используется как более естественная для человека.

Пример, 2 + 2
В инфиксной нотации, в отличие от префиксной и постфиксной, скобки, окружающие группы операндов и операторов, определяют порядок, в котором будут выполнены операции. При отсутствии скобок операции выполняются согласно правилам приоритета операторов.
Польская нотация (запись), также известна как префиксная нотация (запись), это форма записи логических, арифметических и алгебраических в ыражений. Характерная черта такой записи —
оператор располагается слева от операндов. Если
оператор имеет фиксированную арность, то в такой записи будут отсутствовать круглые скобки и она может быть интерпретирована без неоднозначности. Несмотря на то, что польская запись не используется в математике, она широко применяется в информатике.
Пример, + 2 2
Обратная польская запись (англ. Reverse Polish notation, RPN, Постфиксная запись) — форма
записи математических и логических выражений, в которой операнды расположены перед знаками операций. Также именуется как обратная бесскобочная запись, постфиксная нотация, бесскобочная символика Лукасевича, польская инверсная запись, ПОЛИЗ.
Пример, 2 2 +
3. Задание на Практическую работу


Решить следующие задания:


Задание 2. Дано арифметическое выражение. Необходимо:

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

Вариант 1 M+K/(L–N*P)+T*Y	Вариант 2 ((Y+X*K)*(G–S)+T)*(F–K)+D	Вариант 3 (T–S/R)*(Z+X+Y/Q)
Вариант 4 (A*B+(C–D)*F)/G–H	Вариант 5 (M*L–(N+K*F)/S)*T	Вариант 6 P*(A–Q–S)+L/(D+K)
Вариант 7 F+D–G*(X+Y–Z)	Вариант 8 K*T*(L–E/R+S)	Вариант 9 (F*(P–G)+Z/K)*D–T
Вариант 10 M–C/L/(S+R*B)	Вариант 11 (A–P+R/(B–C))/(K+L*F)	Вариант 12 (((M+N)*R+K)*D+F)/G
Вариант 13 S/P–Y*X+D/F	Вариант 14 A/(B+C)–D*F+G	Вариант 15 R+M*(F–K/N)+G*T

Вариант 16 (M-K)/L+N*(P-T)*Y	Вариант 17 ((Y-X*K)*(G+S+T)*F+(K-D)	Вариант 18 (T+S)/R*(Z+(X-Y)/Q)
Вариант 19 (A*(B+C)–D)*F)/(G–H)	Вариант 20 (M*(L–N)+K*F)/S)*T	Вариант 21 (P*A–(Q–S)+L)/D+K
Вариант 22 (F+D)–G*X+(Y–Z)	Вариант 23 (K+T)*(L–E)/(R+S)	Вариант 24 (F*P–(G+Z)/K)*(D–T)-L
Вариант 25 (M–C)/L/S+(R-B)/G	Вариант 26 (A–(P+R)/(B–C))/K*(L+F)	Вариант 27 ((M+N)*R+K)*((D+F)/G)
Вариант 28 S/(P–Y)*(X+D)/F	Вариант 29 A/(B+C)–D*(F+G)/Q	Вариант 30 (R+M)*(F–K)/(N+G)*T

4. Содержание отчета
В отчете следует указать:

• 
  Название работы.
  
• 
  Цель работы.
  
• 
  Теоретическая часть.
  
• 
  Выполненное задание.
  
• 
  Заключение (выводы).
  
• 
  Литература.
  

5. Контрольные вопросы:

1. 
   Понятие графа; ориентированные и неориентированные графы; способы задания графов.
   
2. 
   Часть графа, суграф, покрывающий суграф, подграф на заданных вершинах, звездный граф.
   
3. 
   Операции с частями графа (дополнение, объединение, пересечение).
   
4. 
   Циклы, маршруты, цепи, простые цепи в графах.
   
5. 
   Связность, степени вершин графа, эйлеров цикл, эйлерова цепь в графах.
   
6. 
   Остовное дерево графа. Построение остовного дерева с минимальным весом.
   
7. 
   Расстояние между вершинами графа; диаметр, радиус и центр графа.
   
8. 
   Протяженность между вершинами графа; диаметр протяженности, радиус протяженности и центр протяженности графа.
   
9. 
   Привести пример графа, удовлетворяющего строгому неравенству теоремы Уитни.
   
10. 
    Привести примеры графов, которые имеют все периферийные и все центральные вершины.
    
11. 
    Что такое эксцентриситет?
    
12. 
    Чем диаметр графа отличается от его радиуса (дайте их определения)?
    
13. 
    Чем простая цепь отличается от цикла?
    
14. 
    Что такое маршрут?
    
15. 
    Что такое число рёберной связности?
    
16. 
    Дайте определения моста и цикла.