41618

Автоматизация кодирования графа переходов

Лабораторная работа

Информатика, кибернетика и программирование

В результате выполнения данной лабораторной работы я приобрёл навыки по автоматизации соседнего кодирования графа переходов автомата Мили. Соседнее кодирование реализовано по алгоритму, описаному выше...

Русский

2013-10-24

145 KB

5 чел.

  Национальный Технический Университет Украины

“Киевский Политехнический Институт”

Факультет Информатики и Вычислительной Техники

Кафедра вычислительной техники

Лабораторная работа №4

по курсу «Автоматизация проэктирования

компьютерных систем»

Выполнил:

студент IV курса

Группы ИВ-83

Чуб Александр

Киев

2011 г.

Тема: Автоматизация кодирования графа переходов.

Номер зачётной книжки: 831910 =100000011111112;

 

Описание алгоритма создания соседнего кодирования(private void createCoding(GraphNode previousNode, GraphNode node)):

  1.  Проверяем, имеет ли текущая вершина какой-либо код. Если нет, то п.2, если имеет, то п.5.
  2.  Если нет вершины предыдущей этой, то присваиваем ей код «0».
  3.  Иначе пытаемся сгенерировать код (если не успешно, то добавляем ко всем размеченным вершинам бит «0»), устанавливаем код в вершину.
  4.  Кодируем все соседние вершины.
  5.  Текущая вершина имеет код, то проверяем его, сколькими символами он отличается от кода предыдущей вершины.
  6.  Если их больше одного, то добавляем новую вершину и пытаемся создать кодиование между ними.

private GraphNode insertNode(GraphNode prevNode, GraphNode nextNode) – Добавляет новую вершину между текущей парой, без сигналов.

private int unequalsBits(String code1, String code2) – Возвращает количество различных битов между двумя вершинами.

private void addBit() – Добавляет один бит «0» ко всем размеченным вершинам.

private String getUniqueCodeByPrevious(GraphNode previousNode) - пытается получить код, который будет отличаться только на один бит, если не существует такого кода, возвращает null.

Скриншоты программы:

Листинг программы:

import java.io.Serializable;

import java.util.ArrayList;

public class NewGraph implements Serializable{

 private static final long serialVersionUID = 1L;

 private ArrayList<GraphNode> graphNodes;

 private ArrayList<String> signals;

 private int numOfQ;

 

 public NewGraph(Graph grph) {

 signals = grph.getSignals();

 ArrayList<String> nodesNames=grph.getNodes();

 graphNodes = new ArrayList<GraphNode>();

 for(String name:nodesNames){

  graphNodes.add(new GraphNode(name,graphNodes.size()));

 }

 ArrayList<Connection> links = grph.getConnections();

 for(Connection link:links){

  ArrayList<String> xSignals = link.getXSignals();

  ArrayList<String> ySignals = link.getYSignals();

  int fromNode = link.from()-1;

  int toNode = link.to()-1;

  addGraphLink(fromNode, toNode, xSignals, ySignals);

 }

}

 

 public void addGraphLink(int fromNode, int toNode, ArrayList<String> xSignals, ArrayList<String>ySignals){

 GraphLink graphLink = new GraphLink(graphNodes.get(toNode), xSignals, ySignals);

 GraphNode currentNode = graphNodes.get(fromNode);

 currentNode.addLinkedNode(graphLink);

 graphNodes.set(fromNode, currentNode);

 

}

 

 private String getUniqueCodeByPrevious(GraphNode previousNode) {

 String code = null;

 String prevCode = previousNode.getBitCode();

 for (int i = 0; i < prevCode.length(); i++) {

  String newCode = "";

  for (int j = 0; j < prevCode.length(); j++) {

   if (i != j) {

    newCode += prevCode.charAt(j);

   } else {

    if (prevCode.charAt(j) == '1') {

     newCode += '0';

    } else {

     newCode += '1';

    }

   }

  }

  if (!hasCode(newCode)) {

   code = newCode;

   break;

  }

 }

 return code;

}

 private boolean hasCode(String code) {

 for (GraphNode node : graphNodes) {

  if (code.equals(node.getBitCode())) {

   return true;

  }

 }

 return false;

}

 private void addBit() {

 for (GraphNode node : graphNodes) {

  if (node.getBitCode() != null && !node.getBitCode().isEmpty()) {

   node.setBitCode('0' + node.getBitCode());

  }

 }

}

 

