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;

}

}

Выводы:

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


 

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

25429. Женщины – один из наиболее значимых объектов социальной работы 47.5 KB
  Женщины составляют большинство населения в России где их доля равна 531 881 мужчина на 1000 женщин. Для возрастной структуры России гендерный аспект имеет особое значение: среди жителей страны в возрасте 60 лет и старше доля женщин составляет более 65 диспропорция мужского и женского населения что ведет к женскому одиночеству. Исследованием положения женщин вплотную заняты 2 науки: гендерология и феминология. Предмет гендерологиисоциальные статусы женщины и мужчины определяющие определенный характер их взаимодействия и...
25430. Основные направления социальной работы с женщинами 38 KB
  Женщины социальнодемографическая группа населения которая в силу своих особенностей является категорией особенно нуждающейся в социальной помощи.Основной признак выделения женщин в качестве особой социальнодемографической группы и специфической категории клиентов социальной работы заключается в их генеративной функции то есть способности к деторождению. Споры о роли женщины в обществе о ее социальном положении существовал всегда но на каждом историческом этапе вставал с особой характерной для того времени остротой.
25431. Место и роль пожилых и старых людей в современном обществе 54.5 KB
  Структура ответа: Вступление Понятие пожилого и старого человека Исторический аспект положения пожилых и старых людей в обществе Современная ситуация. За последние 60 лет доля в населении детей уменьшилась почти вдвое а доля пожилых и старых людей в возрасте после 60 лет напротив возросла почти втрое. Согласно международным критериям например ООН население страны считается старым если доля людей в возрасте 65 лет и старше превышает 7.
25432. Регион как объект хозяйствования и управления 51.34 KB
  Реализя крупн региональн программ программ развития сырьевых экологичх освоения террии Одна из задач районирования обеспечить управляемость развитием государства. Региональные структуры характерные для РФ: 1. Суть воспроизводственного подхода Требует обеспечить преимущ региона и использовать возможности при комплексн развитии хозяйства региона.Воспроизводственный процесс единство внутренних и межрегиональных связей обеспечив последовательный процесс прва распределения обмена потребления.
25433. Отличительные особенности регионального воспроизводственного процесса 11.9 KB
  Через четыре месяца вышел первый номер Бюллетеня оппозиции . До 7080 материалов Бюллетеня принадлежали его перу. Всего вышло 87 книжек Бюллетеня .
25434. Социальный работник – клиент - особенности взаимодействия. Клиент в системе социальной работы. Структура социальной помощи клиенту в системе соц.обслуживания 21.46 KB
  работе помощь клиента соц.работника и клиента является восприятия последнего как неповторимой личности. Основными принципами работы с пожилыми людьми являются уважение и интерес к личности клиента акцент на нужности и полезности его опыта и знаний окружающим людям. Определение типа клиента первый шаг в установлении контакта так как отношение и взаимодействие соц.
25435. Клиент в системе социальной работы 13.52 KB
  одним из важнейших условий взаимодействия ср и клиента является восприятие последнего как неповторимой личности. полного знания о клиенте не может быть никогда но ср надо стремиться к тому чтобы получить те знания от клиента которые нужны ему для оказания помощи.Джонсон типы клиента: ищут помощи для себя просят помощи для другогодругих не ищут помощино тем или иными причинами угрожают жизнедеятельности другого чела ищут или используют помощь как средство для собственных целей ищут помощи но не для достойных целей Определение типа...
25436. Идеологическая подготовка масс к предстоящей войне 13.71 KB
  Воскресные номера газет за 22 июня 1941 г. 22 июня в 12 часов дня Центральное радио передало правительственное Заявление о вероломном нападении фашистской Германии на СССР. 22 июня ЦК ВКПб и правительство ввели военное положение на территориях Прибалтики Белоруссии Украины Молдавии и ряда областей РСФСР. 23 июня была объявлена мобилизация военнообязанных 19051918 гг.
25437. Проблематика советской журналистики периода Великой Отечественной войны 13.22 KB
  центральными оставались несколько тематических направлений: освещение военного положения страны и боевых действий Советской Армии; всесторонний показ героизма и мужества советских людей на фронте и в тылу у врага; тема единства фронта и тыла; характеристика военных действий Советской Армии на территориях европейских стран освобождаемых от фашистской оккупации и Германии. центральными оставались несколько тематических направлений: освещение военного положения страны и боевых действий Советской Армии; всесторонний показ героизма и мужества...