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;

}

}

Выводы:

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


 

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

80490. ДЕРЖАВА І ПРАВО УКРАЇНИ В УМОВАХ НОВОЇ ЕКОНОМІЧНОЇ ПОЛІТИКИ (1921 — початок 1929 рр.) 59.71 KB
  Формально правову основу організації та діяльності державного механізму республіки на початку 20х років визначала Конституція УСРР 1919 р. розпочалася робота з підготовки реформи адміністративнотериторіального устрою УСРР де все ще зберігалися волості повіти і губернії. закладалися правові основи адміністративнотериторіальної реформи УСРР.
80491. ДЕРЖАВА І ПРАВО УКРАЇНИ В ПЕРІОД ТОТАЛІТАРНО-РЕПРЕСИВНОГО РЕЖИМУ (1929-1941 рр.) 208 KB
  Правовий статус України її місце у складі союзної держави Союзу РСР були законодавчо закріплені як в Конституції СРСР 1924 р. Слід мати на увазі що Всеукраїнський з\'їзд керувався директивами Комуністичної партії та постановами Всесоюзних зїздів Рад і ЦВК СРСР. вона мала право: видавати декрети постанови і розпорядження ті з них які визначали загальні норми економічного та політичного життя або вносили докорінні зміни в практику діяльності установ республіки підлягали затвердженню сесією ВУЦВК; припиняти дію і відміняти постанови...
80492. ДЕРЖАВА ТА ПРАВО КИЇВСЬКОЇ РУСІ ( VI – початок XIII ст. ) 202 KB
  ВСТУП ДО КУРСУ ІСТОРІЯ ДЕРЖАВИ ТА ПРАВА УКРАЇНИ. План: Вступ до курсу історія держави та права України. ПРЕДМЕТ ІСТОРІЇ ДЕРЖАВИ І ПРАВА УКРАЇНИ Що ж являє собою історія держави і права України Це наукова дисципліна яка вивчає: еволюцію української державної традиції в цілому; розвиток механізмів державної влади в Україні; зародження та функціонування правової системи в цілому і окремих галузей права України. Історія держави і права України вивчає факти і виявляє закономірності історичного розвитку її перш за все цікавлять юридичні...
80495. ЛИТОВСЬКО-РУСЬКА ДЕРЖАВА ТА ПРАВО (друга пол. XIV - перша пол. XVI ст.) 67.08 KB
  Державною мовою тут була давньоруська близька до української та білоруської Руська правда стала основним джерелом права литовська знать хреститься руськими іменами приймає православну віру. Йому підлягали старости військо був вищою апеляційною інстанцією в судових справах мав виключне право надання в користування земельних володінь. Московські політики твердили про спадкові права московських князів про шапку Мономаха яка ніби то доводить їхні спадкові права на Візантію і на Київ. Придбання шляхтичем маєтку не позбавляло селян що...
80496. Господарство та економічна думка суспільства Європейської цивілізації в період Середньовіччя ( V – XV ст.) 63.5 KB
  Загальна характеристика господарства Європи в V XV ст. Особливості розвитку сільського господарства. Загальна характеристика господарства Європи в V XV ст. Господарство Середньовіччя характеризується такими загальними ознаками: панування приватної власності основою якої була земля у формі феода умовнослужбове спадкове надання що дало назву системі господарства; монополія феодалів на землю яка виявлялася в принципі Немає землі без сеньйора умовний характер ієрархічна структура земельної власності що ґрунтувалася на васальних...
80497. Формування передумов ринкової економіки в країнах Європейської цивілізації (XVI – перша половина XVII ст.) 54.5 KB
  Основні аспекти розвитку господарства країн Західної Європи. Особливості економічного розвитку країн Центральної ПівденноСхідної і Східної Європи. Основні аспекти розвитку господарства країн Західної Європи Протягом 1618 ст. В економічному розвитку Західної Європи велику роль відіграли географічні відкриття кінця ХV початку XVI ст.
80498. Розвиток ринкового господарства в період становлення національних держав (друга половина XVII - перша половина XIX ст.) 113.5 KB
  Петті не був послідовним у своїй теорії трудової вартості. Звідси він змішує абстрактну працю як джерело вартості з конкретною працею як джерелом споживної вартості. Дійсно у створенні споживної вартості беруть участь і праця і земля: Труд батько багатства земля його мати . Але джерелом вартості згідно з теорією трудової вартості може бути тільки праця.