 private int unequalsBits(String code1, String code2) {

 int k = 0;

 for (int i = 0; i < code1.length(); i++) {

  if (code1.charAt(i) != code2.charAt(i)) {

   k++;

  }

 }

 return k;

}

 

 

 public void neighborCoding() {

 if (graphNodes.size() > 0) {

  GraphNode firstNode = graphNodes.get(0);

  createCoding(null, firstNode);

  numOfQ = graphNodes.get(0).getBitCode().length();

 }

}

 

 

 private void createCoding(GraphNode previousNode, GraphNode node) {

 if (node.getBitCode() == null || node.getBitCode().isEmpty()) {

  if (previousNode == null) {

   node.setBitCode("0");   

  } else {

   String newCode = getUniqueCodeByPrevious(previousNode); 

   if (newCode == null) {       

    addBit();        

    newCode = getUniqueCodeByPrevious(previousNode);

   }

   node.setBitCode(newCode);

  }

  ArrayList<GraphLink> linkedNodes = node.getLinkedNodes();

  for (GraphLink linkedNode : linkedNodes) {

   createCoding(node, linkedNode.linkedNode);

  }

 } else {

  if (unequalsBits(previousNode.getBitCode(), node.getBitCode()) > 1) {

   GraphNode newNode = insertNode(previousNode, node);

   createCoding(previousNode, newNode);

  }

 }

}

 

 private GraphNode insertNode(GraphNode prevNode, GraphNode nextNode){

 String newName = "Z"+ (graphNodes.size()+1);

 GraphLink currentGraphLink = prevNode.getLinkByID(nextNode.getID());

 if(currentGraphLink == null){

  System.out.println("Couldn't get link from"+prevNode.getID()+" to " +nextNode.getID());

 }

 GraphNode insertedNode = new GraphNode(newName,graphNodes.size());

 graphNodes.add(insertedNode);

 currentGraphLink.linkedNode=insertedNode;

 addGraphLink(insertedNode.getID(),nextNode.getID(),

    new ArrayList<String>(), new ArrayList<String>());

 return insertedNode;

}

 

 public void output(){

 for(GraphNode gNode:graphNodes){

  System.out.println(gNode.toString());

 }

 System.out.println("size "+graphNodes.size());

}

 

 

 public int getNumOfQ(){

 return numOfQ;

}

 

 public ArrayList<String> getSignals(){

 return signals;

}

 

 public GraphNode getNodeById(int i){

 return graphNodes.get(i);

}

 

 

 public ArrayList<GraphNode> getNodes(){

 return graphNodes;

}

 

}

import java.io.Serializable;

import java.util.ArrayList;

public class GraphNode implements Serializable {

 private static final long serialVersionUID = 1L;

 private ArrayList<GraphLink> linkedNodes;

 private String bitCode = null;

 private String name;

 private int id;

 

 

 public GraphNode(String name, int id){

 this.name = name;

 this.id = id;

 linkedNodes = new ArrayList<GraphLink>();

}

 

 public String getBitCode(){

 return bitCode;

}

 

 public void setBitCode(String bCode) {

 bitCode = bCode;

}

 

 public ArrayList<GraphLink> getLinkedNodes(){

 return linkedNodes;

 }

 

 public void addLinkedNode(GraphLink newNode){

 linkedNodes.add(newNode);

}

 

 public String getName(){

 return name;

}

 

 public int getID(){

 return id;

}

 

 public GraphLink getLinkByID(int id){

 for(GraphLink graphLink: linkedNodes){

  if(graphLink.linkedNode.getID()== id){

   return graphLink;

  }

 }

 return null;

}

 

 public String toString(){

 String linksWith ="  ";

 for(GraphLink graphLink: linkedNodes){

  linksWith+= graphLink.linkedNode.getName();

  for(int i = 0; i < graphLink.xConditions.size(); i++){

   linksWith += graphLink.xConditions.get(i)+"/"+graphLink.yConditions.get(i);

  }

  linksWith+="; ";

 }

 return name+"  "+bitCode+linksWith;

 }

 

}

import java.io.Serializable;

import java.util.ArrayList;

public class GraphLink implements Serializable {

 private static final long serialVersionUID = 1L;

 public GraphNode linkedNode;

 public ArrayList<String> xConditions;

 public ArrayList<String> yConditions;

 

 

