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;

}

}

Выводы:

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


 

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

26582. КЛАССИФИКАЦИЯ ПИЩЕВЫХ ЗАБОЛЕВАНИЙ 5.7 KB
  Само название пищевые заболевания пищевые токсикоинфекции пищевые токсикозы указывают что основную роль в их возникновении играют 'пищевые продукты. В зависимости от них все пищевые заболевания людей делят на две большие группы. ПИЩЕВЫЕ ЗАБОЛЕВАНИЯ НЕ БАКТЕРИАЛЬНОЙ ПРИРОДЫ типичные пищевые отравления. Пищевые заболевания не бактериальной природы с недостаточно изученной этиологией.
26583. КОНСЕРВИРОВАНИЕ КОЖЕВЕННОГО СЫРЬЯ 5.55 KB
  Шкуры консервируют посолом врасстил тузлукованием сухосоленым пресносухим и кислотносолевым способами. Шкуры укладывают на стеллажи мездрой вверх посыпая слоем соли до 1 см высотой штабеля 15 2 м. Каждый штабель комплектуют не более 3 суток с момента посола первой шкуры. Тузлукованием консервируют шкуры крупного рогатого скота конские верблюжьи и свиные.
26584. КОНСЕРВИРОВАНИЕ МЯСА ВЫСОКОЙ ТЕМПЕРАТУРОЙ. ВЕТСАНЭКСПЕРТИЗА И ГИГИЕНА ПРИГОТОВЛЕНИЯ БАНОЧНЫХ КОНСЕРВОВ. КОНСЕРВИРОВАНИЕ МЯСА И МЯСНЫХ ПРОДУКТОВ ВЫСОКОЙ ТЕМПЕРАТУРОЙ 16.98 KB
  Технология приготовления консервов сводится к тому что подготовленное мясо или другие продукты закладывают в жестяные или стеклянные герметически закрывающиеся банки которые подвергают стерилизации при температуре выше 100С. Консервный цех или завод имеет два основных отделения: 1 жестянобаночное где изготавливают банки и 2 технологическое в котором проводят все технологические операции при изготовлении консервов. Это необходимо при стерилизации банок когда под действием высокой температуры происходит расширение металла и содержимого...
26585. КОНСЕРВИРОВАНИЕ МЯСА ХОЛОДОМ. ИЗМЕНЕНИЕ В МЫШЕЧНОЙ ТКАНИ ПРИ ЗАМОРАЖИВАНИИ 14.63 KB
  Мясо по термическому состоянию согласно стандартам подразделяют на остывшее охлажденное подмороженное замороженное и оттаявшее. К остывшему относят мясо которое после разделки туши на глубине 8 см имеет температуру не выше 12 С. Остывшее мясо используют на предприятии где его получили вывоз для реализации ограничен исключение представляют продовольственные рынки. К охлажденному относят мясо температура в толще мышц которого не выше 4 С.
26586. ЛАБОРАТОРНЫЕ МЕТОДЫ РАСПОЗНОВАНИЯ МЯСА РАЗНЫХ ВИДОВ ЖИВОТНЫХ 5.55 KB
  ЛАБОРАТОРНЫЕ МЕТОДЫ РАСПОЗНОВАНИЯ МЯСА РАЗНЫХ ВИДОВ ЖИВОТНЫХ.По анатомоморфологическим особенностям туш скелета и внутренних органов убитых животных. Однако у одного и того же вида животных температура плавления жира колеблется в зависимости от пола типа кормления. СУЩНОСТЬ РЕАКЦИИ НА ГЛИКОГЕН ПО НИБЕЛЮ состоит в том что в мясе разных видов животных содержится неодинаковое количество гликогена: в парном мясе лошади более 2 в созревшем около 1 в мясе собаки 23.
26587. МЕРОПРИЯТИЯ ПРИ ОБНАРУЖЕНИИ СИБИРСКОЙ ЯЗВЫ НА СКОТОБАЗЕ МЯСОКОМБИНАТА 2.26 KB
  При обнаружении сиб.язвы после поголовного тщательного осмотра и поголовной термометрии в карантинном отделении неблагополучную партию делят на 2 группы: 1)больных и подозрительных по заболеванию и 2)подозреваемых в заражении
26588. МЕТОДЫ ВЫЯВЛЕНИЯ МЯСА БОЛЬНЫХ ЖИВОТНЫХ 18.96 KB
  МЕТОДЫ ВЫЯВЛЕНИЯ МЯСА БОЛЬНЫХ ЖИВОТНЫХ. У животных убитых в нормальном физиологическом состоянии место зареза неровное и интенсивнее пропитано кровью чем мясо в других местах туш; у животных убитых в агональном состоянии или разделанных после падежа место зареза ровное и пропитано кровью в такой же степени как и остальные мышцы. Удовлетворительное обескровливание наблюдают у старых переутомленных а иногда и больных животных. Плохо обескровлены как правило туши больных животных.
26589. МЕТОДЫ ИССЛЕДОВАНИЯ МОЛОКА ПРИ МАСТИТАХ КОРОВ 4.51 KB
  МЕТОДЫ ИССЛЕДОВАНИЯ МОЛОКА ПРИ МАСТИТАХ КОРОВ. из каждого соска вымени в середине или в конце доения на участки бумаги пропитанныe индикатором наносится капля молока. В луночку молочноконтрольной пластинки к 1 мл сборного молока приливают 1 мл 25 раствора мастоприма. Смесь молока с мастопопримом перемешивают стеклянной палочкой в течение 1020 секунд Результаты реакции оцениваются по консистенции смеси молока с местопримом.
26590. МЕТОДЫ ИССЛЕДОВАНИЯ МЯСА НА СВЕЖЕСТЬ 4.28 KB
  Состояние мышечной ткани – обращают внимание на корочку подсыхания цвет влажность консистенцию и запах; 2. состояние жира: цвет консистенция запах; 3. определение качества бульона – прозрачность и запах. Запах специфический приятный.