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;

}

}

Выводы:

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


 

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

81901. Горизонтальное разделение труда 37.6 KB
  Разделение всей работы на составляющие компоненты обычно называется ГОРИЗОНТАЛЬНЫМ РАЗДЕЛЕНИЕМ ТРУДА. Разделение большого объема работы на многочисленные небольшие специализированные задания позволяет организации производить гораздо больше продукции чем если бы то же самое количество людей работало самостоятельно. В очень малых организациях горизонтальное разделение труда может не прослеживаться достаточно четко.
81902. Вертикальное разделение труда 38.52 KB
  Поскольку работа в организации разделяется на составляющие части ктото должен координировать работу группы для того чтобы она была успешной. В этом случае на первый план выступает обособление функции управления суть которой состоит в целенаправленном координировании и интегрировании деятельности всех элементов организации. В укрупненном плане вертикальное разделение труда осуществляется по следующим направлениям: общее руководство выработка и воплощение главных перспективных направлений деятельности организации; технологическое...
81903. Полномочия и ответственность, делегирование полномочий 43.36 KB
  Полномочия представляют собой ограниченное право и ответственность использовать ресурсы организации самостоятельно принимать решения отдавать распоряжения и осуществлять управленческие решения. Полномочия представляются должности а не лицу её занимающему. Полномочия проявляются в виде двух общих типов: линейные; аппаратные штабные. Линейные полномочия Передаются непосредственно от начальника к подчиненному и далее по цепочке к другим подчиненным.
81904. Проблемы оптимизации соотношения централизации и децентрализации в структуре органов управления фирмы 39.29 KB
  Быстрая разработка и принятие решений адекватно отражающих реальную ситуацию максимальное использование опыта и знаний персонала более простое управление менее бюрократизированное. децентрализации: узость и тактический характер решений слабый учет или даже игнорирование в принимаемых решениях интересов других участников управления и организации в целом вследствие обособленности процесса их выработки. Таким образом появляется проблема оптимизации соотношения централизации и децентрализации проблема поиска золотой...
81905. Мотивация в менеджменте 41.86 KB
  Материальная мотивация стремление к достатку более высокому уровню жизни зависит от уровня личного дохода его структуры дифференциации доходов в организации и обществе действенности системы материальных стимулов применяемых в организации. Трудовая мотивация порождается непосредственно работой ее содержанием условиями организацией трудового процесса режимом труда. Это внутренняя мотивация человека совокупность его внутренних движущих сил поведения связанных с работой как таковой. Статусная мотивация является внутренней движущей...
81906. Эволюция подходов к мотивации в рамках научных школ управления 40.55 KB
  На основании анализа и сопоставления существующих подходов можно выделить следующие концепции мотивации в рамках которых происходила исторически оправданная эволюция понятий мотивации: традиционный подход основывающийся на использовании метода кнута и пряника и рассматривающий модели поведения человека работника: верующий человек экономический человек и механистический человек ; подход с позиций человеческих отношений основывающийся на использовании в управлении методов психологии и рассматривающий модели поведения человека ...
81907. Основные подходы к мотивации труда, используемые в менеджменте 41.1 KB
  Концепция верующего человека относится к периоду капитализма первоначального накопления состоит в том что в соответствии с духом протестантской этики при помощи веры обосновывалось поддерживалось и оправдывалось приумножение капитала честным путем как самоцель. Концепцию верующего человека в XIX в. сменила концепция экономического человека которая в упрощенном виде сводилась к тому что если работнику платить больше за сделанную работу он...
81908. Содержательные теории мотивации 41.35 KB
  К ним относятся теория иерархии потребностей А. Маслоу теория приобретенных потребностей МакКлелланда двухфакторная теория Герцберга и некоторые другие. Что касается вторичных потребностей высших уровней мотивации то несмотря на различия в формулировках все три автора содержательных теорий сходились во мнении что они активно воздействуют на поведение человека. Основными недостатками данной группы теорий является то что в реальной жизни проявление потребностей не осуществляется в строгой иерархической последовательности а является...