 public GraphLink(GraphNode linked, ArrayList<String> xCond, ArrayList<String> yCond){

 linkedNode = linked;

 xConditions = xCond;

 yConditions = yCond;

}

 

 

 public String signalsToString(){

 String signals ="";

 if(xConditions.size()==0){

  return signals;

 }

 signals+=xConditions.get(0)+"/"+yConditions.get(0);

 for(int i = 1; i<xConditions.size();i++) {

  signals+="OR"+xConditions.get(i)+"/"+yConditions.get(i);

 }

 return signals;

}

}

Выводы:

В результате выполнения данной лабораторной работы я приобрёл навыки по автоматизации соседнего кодирования графа переходов автомата Мили. Соседнее кодирование реализовано по алгоритму, описаному выше.


 

А также другие работы, которые могут Вас заинтересовать

52119. Розвязування раціональних рівнянь 107.5 KB
  Мета: удосконалити вміння розвязувати раціональні рівняння; розвиток уваги і вміння чітко та математично грамотно висловлювати власну думку. Тип уроку: удосконалення знань і вмінь
52120. Означення квадратного рівняння. Неповні квадратні рівняння, їх розвязування 43.5 KB
  Неповні квадратні рівняння їх розвязування Мета: удосконалити знання учнів про означення квадратного рівняння; удосконалити вміння розвязувати неповні квадратні рівняння; розвиток концентрації уваги Тип уроку: удосконалення знань і вмінь Обладнання та наочність: картки для усного рахунку опорна схема правила проведення інтерактивної технології âРобота в парахâ Хід уроку І. Актуалізація опорних знань Запитання для фронтального опитування: означення квадратного рівняння; коефіцієнти квадратного рівняння; Опорна схема неповні...
52121. Розвязування тригонометричних рівнянь зведенням до однієї тригонометричної функції 7.06 MB
  Розвязування тригонометричних рівнянь зведенням до однієї тригонометричної функції. Формування в учнів умінь розвязувати тригонометричні рівняння способом зведення до однієї тригонометричної функції алгебраїчний спосіб розвивати логічне мислення уяву пам'ять виховувати інтерес до математики уважність відповідальність культуру математичних записів. Ми ніколи не станемо математиками...
52122. Розкладання многочленів на множники способом винесення спільного множника за дужки та способом групування 60 KB
  Тема: Розкладання многочленів на множники способом винесення спільного множника за дужки та способом групування. Які вирази називаються многочленами Що означає розкласти многочлен на множники Способи розкладання многочлена на множники Як розкласти многочлен на множники способом групування III.
52123. Решение задач с помощью производной 63 KB
  Активизировать познавательную деятельность учащихся путем решения задач с практическим содержанием. Оборудование: Портреты ученых Карточки с заданиями для устных упражнений Таблица Чертежи к задачам математические модели Минизадачники Ход урока В мире не происходит ничего в чем бы ни был виден смысл какогонибудь максимума или минимума Леонард Эйлер I. Выдающиеся ученые: француз Пьер Ферма 16011665 англичанин Исаак Ньютон 16431727 немец Готфрид Лейбниц16461716 француз Жозеф Лагранж 17361813...
52124. Розвязування систем рівнянь методом заміни змінної 4.01 MB
  Мета: освітня: формувати поняття однорідного многочлена симетричного многочлена; формувати умінь і навичок розвязування систем рівнянь методом заміни змінної та вироблення вмінь і навичок застосовувати цей спосіб під час розвязування систем рівнянь; розвиваюча: формувати вміння знаходити звязок з раніше вивченим: переносити набуті знання в нові ситуації; стимулювати учнів до висловлювань без побоювань помилитися; заохочувати знаходити свій спосіб фіксації пояснення нового матеріалу; виховна: виховувати культуру математичних міркувань;...
52125. Решение нестандартных задач в курсе алгебры 8-9 класса 1.46 MB
  Доказать что значение выражения является натуральным числом. А При каком положительном значении параметра сумма квадратов корней уравнения равна 16 Ответ: Б При каком отрицательном значении параметра сумма квадратов корней уравнения Ответ: Доказать что значение выражения натуральное число. Доказать что значение выражения чётное число отрицательное. Построить график функции const Построить график функции: а б в Доказать что график функции это две...
52126. Методи розвязування показникових рівнянь 1.22 MB
  Мета: Систематизувати й узагальнити знання уміння та навички учнів із теми формувати вміння учнів розвязувати показникові рівняння різними способами: зведення до однієї основи до спільного...